[99클럽 코테스터디 22일차 TIL / 백준] 11053 - 가장 긴 증가하는 부분 수열(DP)

99클럽 코테스터디 22일차 TIL
KeyWord : 동적프로그래밍(DP)

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 $A_i$가 주어진다. (1 ≤ $A_i$ ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

---

 

풀이

 

메모제이션 기법으로 해결할 수 있는 문제이다.

일단, 수열 {1, 2}와 수열 {4, 3, 6, 10, 32, 13, 10, 4} 중 어떤 수열에서 문제의 해를 구하기 쉬울까?

당연히 길이가 짧은 수열 {1, 2}이다. 즉, 수열의 길이가 짧을 수록 연산량은 줄어들고, 해를 구하기 쉬워진다.

이 생각을 가지고 문제에서 주어진 수열 A = {10, 20, 10, 30, 20, 50}를 예시로 들어 생각해보자.

먼저, A의 부분 수열 {10, 20, 10, 30, 20}을 A-1이라고 하자.

수열 A-1의 가장 긴 증가하는 부분수열은 {10, 20, 10, 30, 20}이다.
수열 A의 가장 긴 증가하는 부분수열은 A = {10, 20, 10, 30, 20, 50}이다.

즉, 수열 A의 가장 긴 증가하는 부분 수열의 길이는 수열 A의 부분 수열 A-1의 가장 긴 증가하는 부분 수열에 50을 추가했을 때의 길이와 같다.

이러한 방식을 이용해서 수열의 길이를 줄여보자.

• A-1 = {10, 20, 10, 30, 20}
• A-2 = {10, 20, 10, 30}
• A-3 = {10, 20, 10}
• A-4 = {10, 20}
• A-5 = {10}

결국, 수열의 길이가 1이 될때까지 부분수열을 만들었다.

여기서 길이가 1인 수열 A-5의 가장 긴 부분수열의 길이는 얼마일까? 당연히 1이다.

그렇다면 A-4는? 2가 된다. A-5에서 만들어진 가장 긴 부분수열에 20을 추가했을 때 가장 긴 부분수열이 변화하는지를 살펴보면 된다.

A-3일 때는? 마지막 원소인 10은, 선행 원소인 20보다 작으므로 가장 긴 부분수열은 변화하지 않는다. 즉, A-3의 가장 긴 증가하는 부분수열의 길이는 2.

이러한 규칙대로 A까지 나아가면 해를 구할 수 있게 된다.

 

오케이. 여기까지는 이해됐다. 그런데 이걸 어떻게 코드로 구현해야 할까?

맨 처음에 이야기한 대로 이 문제는 dp를 이용한 메모제이션 기법으로 해결할 수 있다.

dp[] 배열을 만들고, 이 배열에 각 부분 수열에서 만들어지는 가장 긴 증가하는 부분수열의 길이를 메모제이션할 것이다.

• A[0] = 10 → dp[0] = 1
• A[1] = 20 → dp[1] = 2
• A[2] = 10 → dp[2] = 2
• A[3] = 30 → dp[2] = 3
• A[4] = 20 → dp[2] = 3
• A[5] = 50 → dp[2] = 4

이제 이것을 코드로 구현하면, 아래와 같이 된다.

for (int i = 1; i < N; i++) {  
    for (int j = 0; j < i; j++) {  
        if (A[i] > A[j]) {  
            dp[i] = Math.max(dp[i], dp[j] + 1);  
        }
    }
}

 

코드

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.Arrays;  
import java.util.StringTokenizer;  

public class Main {  
    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  

        int N = Integer.parseInt(br.readLine());  

        StringTokenizer stk = new StringTokenizer(br.readLine());  
        int[] A = new int[N];  
        for (int i = 0; i < N; i++) {  
            A[i] = Integer.parseInt(stk.nextToken());  
        }  

        int[] dp = new int[N]; // 현재 인덱스 기준 가장 긴 증가하는 부분 수열의 길이  
        Arrays.fill(dp, 1);  

        int answer = 1;  
        for (int i = 1; i < N; i++) {  
            for (int j = 0; j < i; j++) {  
                if (A[i] > A[j]) {  
                    dp[i] = Math.max(dp[i], dp[j] + 1);  
                }
            }  
            answer = Math.max(answer, dp[i]);  
        }  

        System.out.println(answer);  
    }  
}

 

---

 

여담 : dp인데도 시간 복잡도가 $O(N^2)$?

이 문제의 경우에는 N의 최댓값이 1,000이기에 $O(N^2)$ 알고리즘으로도 통과가 되었다. 하지만 N의 범위가 이것보다 더 컸다면 시간초과로 실패할 것이다.

실제로 가장 긴 증가하는 부분 수열2 문제에서는 이것과 같은 방식으로 진행하면 시간초과로 실패한다고 한다.

여기서 등장하는 아이디어가 이분탐색이다.

생각해보면 당연하게도, 가장 긴 증가하는 부분수열은 이미 정렬된 상태이다. 즉, 이분탐색이 가능하다!

for (int j = 0; j < i; j++) {  
    if (A[i] > A[j])
        ...
}

즉 이 부분을 완전탐색이 아니라, 이분탐색을 적용하면 효율성을 챙길 수 있다.

관련된 코드는 다음에 가장 긴 증가하는 부분 수열2에서 풀이해보도록 하겠다.