뜌릅

집합의 요소들의 구성 여부를 표현할 때 유용한 테크닉 왜 비트마스크를 사용하는가? DP나 순열 등, 배열 활용만으로 해결할 수 없는 문제 작은 메모리와 빠른 수행시간으로 해결이 가능 (But, 원소의 수가 많지 않아야 함) 집합을 배열의 인덱스로 표현할 수 있음 코드가 간결해짐 비트마스크는 2진법으로 사용하는 것을 비트마스크라고 합니다. 예시) [1,2,3,4,5]라는 집합이 있을때 임의로 몇개를 골라서 뽑는 경우를 구한다고 해보자. 원래라면 각 배열의 요소를 for문을 통해 접근하면서 확인해야 할 것이다. 하지만 비트마스킹으로 구현하게 되면 int 하나로 표현이 가능하다. [1,2,3,4,5] => 11111 => 31 [1,2,3] => 00111 => 7 [1,2,5] => 10011 => 19 이..

다익스트라 알고리즘은 특정 정점에서 다른 정점으로가는 최단 경로를 구합니다. 여기서 DP가 적용이 됩니다. DP는 이미 최단경로를 구한 곳은 다시 구할 필요가 없기 때문입니다. 이를 활용해 정점에서 정점까지 간선을 따라 이동할때 최단경로를 구할 수 있습니다. 우선순위 큐를 사용하여 구현하였습니다. void dijkstra(vector matrix, int start){//인접 행렬임 vector distance(matrix.size(), INT_MAX); priority_queue pq; pq.emplace(0,start); distance[start] = 0; while(!pq.empty()){ int cost = pq.top().first; int cur = pq.top().second; pq.pop..

최소 공통 조상을 찾는 알고리즘입니다. 두 정점이 만나는 최초 부모 정점을 찾으면 됩니다. 예시)13번과 15번의 공통 조상 노드는 5번노드이다. 예시) 13번과 11번 노드의 공통조상은 1번노드이다. LCA 알고리즘을 푸는 방법은 인풋(트리의 형태)가 어떻게 주어지느냐에 따라 다르지만 기본적으로 root노드와 자식노드만 알고있다고 가정해보겠습니다. LCA을 풀기위한 가장 효율적인 방법은 Sparse Tree을 사용하는 것입니다. 이 방법은 우선 DFS을 이용하여 Depth(해당 레벨에 어떤 노드들이 존재하는지 알려주는 배열), Parent(해당 노드의 부모 노드를 알려주는 배열)을 구합니다. const int MAX = 100001; // 최대 노드 수 const int LOG = 17; // 2^17..

최장 증가 부분 수열은 배열에서 가장 긴 증가하는 수열을 찾는 알고리즘입니다. 예시) [ 7, 2, 3, 8, 4, 5 ] → 해당 배열에서는 [2,3,4,5]가 LIS로 답은 4 예시) [ 6, 2, 5, 1, 7, 4, 8, 3] -> [2,5,7,8] DP로 풀기 일반적으로 푸는 방법은 DP을 이용하여 푸는 것입니다. 이중 포문을 통하여 구현하며 시간복잡도는 O(N^2)가 나옵니다. 방법은 간단합니다. Bottom to Top형태의 DP을 사용합니다. i = 1 부터 Dp의 값을 계산해 나갑니다. i번째의 배열값은 자기보다 작은 index인 j번째 배열값들과 비교하여 더큰지를 비교합니다. 만약 더 크다면 해당번째의 Dp값을 비교합니다. Dp[i]의 의미는 i번째 인덱스에서 끝나는 가장 큰 최장 증가..

그래프 알고리즘으로, 문제를 풀 때 상당히 많이 사용합니다. 경로를 찾는 문제 시, 상황에 맞게 DFS와 BFS를 활용하게 됩니다. DFS 깊이 우선 탐색입니다. 모든 경로를 탐색해야 할 경우에 적합하며 노드에서 다른 브랜치를 찾아보기 이전에 현재 브랜치를 모두 탐색한 후에 다음 브랜치를 탐색합니다. 스택 or 재귀를 통해서 구현할 수 있습니다. 하지만 재귀 또한 Stack Trace을 통해서 작동하는 것이기 때문에 본질은 같다고 할수있습니다. 시간 복잡도는 다음과 같습니다. 인접 행렬 : O(V^2) 인접 리스트 : O(V+E) 둘의 시간복잡도는 같으나 이 또한 구조체의 특징때문에 차이가 발생하는 것이지 동작 자체는 동일합니다. 각 노드에 대해 탐색해야할 모든 브랜치를 탐색하게 되므로 인접행렬은 O(V..

이분탐색은 두 부분으로 찾을때까지 분할하면서 찾는 탐색알고리즘 입니다. 선형탐색보다 압도적으로 속도가 빠르지만 정렬된 알고리즘에 한해서 사용할수 있다는 제약이 있습니다. 변수 3개(start, end, mid)를 사용하여 탐색합니다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색의 과정입니다. int binary_search(vector arr, int target) { sort(arr.begin(), arr.end()); int left = 0; int right = arr.size() - 1; int mid = 0; while(left arr[mid])left = mid + 1; } return arr.size(); }

