[백준] 11053 : 가장 긴 증가하는 부분 수열 (JAVA)

난이도

🥈 2

 

링크

https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

---

문제

---

풀이과정

해당 문제는 DP 중에서 최장 증가 부분 수열 (LIS)을 사용하는 문제이다. 

LIS란 Longest Increasing Subsequence의 약자로, 말 그대로 가장 긴 증가하는 부분 수열을 의미한다. 

주어진 수열에서 오름차순으로 정렬된 가장 긴 부분 수열을 찾는 알고리즘으로, 풀이 방법은 DP를 활용하는 방법과, 이진 탐색을 활용하는 방법 2가지가 존재한다.

 

DP를 활용하는 방법의 경우 단순하지만 시간 복잡도가 O(n^2)이고, 이진 탐색을 활용하는 경우 조금 더 복잡하지만 시간 복잡도가 O(nlogn)이다.

 

이번 11053번 문제는 DP를 활용하여 문제를 풀어보았다.

 

우선 예제에서 주어진 수열은 {10, 20, 10, 30, 20, 50} 이다. 해당 수열은 seq 배열에 저장하고, dp 배열에 메모이제이션을 하였다.

seq = new int[A];
// Integer 객체를 사용한 이유는 아래에서 null을 사용하기 때문!
dp = new Integer[A];

 

 

먼저 seq[0] = 10이라는 값이 들어가 있고, 해당 값보다 이전의 값은 존재하지 않기 때문에 dp[0] = 1이 된다.

seq	10	20	10	30	20	50
dp	1

 

다음 seq[1] = 20이라는 값이 들어가 있고, seq[0] = 10보다 큰 수이기 때문에 { 10, 20 }의 부분 수열이 된다. 

현재 값인 20보다 작거나 같은 이전 원소들 중 가장 큰 dp의 값은 1이기 때문에 1+1 = 2를 현재 dp 값으로 저장한다.

seq	10	20	10	30	20	50
dp	1	2

 

seq[2] = 10이라는 값이 들어가 있고, 현재 값 10보다 작거나 같은 이전 원소들 중

가장 큰 dp의 값은 seq[0] = 10일 때의 dp[0] = 1이기 때문에 1+1 = 2를 현재 dp 값으로 저장한다.

seq	10	20	10	30	20	50
dp	1	2	2

 

seq[3] = 30이라는 값이 들어가 있고, 현재 값 30보다 작거나 같은 이전 원소들 중

가장 큰 dp의 값은 seq[1] = 20일 때의 dp[1] = 2이기 때문에 2+1 = 3를 현재 dp 값으로 저장한다. 

다음의 부분 수열은 { 10, 20, 30 }이 된다. 

seq	10	20	10	30	20	50
dp	1	2	2	3

 

seq[4] = 20이라는 값이 들어가 있고, 현재 값 20보다 작거나 같은 이전 원소들 중

가장 큰 dp의 값은 seq[1] = 20일 때의 dp[1] = 2이기 때문에 2+1 = 3를 현재 dp 값으로 저장한다. 

seq	10	20	10	30	20	50
dp	1	2	2	3	3

 

seq[5] = 50이라는 값이 들어가 있고, 현재 값 50보다 작거나 같은 이전 원소들 중

가장 큰 dp의 값은 seq[3] = 30일 때의 dp[3] = 3이기 때문에 3+1 = 4를 현재 dp 값으로 저장한다. 

해당 부분 수열은 { 10, 20, 30, 50 }이 된다. 

seq	10	20	10	30	20	50
dp	1	2	2	3	3	4

 

 

위의 예제에서 결국 가장 긴 부분 수열을 구하면 4라는 결과 값이 나오는 것을 확인할 수 있다.

---

private static int LIS(int n) {
    // 탐색하지 않은 위치의 경우 dp를 1로 초기화
    if (dp[n] == null) {
        dp[n] = 1;
		
        // n 이전의 노드들을 탐색하여 현재 값 seq[n]보다 작은 값을 발견했을 때 부분수열 길이 찾기
        for (int i = n-1; i >= 0; i--) {
            if (seq[i] < seq[n]) {
                dp[n] = Math.max(dp[n], LIS(i) + 1);
            }
        }
    }

    return dp[n];
}

 

위의 코드를 자세하게 살펴보면

우선 현재 dp[n]의 값이 null이라는 것은 아직 탐색하지 않았다는 것이기 때문에 dp[n]의 값을 1로 초기화한 후 아래의 코드를 실행시킨다. 이때 1로 초기화 하는 이유는 모든 부분수열의 길이가 최소한 1 이상이기 때문이다.

 

이후 for문을 사용하여 n-1 ~ 0까지의 노드들을 탐색하며 해당 노드의 값보다 작은 값들과의 비교를 통해 부분수열의 최대 길이를 구한다.

 

예를 들어, N=4일 때 3~0까지의 노드들을 탐색하면서 if 문에 들어가는 경우는 seq[2] = 10과 seq[0] = 10이다.

 

1) 먼저 seq[2]인 경우 dp[4]와 LIS(2)+1를 비교하여 더 큰 값을 dp[4]에 넣는다.

이때 LIS(2) 재귀호출을 하면 dp[2]를 탐색하지 않았을 경우에는 1로 초기화 되고, 1~0까지 중 작은 값들을 찾아낸다. 다음의 과정에서 seq[2] = 10보다 작은 값은 없기 때문에 dp[2] = 1이 return 된다.

 

1로 초기화된 dp[4]와 LIS(2)(=1) + 1 = 부분수열 {10, 20} = 2을 비교하였을 때 더 큰 수는 2이기 때문에 dp[4]는 2로 갱신된다. 

 

2) seq[0]인 경우에도 dp[4]와 LIS(0)+1을 비교했을때 LIS(0)의 값도 1이 나오기 때문에 결국 최대 길이는 2가 된다.

 

위와 같은 원리로 코드가 동작된다. 

---

전체 코드

import java.io.*;
import java.util.*;

public class Main {

    private static int[] seq;
    private static Integer[] dp;

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

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

        seq = new int[A];
        dp = new Integer[A];

        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < A; i++) {
            seq[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = 0; i < A; i++) {
            LIS(i);
        }

        int max = 0;

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

        System.out.println(max);
    }

    private static int LIS(int n) {
        if (dp[n] == null) {
            dp[n] = 1;

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

        return dp[n];
    }
}

 

결과