서론
Divide and Conquer Optimization은 점화식이 아래 조건을 만족할 때 사용할 수 있습니다.
- 점화식 꼴 : $\displaystyle D(t, i) = min_{1 ≤ j < n}{D(t-1, j)+C(j, i)}$
- 조건 : $D(t, i) = D(t-1, j) + C(j, i)$을 만족하는 가장 작은 $j$를 $P(t, i)$이라고 할 때 $P(t, i) ≤ P(t, i+1)$을 만족
Divide and Conquer Optimization은 점화식이 아래 조건을 만족할 때 사용할 수 있습니다.
수정 예정
monotone stack은 몇몇 문제들의 시간 복잡도를 O(n)정도로 줄어주는 강력한 테크닉입니다.
이번 글에서는 Union Find를 구현해봅시다. 배열을 이용한 구현과 트리를 이용한 구현, 총 두 가지를 살펴보도록 하겠습니다.
Union Find는 상호 배타적 집합(disjoint set)을 표현할 때 쓰는 자료구조입니다.
라고 설명을 하면 무슨 소리인지 잘 모를 수도 있겠죠.
아주 간단하게 설명하자면, 전체 집합을 공통원소가 없는 부분 집합들로 나눠서 저장하는 자료구조입니다.
이전 글에서 Max-Flow를 구하는 방법에 대해 알아보았고, 마지막 부분에서는 문제 하나를 풀어보았습니다.
icpc.me/11375 문제를 풀어보았고, 문제를 그래프로 모델링하면 아래 사진처럼 그래프가 만들어졌습니다.