[BEAKJOON] 14002 - 가장 긴 증가하는 부분 수열 4

이번 포스트에서 다뤄볼 문제는 Beakjoon online judge 사이트에 있는 14002번 문제 '가장 긴 증가하는 부분 수열 4' 이다.

이 문제는 LIS 로 알려진 유명한 문제이다.

 

---

이 문제를 풀기 위해 이용한 알고리즘은 DP 이다.

물론, 2중 for 문을 이용해서 전체를 계속 순회해도 문제를 풀 수 있다. 특히 이 문제에서는 크기가 1000 이므로,

O(n^2) 이다. 따라서 충분히 시간 내에 풀 수 있다. 하지만 DP 를 이용한다면, O(n) 으로 계산 할 수 있다.

 

DP 문제는 다들 많이 풀어보는 유형이라 방법은 알고 있겠지만, 모르는 분들에게 도움이 되고자 설명한다.

 

dp 배열을 수열 길이만큼 잡은 후, 0 으로 초기화 해준다.

여기서 C 언어를 사용하고 있다면, 전역변수로 선언하면 0 으로 자동 초기화 된다. (Tip)

 

위에 예시를 들어 생각해보자.

 A  = { 10, 20, 10, 30, 20, 50 }

dp = {  0 ,  0,   0,   0,   0,   0 }

일 때,

'가장 길게 증가하는 부분 수열' 를 우선 LIS 라고 부르자. 너무 길기 때문에

A[0] ~ A[5] 까지의 LIS은 { 10, 20, 30, 50 } 이다.

A[0] ~ A[4] 까지의 LIS은 { 10, 20, 30 } 이다.

A[0] ~ A[3] 까지의 LIS은 { 10, 20 } , { 10, 30 } , { 20 , 30 }  세가지가 가능하다. 

 

이렇게 구해진 LIS 를 보면, 이전에 구한 값들이 사용되는 것을 확인 할 수 있다. 

즉, 한번 구해야할 것을 한번만 구하고 저장해서 다음에 재사용하는 방법을 DP 라고 한다.

 

dp[i] 를 A[i] 를 포함 했을 때, 가장 긴 부분 수열의 길이라고 하자.

 

dp[i] 를 구하기 위해서는 dp[0] 부터 dp[i - 1] 까지의 값을 이용해야 한다.

A[i] 보다 작은 A[k] ( k 는 0 부터 i - 1 사이의 값 ) 들 중, dp[k] 가 가장 큰 값에 +1 을 한 값이 dp[i] 가 된다.

 

이렇게 주어진 A 배열을 모두 돌았을 때, dp 배열에 있는 값 중 가장 큰 값이 A 배열의 LIS 길이 이다.

 

하지만, 우리가 구해야 하는 것을 LIS 의 길이와 LIS 그 자체를 구하는 것이다.

 

LIS 를 구하는 방법 또한 DP 를 이용해서 배열의 값으로 배열을 넣어서 누적하면 되지 않을까 생각할 수 도 있으나, 이렇게 되면 메모리를 비효율적으로 가져가게 된다.

i	0	1	2	3	4	5
A[i]	10	20	10	30	20	50
dp[i]	1	2	1	3	2	4
LIS[i]	{10}	{10,20}	{10}	{10,20,30}	{10,20}	{10,20,30,50}

물론 이렇게도 구할 수 있다. 하지만 이렇게 된다면, LIS 의 요소로 배열을 가져야 하므로, LIS 는 2차원 배열이고, 그 크기는 n^2 이 된다.

그렇다면 어떻게 LIS 를 구할 수 있을까?

 

dp[i] 가 갱신될 때, 이용된 누적 값 dp[k] 에서 k 를 기억하고 있으면 된다.

i	0	1	2	3	4	5
backTracking[i]	0	0	2	1	0 ( 또는 2 )	3

이다. dp 중 가장 큰 값은 dp[5] 이다. 그렇다면, LIS 로 "10 20 30 50"  를 출력해야 하므로, backTracking 하면서 값들을 stack 에 넣은 후, 다시 꺼내면 된다. 

그 과정을 설명하면 다음과 같다.

dp[5] : max

stack.push(A[5])

backTracking[5] : 3

stack.push(A[3])

backTracking[3] : 1

stack.push(A[1])

backTracking[1] : 0

stack.push(A[0])

backTracking[0] : 0 ->  종료



while (stack.size != 0)

    print stack.pop()

 

---

 

코드를 보려면 더보기를 눌르면 됩니다.

#include <stdio.h>
#include <stack>
#define MAX 1000

using namespace std;

void solution(int* arr, int n);

int main(int argc, char const *argv[])
{
    int n;
    int arr[MAX];
 
    scanf("%d", &n);

    for (int i = 0; i < n; i++) 
        scanf("%d", &arr[i]);
        
    solution(arr, n);

    return 0;
}

void solution(int* arr, int n) {
    int dp[MAX];
    int backTracking[MAX];
    int max = -1;

    for (int i = 0; i < n; i++) {
        dp[i] = 1;
        backTracking[i] = i;
    }

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

    printf("%d\n", max);
    stack<int> s;
    while (maxIdx != backTracking[maxIdx]) {
        s.push(arr[maxIdx]);
        maxIdx = backTracking[maxIdx];
    }
    s.push(arr[maxIdx]);

    while (!s.empty()) {
        printf("%d ", s.top());
        s.pop();
    }
    printf("\n");
}

 

연습하면 쉬운 문제이지만, 처음 이 유형의 문제를 봤을 때는 정말 어려웠다. 이 문제를 풀면서 어려움을 겪는 사람에게 도움이 됐으면 한다.