기수정렬 기수정렬( radix sort )은 낮은 자리수부터 정렬해가는 것을 기본 개념으로 하는 정렬 알고리즘입니다. 기수 정렬은 비교연산을하지 않으며 정렬 속도가 빠르지만 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요합니다. 일반적으로 자릿수가 고정되어 있습니다. 다음은 자연수에 대해 기수 정렬하는 과정입니다. 0~9까지 버킷(Queue)을 준비합니다. 모든 데이터에 대해 가장 낮은 자릿수부터 버킷에 알맞게 데이터를 둡니다. 0부터 차례대로 버킷에서 데이터를 다시 가져옵니다. 가장 높은 자릿수를 기준으로 하여 자리수를 높여가며 2번 3번 과정을 반복합니다. 예시 아래의 8개 데이터에 대하여 기수 정렬을 시도해 보겠습니다. 위의 그림과 같이 각 숫자에 해당하는 Queue공간을 할당하고 진행..

개념 힙 정렬은 힙을 통해 구현하는 정렬 알고리즘입니다. 힙이란 간단하게 말하자면 최댓값, 최솟값을 쉽게 추출해낼수 있는 자료구조입니다. 이러한 힙트리를 구성해서 정렬을 하게 되는데, 오름차순 정렬을 위해서는 최소힙을 사용하고, 내림차순 정렬을 위해서는 최대힙을 사용합니다. 전체적인 과정은 다음과 같습니다. 정렬해야할 다음 n개의 요소들로 최소 힙(완전 이진트리)을 만듭니다. 그 다음으로 한번에 하나씩 요소를 힙에서 꺼내어 배열의 뒤에서부터 저장하면 됩니다. 삭제되는 요소들은 값이 증가하는 오름차순 형태로 정렬되게 됩니다. 다음은 내림차순 정렬을 위한 최대힙의 구조입니다. 코드 힙은 C++에서 priority_queue라는 우선순위 큐를 통해 이미 구현되어 있습니다. 따라서 우선순위 큐를 사용하여 구현해..

개념 분할정복 개념이 들어간 정렬 알고리즘입니다. 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략입니다. 퀵 정렬과 동일하게 순환호출을 통해서 구현합니다. 배열의 길이가 0 또는 1이면 이미 정렬된 것으로 봅니다. Base Case입니다. 배열의 길이가 2 이상인 경우에 정렬되지 않은 배열로 절반으로 잘라 두 서브 배열로 나눕니다. 각 서브 배열을 재귀적으로 합병하여 정렬합니다. 두 부분 배열을 다시 하나의 정렬된 배열로 합병합니다. 합병 정렬을 분할정복개념으로 나누면 아래와 같습니다. Divide: 입력 배열을 같은 크기의 2개로 나눈다. Conquer: 부분 배열을 정렬한다. 부분배열의 크기가 충분히 작지 않으면(base case) 순환호출을 통해 ..

개념 분할정복의 한 방법으로서, 평균적으로 매우 빠른 알고리즘에 속합니다. 우리가 라이브러리에서 사용하는 대부분의 정렬 함수는 퀵 정렬을 변형한 것입니다. 분할정복 답게 문제를 분리하여 각각 해결하고 합쳐서 해결하는 방식입니다. 배열안에 있는 요소를 선택합니다. 이렇게 고른 원소를 피봇이라고 합니다. 피봇을 기준으로 피봇보다 작은 원소들은 왼쪽으로 큰 원소들은 오른쪽으로 옮깁니다. 피봇을 제외한 왼쪽 배열과 오른쪽 배열을 각각 순환 호출을 통하여 피봇을 설정하고 왼쪽 오른쪽으로 나눕니다. 배열이 더이상 분할이 불가능할 때까지 반복합니다. 즉 피봇을 기준으로 분할하고 분할된 배열들을 합하여 정렬된 배열이 되게 하는 알고리즘입니다. 분할 정복기준으로 단계를 나누면 아래와 같습니다. Divide: 입력 배열을..