본문 바로가기

Study/Algorithm & Ds6

Disjoint Set (Union find) Disjoint set이라고도 하고 union find라고도 하는 이 방법은 어느 두 집합을 합치고, 어느 두 요소가 같은 집합에 존재하는지 빠르게 알 수 있게 하는 방법이다. Disjoint Set은 아래 두 연산을 구현한다. union(a,b)는 a가 속한 집합과 b가 속한 집합을 합치는 연산이다. find(a)는 a가 속한 집합을 반환하는 연산이다. 아래는 위 두 연산을 사용하였을 때의 예제이다. 1~5의 요소가 있다고 하자. 각 요소는 초기에 서로 다른 집합에 속한다. (1), (2), (3), (4), (5) 1이 속한 집합과 2가 속한 집합을 합치자. : union(1,2) 결과 : (1,2), (3), (4), (5) find(1) == find(2)는 true이어야 한다. find(2) =.. 2023. 5. 1.
Binary Heap (이진 힙) 힙은 아래 성질을 만족하는 Alomost complete binary tree이다. Max heap의 경우 parent node의 값은 child node의 값보다 크거나 같다. Min heap의 경우 parent node의 값은 child node의 값보다 작거나 같다. 아래의 모든 설명은 Max heap을 기준으로 한다. Max heap의 경우 tree 내의 모든 노드에 대해 parent node의 값은 child node의 값보다 작지 않다. 그래서 Max heap에선 root node의 값이 가장 크다. 값을 삽입하고 뺄 때도 이 성질을 유지하면 root에서는 항상 tree 내의 가장 큰 값이 존재하게 된다. Cpp의 priority queue를 사용해 본 적이 있는가? 어떤 값을 priority.. 2023. 1. 31.
Binary Search, 이진탐색 정렬된 배열에서 특정 값의 위치 찾기 아래의 정렬된 배열에서 6을 찾는다고 하자. ---------- 0123456789 지금은 배열 전체가 탐색 범위이다. 여기서 중앙에 있는 값과 목표로 하는 값(6)을 비교해 보자. 중앙에 있는 값은 index가 4인 값이다. floor((0 + 9)/2) = floor(4.5) = 4, arr[4] target 임으로 i.. 2023. 1. 6.
Next permutation, 다음 순열 구하기 어떤 순열이 주어져 있을 때 다음 순서의 순열을 구하는 알고리즘이다. 참고로 여기서 말하는 순서는 어떤 요소들로 순열을 만들고 이 순열들을 사전 순서대로 정리하듯 정렬하였을 때를 기준으로 한다. 예를 들어 어떤 1, 2, 3을 가지고 모든 순열을 만들고 이를 사전 순서대로 정리하면 아래와 같다. 123 132 213 231 312 321우리가 하고자 하는 것은 어떤 순열이 주어졌을 때 다음 순열을 구하는 것이다. 예를 들어 231 이 주어졌을 경우 312를 반환하는 것이다. Algorithm 어떤 순열을 arr라고 하자. arr[i] arr[i] 인 j 중 가장 큰 j를 구한다. swap(arr[i],arr[j]).. 2022. 4. 4.
Merge Sort (합병 정렬) Merge Sort는 배열의 값을 정렬하는 여러 가지 방법 중에 하나이다. Merge Sort는 정렬이 된 부분 배열들을 합쳐가면서 정렬을 수행한다. 정렬이 된 배열들을 합친다는 것이 Merge Sort의 핵심 아이디어이다. 이 아이디어를 이용하여 어떻게 전체 배열에 대해 정렬을 수행할 수 있을까? Merge Sort (합병 정렬)로 배열을 정렬하는 방법에 대해 알아보자. 참고로 이 글에서는 오름차순으로 정렬할 것이다. Merge 정렬에 대해 생각하기 전에, 정렬이 된 두 배열을 합치는 작업에 대해 생각해보자. 함수 merge가 이 작업을 수행한다고 해보자. merge의 입력으로 들어오는 두 배열은 이미 정렬이 되어 있어야 하고 반환하는 결과물도 정렬이 되어 있어야 한다. 사실, 두 배열이 정렬이 되어있.. 2021. 9. 17.
Fenwick Tree (펜윅 트리, Binary Indexed Tree = BIT) 배열에서 어느 구간의 구간합을 구한다고 하자. 누적합을 저장한 배열을 사용하면 특정 구간의 구간합을 단순히 두 위치의 값을 빼줌으로 상수 시간에 쉽게 구할 수 있다. 그러나 만약 배열의 값이 자주 바뀐다면 문제가 생긴다. 만약 원래 배열의 k번째 값이 변경된다면 누적합을 저장한 배열에서 k번째와 그 이후의 값들은 모두 변경해주어야 한다. 최악의 경우엔 누적 값을 저장한 배열의 n개의 값들을 다 변경해주어야 한다. 데이터의 양이 많으면서 데이터의 값이 자주 수정된다면 누적합은 사용하기 적합하지 않은 방법이다. 이때 펜윅트리를 사용하면, O(logn)에 해결할 수 있다. 이번 글에서는 펜윅트리에 대해 알아보겠다. 참고로 이번 글에서 n번째라고 하면 배열에서 처럼 0부터 셈을 하는 것이 아닌 일상에서 처럼 1.. 2021. 5. 13.

티스토리툴바