[알고리즘] 가장 긴 증가하는 부분 수열 (LIS)

가장 긴 증가하는 부분 수열 (Longest Increasing Subsequence)

• 가장 긴 증가하는 부분 수열을 찾는 문제는 유명한 다이나믹 프로그래밍 문제이다.
• 직관적인 O(N^2) 알고리즘과 좀 더 복잡한 O(NLogN) 알고리즘으로 나뉜다.

O(N^2) 알고리즘

• O(N^2) 알고리즘은 다음과 같은 점화식을 통해 구할 수 있다.

  DP[i] : i번째 원소를 마지막으로 하는 LIS 길이
  DP[i] = 1 ~ i-1 까지 원소들을 순회하며, i번째 원소보다 값이 작은 것 중 가장 큰 DP값+1

for (int i = 0; i < n; i++) {
	for (int j = 0; j < i; j++) {
    	if (arr[j] < arr[i]) 
        	dp[i] = max(dp[i], dp[j] + 1);
    }
}

O(NLogN) 알고리즘

• 위 알고리즘은 DP[i]를 구할 때 1 ~ i-1까지 모두 순회해야해서 시간복잡도가 높다.
• O(NLogN) 방식은 이진탐색(LogN)을 통해 해당 순회를 대체하기 때문에 전체 시간복잡도가 O(NLogN)이 된다.
• 알고리즘은 다음과 같은 방식으로 이뤄진다.

• 다음과 같은 리스트 L을 업데이트하며 동작한다.
• L[i] = 길이 i인 증가하는 부분 수열을 만들 수 있는 마지막 원소 중 가장 작은 값
• L의 크기가 곧 현재까지 만들 수 있는 LIS의 길이이며 처음에는 빈 리스트로 시작한다.
• L의 업데이트는 수열의 원소들을 순회하며 다음과 같이 이뤄진다.
  1. L이 비어있거나 현재 L의 마지막 원소보다 cur(현재 원소)가 더 클 경우
  --> L의 뒤에 cur을 추가한다.
  2. 그렇지 않을 경우
  --> L리스트에서 lower bound를 찾아서, 그 자리를 cur로 바꾼다.

for (int i = 0; i < N; i++) {
	int cur = arr[i]
    int index = lowerBound(0, len, cur);
    L[index] = cur;
    if (index == len) len++; // 1번 케이스 
}