LIS - 가장 긴 증가하는 부분 수열
LIS는 이분탐색을 사용하는 기법이다. Longest Increasing Subsequence의 약자로써, 가장 긴 증가하는 부분 수열을 의미한다. 이에 대해 이해하면, 사실 가장 긴 감소하는 부분 수열에도 똑같이 응용 가능하다. [어떤 수를 어디에 놓을지]를 이분탐색으로 해결하는 것이 핵심이다. 위의 그림과 같이, [4, 2, 1, 5, 6, 3] 이라는 수열이 있다고 예를 들자. 이때 가장 긴 증가하는 부분 수열을 찾고자 할 때, 위에 일일이 적은 대로 앞에서부터 하나씩 골라서 확인해볼 수 있을 것이다. 그럼 방식은 2중 for-loop구조를 갖게 되므로, O(n^2)의 시간복잡도를 갖게 된다. 당연히 좋은 방법이 아니다. 위의 그림을 보자. 가장 긴 증가하는 부분 수열을 담을 LIS벡터 또는 배열을..
위상정렬 - topological sort (비선형 자료구조의 선형화)
비교적 빠른 습득이 가능하고, 효용성도 좋은 알고리즘이라고 생각한다. 문제를 보면 위의 그림과 같이, A,B,C,D가 만드는 쌍(pair)에 대한 관계를 표현하고, 이를 통해 일종의 논리적 체인을 구성해야 하는 일이 있다. 그리고 아래와 같이, 그래프 상에서 DP를 해야하는 경우도 있다. 위의 그림을 조금 더 살펴보자. 위에서 처럼 A에 1을 놓고 전파를 시작한다. A에서 갈 수 있는 정점은 B와 C이므로 B와 C에 A로부터 받은 1을 합산해준다.(모든 정점의 초기값은 0이었다, A를 제외하고.) 위와 같이, E까지 전파하면, BFS를 돌렸을 때, 모든 정점에 대한 방문체크가 끝나고, 그림에서와 같은 값을 갖게 된다. 하지만 이는 올바르지 않다. 전파하는 와중에 값이 변경된 정점이 있기 때문이다. C의 ..
