LIS - 가장 긴 증가하는 부분 수열
LIS는 이분탐색을 사용하는 기법이다. Longest Increasing Subsequence의 약자로써, 가장 긴 증가하는 부분 수열을 의미한다. 이에 대해 이해하면, 사실 가장 긴 감소하는 부분 수열에도 똑같이 응용 가능하다. [어떤 수를 어디에 놓을지]를 이분탐색으로 해결하는 것이 핵심이다. 위의 그림과 같이, [4, 2, 1, 5, 6, 3] 이라는 수열이 있다고 예를 들자. 이때 가장 긴 증가하는 부분 수열을 찾고자 할 때, 위에 일일이 적은 대로 앞에서부터 하나씩 골라서 확인해볼 수 있을 것이다. 그럼 방식은 2중 for-loop구조를 갖게 되므로, O(n^2)의 시간복잡도를 갖게 된다. 당연히 좋은 방법이 아니다. 위의 그림을 보자. 가장 긴 증가하는 부분 수열을 담을 LIS벡터 또는 배열을..
백준 2352 반도체 설계
www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net 이 문제는 이런 유형을 아예 처음 보았다면 이것이 LIS인지 쉽게 떠올리기 어려울 수도 있다. LIS에 대한 내용은 이전 포스팅에서 정리해두었으니 참조 부탁드린다. 위와 같이, 1에서 시작한 선은 4로 연결되고, 3에서 시작한 선은 6에서 끝난다. 그 시작점과 끝점을 두줄에 걸쳐 나열하였다. 윗줄에 1, 2, 3, 4, 5, 6을 굳이 쓴 이유는 출발점이 증가하는 순서대로 나열되어있다는 것을..
