[알고리즘] Disjoint Set. aka, 서로소 집합. aka, Union - Find
Disjoint Set이란? Disjoint Set을 번역하면 서로소 집합입니다. 이는 공통된 원소를 가지고 있지 않는 집합들을 표현하는 자료 구조 입니다. 즉, 교집합이 공집합이고, 상호배타적입니다. https://ko.wikipedia.org/wiki/%EC%84%9C%EB%A1%9C%EC%86%8C_%EC%A7%91%ED%95%A9 서로소 집합 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 집합론에서 서로소 집합(-素集合, 영어: disjoint sets)는 공통 원소가 없는 두 집합이다.[1] 예를 들어서 {1, 2, 3}과 {4, 5, 6}은 서로소이며 {1, 2, 3}과 {3, 4, 5}는 아니다. ko.wikipedia.org 어떻게 표현하나? 기본적인 원리는, 각 집..
2023. 1. 17.
[알고리즘] 누적합 (Prefix Sum)
누적합은 구간의 합을 빠르게 구하는 방법입니다. 1차원 배열에서의 누적합 아래와 같은 1차원 배열이 있습니다. A = [4, -2, 1, 5, -3] 위의 배열에서 인덱스 1번부터 3번까지의 합을 구하고자 합니다. 그럼 -2 + 1 + 5 = 4를 계산해야하니 시간복잡도는 O(N)입니다. 그런데 배열이 크고, 구간합을 자주 계산하게 된다면 시간이 오래 걸리기 때문에, 이럴 때 사용하는 것이 누적합니다. 누적합은 말그대로 누적해서 더하는 것입니다. 아래처럼요. S[n+1] = sum(0, n) 인덱스 0번부터 n번의 합 ( 계산의 편의를 위해 s[0]번은 비워둠 ) S = [0, 4, 2, 3, 8, 5] 일단 누적합을 계산해두고나면, 구간합을 아주 빠르게 구할 수 있습니다. 위의 예시처럼 인덱스 1번부터..
2023. 1. 13.
[알고리즘] LIS 최장 증가 부분 수열, SegmentTree
최장 증가 부분 수열이란? A라는 수열ㄹ에서 연속되는 것과 상관없이 Ai < Aj (단, i < j)를 만족하는 부분 수열입니다. [10, 20, 10, 30, 20, 50] 위와 같이 수열이 주어졌을 때, [10, 20] [10, 20, 30] [10, 20, 30, 50] ... 모두 증가 부분 수열이며, 그 중 가장 길이가 긴 부분 수열이 최장 증가 부분 수열입니다. 어떻게 구하나? 동적계획법을 이용하여 구할 수 있습니다. 수열 A가 주어졌을 때, D(i)를 i번째 수를 부분 수열의 마지막으로하는 부분 수열 중 가장 길이가 긴 수열의 길이라고 한다면, D(i)는 Ai보다 앞에 있고 Ai보다 작은 Aj의 j에 대하여 D(j)가 가장 큰 값 + 1이될 것입니다. 즉 index 0부터 차례로 순회하며 D..
2022. 10. 10.
