LIS 알고리즘 - DP(동적계획법)

 

LIS(최장 증가 부분 수열, Longest Increasing Subsequence) 알고리즘은 주어진 배열에서 가장 길게 증가하는 부분 수열을 찾는 알고리즘이다.

이 문제는 기본적으로 배열에서 연속적이지 않지만, 각 숫자가 이전의 숫자보다 커지는 수열을 찾는 문제이다.

LIS 문제는 여러 방법으로 해결할 수 있지만, 대표적인 두 가지 방법은 동적 계획법(DP) 과 이분 탐색을 이용한 방법이다.

 

1. LIS 알고리즘 DP(동적계획법)

 

동적 계획법을 이용한 LIS 문제 해결은 O(n²) 시간 복잡도를 가진다.

 

다음과 같은 배열이 주어졌을 때 {50, 3, 20, 10, 2, 1} DP를 적용한 계산 과정을 살펴보자.

 

먼저 간단하게 알고리즘을 살펴보면 다음과 같다.

• LIS[i]: 인덱스 i까지의 수열에서 끝나는 가장 긴 증가 부분 수열의 길이를 저장.
• 처음에는 모든 LIS[i] 값을 1로 설정(각각의 요소는 그 자체로 수열을 이루기 때문에 최소 1의 길이를 가지게된다.)
• 그 다음, 각 요소에 대해 이전 요소들과 비교하면서, 더 작은 값일 경우 해당 값에 1을 더해 길이를 갱신한다.

DP를 적용한 코드는 다음과 같다.

int n = nums.length;
int[] LIS = new int[n];
Arrays.fill(LIS, 1);

for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
        if (nums[i] > nums[j]) {
            LIS[i] = Math.max(LIS[i], LIS[j] + 1);
        }
    }
}

 

위의 코드를 살펴보자.

초기 상태에서 lisSize 리스트는 각 원소의 LIS 길이를 1로 설정해두고 시작한다. 

초기 배열:          {50, 3, 20, 10, 2, 1}
초기 lisSize:       [1, 1, 1, 1, 1, 1]

 

1) i = 1

• j = 0에서 비교 : nums[1](3) < nums[0](50) → 증가하는 수열이 아니므로 업데이트 없음.

LIS: [1, 1, 1, 1, 1, 1]

 

2) i = 2

•  j = 0에서 비교 : nums[2](20) < nums[0](50) → 증가하는 수열이 아니므로 업데이트 없음.
•  j = 1에서 비교 : nums[2](20) > nums[1](3) → LIS[2] = Math.max(LIS[2], LIS[1] + 1) = Math.max(1, 2) = 2

LIS: [1, 1, 2, 1, 1, 1]

 

3) i = 3 

• j = 0 에서 비교 : nums[3](10) < nums[0](50) → 증가하는 수열이 아니므로 업데이트 없음.
• j = 1 에서 비교 : nums[3](10) > nums[1](3) → LIS[3] = Math.max(LIS[3], LIS[1] + 1) = Math.max(1, 2) = 2
• j = 2 에서 비교 : nums[3](10) < nums[2](20) → 업데이트 없음.

LIS: [1, 1, 2, 2, 1, 1]

 

4) i = 4

•  j = 0 에서 비교 : nums[4](2) < nums[0](50) → 업데이트 없음.
•  j = 1 에서 비교 : nums[4](2) < nums[1](3) → 업데이트 없음.
• j = 2 에서 비교 : nums[4](2) < nums[2](20) → 업데이트 없음.
• j = 3 에서 비교 : nums[4](2) < nums[3](10) → 업데이트 없음.

LIS: [1, 1, 2, 2, 1, 1]

 

5) i = 5

• j = 0에서 비교: nums[5](1) < nums[0](50) → 업데이트 없음.
• j = 1에서 비교: nums[5](1) < nums[1](3) → 업데이트 없음.
• j = 2에서 비교: nums[5](1) < nums[2](20) → 업데이트 없음.
• j = 3에서 비교: nums[5](1) < nums[3](10) → 업데이트 없음.
• j = 4에서 비교: nums[5](1) < nums[4](2) → 업데이트 없음.

LIS: [1, 1, 2, 2, 1, 1]

 

최종 LIS 배열은 [1, 1, 2, 2, 1, 1]이 되며 이 배열의 최댓값이 LIS의 길이이므로, 주어진 배열의 최장 증가 부분 수열의 길이는 2이다.