Algorithm
-
[Algorithm] - 부분합Algorithm/Algorithm 2022. 9. 24. 00:39
부분 합 부분 합이란? 흔히 부분합 알고리즘은 시작점 S 부터 끝점 E까지의 모든 합을 구하는 문제입니다. 하지만, 주어진 시간내에 주어지는 모든 범위의 부분합을 구하기 위해선, 일일이 다 더해주는 것은 비효율적인 일입니다. 임의의 배열을 만들어, 일일히 더하는 것이 아닌 모든 동작을 한번에 하도록 처리하여 주는 것이 주요 목표입니다. O(N) -> O(1) 아이디어 index 2~4까지의 값을 구하려고 합니다. 이 때 부분합은 arr[2]+arr[3]+arr[4]라고 할 수도 있지만, sum[5]-sum[2]와도 같습니다. 만약 부분적으로 특정 값을 빼고 넣어준다고 하여 봅시다. [4,4,4,4,4] 라는 배열에서 1부터 마지막 index까지 6을 추가 2부터 3까지 index만 5를 추가한다고 해봅시..
-
[프로그래머스] - 여행경로Algorithm/프로그래머스 2022. 9. 16. 18:34
문제 [프로그래머스] - 여행경로 https://school.programmers.co.kr/learn/courses/30/lessons/43164 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 이해 더보기 문제 설명 주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다. 항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요. 제한사항 모든 공항은 알파벳 대문자 3글자로 이루어집니다. 주어진 공항 수는 3..
-
[프로그래머스] - 섬 연결하기Algorithm/프로그래머스 2022. 9. 16. 18:27
문제 [프로그래머스] - 섬 연결하기 https://school.programmers.co.kr/learn/courses/30/lessons/42861# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 이해 더보기 문제 설명 n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요. 다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 ..
-
[Algorithm] - LCA ( 최소 공통 조상 )Algorithm/Algorithm 2022. 9. 15. 00:46
LCA ( Lowest Common Ancestor ) 최소 공통 조상은 트리 구조에서 임의의 두 정점이 갖는 가장 가까운 조상 정점을 의미한다. 아래 그림에서 노드 13번과 15번 노드의 공통 조상을 찾는다한다. 따라 올라가게 되면 5번 노드가 공통 조상이다. 아래 그림에서 노드 13번과 11번 노드의 공통 조상을 찾는다한다. 따라 올라가게 되면 1번 노드가 공통 조상이다. 알고리즘 1. a,b 노드의 깊이를 파악한다. 2. 깊이가 동일하다면 상위 노드를 찾아가면서 동일한 노드가 나올 때까지 추적 그렇다면 노드의 깊이를 어떻게 파악할 것인가? DFS로 root 노드로 부터 깊이를 미리 구해둔다. 또한, 깊이를 구하면서 자신의 부모 노드를 기억하여 두고 부모 노드로 추적할 수 있게끔 할 수 있어야한다. ..
-
[Algorithm] - 정렬Algorithm/Algorithm 2022. 9. 2. 14:06
알고리즘이란? 가정 : 정렬할 데이터가 담긴 배열(리스트)의 각 원소를 O(1) 시간에 접근 가능한가? 결과 : C , Python과 같은 배열인 경우 가능 하지만, 그렇지 않은 경우가 있다. 데이터가 HDD 에 있다면 ? 메인 메모리에 올라와 있어야만 이 가정이 통한다. 정렬 1. 버블 정렬 시간 복잡도 : O(N^2) Stable Sort ( 같은 값이라 하여도 순서를 보장 ) 맨 왼쪽 원소부터 바로 이웃한 원소와 비교해 가면서, 큰 수가 오른쪽으로 가도록 교환 이 과정을 다시 나머지 n-1개 수에 대해서 반복 2. 삽입 정렬 시간 복잡도 최악의 경우 : O(N^2) , 최상 O(N) Stable Sort ( 같은 값이라 하여도 순서를 보장 ) 정렬 대상이 될 원소를 두 부분으로 나눔 앞은 '이미 정..
-
[Algorithm] - DPAlgorithm/Algorithm 2022. 9. 1. 22:30
DP(Dynamic Programming) 동적 프로그래밍으로, 큰문제를 작은 문제로 나누어 푸는 문제이다. Devide & Conquer과 비슷하지만, DP는 작은 문제로 나누어 반복되는 것을 이용해가면서 푸는 것이다. 반복되는 작업을 푸는 것은 Recursion으로 풀이가 가능하지만, 반복되는 작업을 또 하기보다 값을 저장하여 두고 다시 재사용하는 방식으로 푸는 것이 특징. ( Memoization) 대표 문제 Fibonacci / Knapsack problem 아래 그림과 같은 형태로 재귀로 풀이가 가능하지만, 매번 재귀로 풀이시 동일한 값을 또 사용할 수 있다. BOJ 2293번 각 Data에서 단계를 나누어 가능한 경우의 수를 늘려준다. idx 0 1 2 3 4 5 6 7 8 9 10 (k) d..
-
[Algorithm] - 위상 정렬Algorithm/Algorithm 2022. 9. 1. 22:26
위상 정렬 방향 그래프에서 간선으로 주어진 정점 간 선후 관계를 위배하지 않도록 나열하는 정렬 싸이클이 존재하는 경우는 발생할 수 없다 일반적으로 방향그래프로 설정이 되어 있기 때문에 Indegree 값이 0인 Node들에서 먼저 시작하면서 VFS 처럼 구현하면 된다. 위상 정렬의 결과가 Node들의 수와 동일해야 한다! ( 동일하지 않는 경우는 Cycle이 발생된 경우 ) 알고리즘 시간 복잡도 : O( V+E ) 1. 처음 방향 그래프들의 Edge를 읽으며, Indegree Table을 설정 2. Indegree가 0인 Node들을 Queue에 넣는다. 3. Queue에 Node들을 꺼내며, 위상 정렬 값 추가 4. 연결된 Node들의 Indgree값을 줄여주고 , 0이면 Queue에 추가 5. 3~4..
-
[Algorithm] - HEAP(우선 순위 QUEUE)Algorithm/Algorithm 2022. 9. 1. 16:56
Heap - 우선 순위 Queue Pop을 할 때 가장 먼저 들어온 원소가 나오는 대신 , 우선 순위가 가장 높은 원소가 나온다. 원소의 추가 O(LogN) 우선 순위 높은 ITEM 확인 O(1) 우선 순위 높은 순서 제거 O(LogN) 이진 검색 트리와 Heap 은 다른 자료 구조다. import heapq BOJ 1715번 - 카드 정렬하기 IDEA 1. 작은 값 2개 값을 더하는게 최소의 경우이다. ( GREEDY ) -> 작은 값을 더하지 말고 다른 값을 더하였을 경우보다 더 작은 경우가 발생 불가능! 2. 수의 범위가 1000일 때, 10만개인 경우에 INT형의 범위를 벗어나는가? -> INT형의 범위를 벗어나지 않아 별도로 생각하지 않아도 된다. 3. 예외 처리 1개만 들어온 경우는 최소..