Divide and Conquer Optimization 작성일 2019-01-03 | In Hard-Algorithm 서론 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)$을 만족 더 읽어보기 »
monotone stack 작성일 2019-01-01 | In Medium-Algorithm monotone stack은 몇몇 문제들의 시간 복잡도를 O(n)정도로 줄어주는 강력한 테크닉입니다. 더 읽어보기 »
[UnionFind] Union Find의 최적화 작성일 2019-01-01 | In Medium-Algorithm 최악의 경우 이전 글 마지막 부분을 다시 가져와봅시다. 더 읽어보기 »
[UnionFind] Union Find의 Naive한 구현 작성일 2019-01-01 | In Medium-Algorithm 이번 글에서는 Union Find를 구현해봅시다. 배열을 이용한 구현과 트리를 이용한 구현, 총 두 가지를 살펴보도록 하겠습니다. 더 읽어보기 »