[코딩테스트 합격자 되기(Java)] 문제 68. LIS길이계산하기★ ★ ★

문제

정수배열 nums에서 LIS의 길이를 찾는 함수를 작성하세요.

제약조건

• nums는 최대길이 1,000의 정수 배열입니다.
• nums의 각 요소는 -1,000 이상 1,000 이하의 정수입니다.

 

입출력 예

nums	return
[1, 4, 2, 3, 1, 5, 7, 3]	5
[3, 2, 1]	1

 

 

 

---

풀이 및 코드

LIS(Longest Increasing Subsequence)란?

"최장 증가 부분 수열"이라고도 하며, 주어진 수열에서 엄격히 증가하는 가장 긴 부분 수열을 찾는 문제이다.

부분 수열은 원래의 수열에서 원소들의 순서를 유지하면서 일부 원소들만 선택한 수열을 의미한다.

 

예를 들어, `[1, 4, 2, 3, 1, 5, 7, 3]` 에서 LIS는 `[1, 2, 3, 5, 7]`이다.

 

동적 계획법 (Dynamic Programming) 접근

LIS는 DP를 이용하여 해결할 수 있다.

수열의 각 원소에 대해, 해당 원소보다 작은 값들로 이루어진 가장 긴 증가하는 부분 수열의 길이를 기록한다.

각 원소를 끝으로 할 때의 LIS 길이를 dp 배열에 저장하고, 이 배열에서 가장 큰 값을 LIS의 길이로 선택한다.

1. dp[i]는 수열 i번째 원소를 끝으로하는 LIS 길이를 저장
2. 초기값으로 dp[i] = 1 로 설정 (각 원소는 최소 1개의 부분 수열을 가짐)
3. i번째 원소 > j번째 원소 이면, dp[i] 는 dp[j]+1로 갱신.

 

► 예시) `arr = [1, 4, 2, 3, 1, 5, 7, 3]`의 LIS 길이 찾기

0. dp 배열 초기값 1로 설정

i	0	1	2	3	4	5	6	7
dp[i]	1	1	1	1	1	1	1	1

 

1. dp[1] 구하기

`i = 1`일 경우

`j = 0` : `arr[1] > arr[0]`를 만족. `dp[1] = dp[0] + 1 = 2`로 갱신

i	0	1	2	3	4	5	6	7
dp[i]	1	2	1	1	1	1	1	1

 

2. dp[2] 구하기

`i = 2`일 경우

`j = 0` : `arr[2] > arr[0]`를 만족. `dp[0] + 1 < dp[2]` 만족. `dp[2] = dp[0] + 1 = 2`로 갱신

`j = 1` : `arr[2] > arr[1]`를 불만족

i	0	1	2	3	4	5	6	7
dp[i]	1	2	2	1	1	1	1	1

 

3. dp[3] 구하기

`i = 3`일 경우

`j = 0` : `arr[3] > arr[0]`를 만족. `dp[0] + 1 < dp[3]` 만족. `dp[3] = dp[0] + 1 = 2`로 갱신

`j = 1` : `arr[3] > arr[1]`를 불만족

`j = 2` : `arr[3] > arr[2]`를 불만족

i	0	1	2	3	4	5	6	7
dp[i]	1	2	2	3	1	1	1	1

 

4. dp[4] 구하기

`i = 4`일 경우

`j = 0` : `arr[4] > arr[0]`를 불만족.

`j = 1` : `arr[4] > arr[1]`를 불만족.
`j = 2` : `arr[4] > arr[2]`를 불만족.
`j = 3` : `arr[4] > arr[3]`를 불만족.

i	0	1	2	3	4	5	6	7
dp[i]	1	2	2	3	1	4	5	1

 

5. dp[5] 구하기

`i = 5`일 경우

`j = 0` : `arr[5] > arr[0]`를 만족. `dp[0] + 1 < dp[5]` 만족. `dp[5] = dp[0] + 1 = 2`로 갱신

`j = 1` : `arr[5] > arr[1]`를 만족. `dp[1] + 1 < dp[5]` 만족. `dp[5] = dp[1] + 1 = 3`으로 갱신
`j = 2` : `arr[5] > arr[2]`를 만족. `dp[2] + 1 < dp[5]` 불만족.
`j = 3` : `arr[5] > arr[3]`를 만족. `dp[3] + 1 < dp[5]` 만족. `dp[5] = dp[3] + 1 = 4`로 갱신
`j = 4` : `arr[5] > arr[4]`를 만족. `dp[4] + 1 < dp[5]` 불만족.

i	0	1	2	3	4	5	6	7
dp[i]	1	2	2	3	1	4	1	1

 

6. dp[6] 구하기

`i = 6`일 경우

`j = 0` : `arr[6] > arr[0]`를 만족. `dp[0] + 1 < dp[6]` 만족. `dp[6] = dp[0] + 1 = 2`로 갱신

`j = 1` : `arr[6] > arr[1]`를 만족. `dp[1] + 1 < dp[6]` 만족. `dp[6] = dp[1] + 1 = 3`으로 갱신
`j = 2` : `arr[6] > arr[2]`를 만족. `dp[2] + 1 < dp[6]` 불만족.
`j = 3` : `arr[6] > arr[3]`를 만족. `dp[3] + 1 < dp[6]` 만족. `dp[6] = dp[3] + 1 = 4`로 갱신

`j = 4` : `arr[6] > arr[4]`를 만족. `dp[4] + 1 < dp[6]` 불만족.
`j = 5` : `arr[6] > arr[5]`를 만족. `dp[5] + 1 < dp[6]` 만족. `dp[6] = dp[5] + 1= 5`로 갱신

i	0	1	2	3	4	5	6	7
dp[i]	1	2	2	3	1	4	5	1

 

7. dp[7] 구하기

`i = 7`일 경우
`j = 0` : `arr[7] > arr[0]`를 만족. `dp[0] + 1 < dp[7]` 만족. `dp[7] = dp[0] + 1 = 2`로 갱신

`j = 1` : `arr[7] > arr[1]`를 불만족.
`j = 2` : `arr[7] > arr[2]`를 만족. `dp[2] + 1 < dp[7]` 만족. `dp[7] = dp[0] + 1 = 3`으로 갱신
`j = 3` : `arr[7] > arr[3]`를 불만족.

`j = 4` : `arr[7] > arr[4]`를 만족. `dp[4] + 1 < dp[7]` 불만족.
`j = 5` : `arr[7] > arr[5]`를 불만족.
`j = 5` : `arr[7] > arr[6]`를 불만족.

i	0	1	2	3	4	5	6	7
dp[i]	1	2	2	3	1	4	5	3

 

최종 dp 배열의 원소 중 최대 값은 5이다. LIS 길이는 5이다.

 

 

코드

import java.util.Arrays;

public class Main {
    private static int solution(int[] nums){
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1); // 최소 길이 1이므로 1로 다 채워주기
        int lis = 1; // lis 값 저장
        for(int i = 1; i < dp.length; i++){
            for(int j = 0; j < i; j++){
                // n>i && num[n]>num[i]인 값들 중 dp[n]이 가장 큰 것에 +1하여 저장.
                if(nums[j] < nums[i]){
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            lis = Math.max(lis, dp[i]); // lis 값 최장 값으로 변경
        }
        return lis;
    }

    public static void main(String[] args) {
        System.out.println("tc1 : "+solution(new int[] {1, 4, 2, 3, 1, 5, 7, 3})); //5
        System.out.println("tc2 : "+solution(new int[] {3, 2, 1})); //1
        System.out.println("tc3 : "+solution(new int[] {3, 2, 1, 3})); //2
    }
}