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

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

# 문제

 

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

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

 

# 입력

 

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

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

 

# 출력

 

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

 

# 예시 입력

6
10 20 10 30 20 50

# 예시 출력

4

---

동적 프로그래밍 문제라고 한다. 문제를 보고 '이게 왜 동적 프로그래밍 문제이고, DP 문제라면 어떻게 점화식을 세우고 어떤 값을 어떻게 저장해야 할까???' 하는 생각이 들었다. 총체적 난국이었던 것 이다. 아직 코린이였던 나에게 생소한 문제였던 것 같다. 일단 부분 수열이라는 단어의 정의조차 모호해서 검색해보았다. 내가 예상 한 것은 수학에 중점을 갖춘 설명이었는데, 대부분 프로그래밍 문제를 다루는 포스팅이었다. 어쨌든 나무위키, 타 블로그 등을 보며 코드는 일절 보지 않고 문제를 해결하기 위한 방법만 빠르게 습득했다. 나에게 생소했던 만큼 어려웠다... 문제 해결 법을 깨닫고 난 뒤에 이 문제가 부분 수열 문제에서 그나마 쉽게 나온 문제인 것 같았다.

 

부분 수열 문제를 동적 프로그래밍으로 해결하기 위해 크게 두 가지 방법이 존재한다고 한다.

 

1) O(N^2) 방법

2) O(Nlog N) 방법

 

O(N^2)는 n회 반복하는 루프 안에 1부터 n-1까지 반복하는 루프가 있는 이중 루프 구조 인 것 같다. 가물가물 하지만 버블정렬인가...삽입정렬인가 아무튼 그런 구조로 비교적 간단하게 구현할 수 있는 코드라고 생각한다. 간단하게 구현할 수 있는 만큼 소모되는 리소스도 크므로 새롭게 터득도 해볼 겸 O(Nlog N) 방법으로 해보기로 했다. (사실 풀고나니까 시간 복잡도가 O(Nlog N)이 나왔는지 모르겠다..) 아래는 O(Nlog N) 방법으로 문제를 해결해나가는 과정을 예시로 들어본다.

 

# O(Nlog N) 방법

O(Nlog N) 알고리즘은 O(N^2)을 개량한 형태이다. 이 알고리즘은 다음과 같은 의문에서 시작한다. result[i]를 계산하기 위해 꼭 arr[1]~arr[i]를 다 순회해야 하는가? O(N^2) 알고리즘에서는 arr의 내부를 전체 다 훑어보는데, 이는 arr[i]보다 작은 arr[j]를 가지는 j들 중에서 가장 큰 result[j]를 찾기 위함이다. (단, i > j) 만약 result[j] = k를 만족하는 j 중 arr[j]의 값이 가장 작은 j만 어딘가에 저장해둔다면, 나중에 result[i]를 계산할 떄 그 값들만 참조하면 result[i]의 값을 쉽게 알 수 있다.

 

idx	1	2	3	4	5	6	7
arr	3	1	2	7	8	2	10
result(=dp)	1

X = [3]

 

위 표와 같이 7개의 숫자가 arr이라는 배열에 담겨있다고 하자. result 배열은 result[i]가 가질 수 있는 증가하는 부분 수열 길이의 최대 값이다. result[1]은 시작 점이므로 1이다. 그리고 O(N^2)의 방법으로 풀 때는 요구되지 않았던 배열 하나가 더 필요하다. 그 배열을 X[]라고 한다. 이 배열은 result[i] = k인 값들 중 arr[i]의 값이 가장 작은 값을 계속 업데이트 한다.

---

* idx = 2

idx가 하나씩 증가할 때 마다, arr[idx]를 항상 비교할 것 이다. 누구랑 비교하는가? 바로 X[]안에 있는 값들과 비교를 할 것이다.

arr[2]와 X[1]=3을 비교하면, 1 < 3이므로 result[2] = 1 이고, X[1]=3은 arr[2]=1 보다 작으므로 X[1]=arr[2]로 수정한다. 즉 X[1] = 1

 

idx	1	2	3	4	5	6	7
arr	3	1	2	7	8	2	10
result(=dp)	1	1

X = [1]

---

* idx = 3

arr[3]=2를 다시 X배열의 값들과 비교한다. arr[3]=2과 X[1]=1을 비교하면 arr[3] > X[1] 이므로 result[3] = 1+1이다. 그리고 X[1+1]의 값이 비어있으므로(0이므로) X[1+1]=arr[3] 으로 지정한다. 혹시 눈치가 빠른 분들은 조금 눈치챘을지도 모른다. 점화식이라던지 슈도코드라던지 머리 속에 살짝 그려졌을 수도 있다. 그렇지 않아도 상관없다 ^^

 

idx	1	2	3	4	5	6	7
arr	3	1	2	7	8	2	10
result(=dp)	1	1	(1+1) = 2

X = [1, 2]

---

* idx = 4

arr[4]=7을 X의 배열 값들과 비교한다. 현재 X=[1, 2]가 들어있다.

arr[4] = 7 > 1 이므로 result[4] = 1 + 1

arr[4] = 7 > 2 이므로 result[4] = 2 + 1, X[2+1] == 0 이니까 무엇을 해야하는가? X[2+1] = arr[4]을 지정해야 한다.

 

idx	1	2	3	4	5	6	7
arr	3	1	2	7	8	2	10
result(=dp)	1	1	2	(2+1) = 3

X = [1, 2, 7]

---

* idx = 5

arr[5]=7을 X의 배열 값들과 비교한다. 현재 X=[1, 2, 7]가 들어있다.

arr[5] = 8 > 1 이므로 result[5] = 1 + 1

arr[5] = 8 > 2 이므로 result[5] = 2 + 1

arr[5] = 8 > 7 이므로 result[5] = 3 + 1, X[3+1] == 0 이니 역시나 X[3+1] = arr[5]을 지정해야 한다.

 

idx	1	2	3	4	5	6	7
arr	3	1	2	7	8	2	10
result(=dp)	1	1	2	3	(3+1) = 4

X = [1, 2, 7, 8]

---

* idx = 6

arr[6]=2을 X의 배열 값들과 비교한다. 현재 X=[1, 2, 7, 8]가 들어있다.

arr[6] = 2 > 1 이므로 result[6] = 1 + 1

arr[6] = 2 == 2 이므로 result[5] = 2, 이제 idx = 6에서는 더이상 X의 값들과 비교할 필요가 없다. 따라서 다음 인덱스로 넘어가도록 한다.

 

idx	1	2	3	4	5	6	7
arr	3	1	2	7	8	2	10
result(=dp)	1	1	2	3	4	2

X = [1, 2, 7, 8]

---

* idx = 7

arr[7]=10을 X의 배열 값들과 비교한다. 현재 X=[1, 2, 7, 8]가 들어있다.

arr[7] = 10 > 1 이므로 result[7] = 1 + 1

arr[7] = 10 > 2 이므로 result[7] = 2 + 1

arr[7] = 10 > 7 이므로 result[7] = 3 + 1

arr[7] = 10 > 8 이므로 result[7] = 4 + 1, X[4+1] == 0 이므로 X[4+1] = 10

 

idx	1	2	3	4	5	6	7
arr	3	1	2	7	8	2	10
result(=dp)	1	1	2	3	4	2	(4+1)=5

X = [1, 2, 7, 8, 10]

---

이로써 모든 작업이 완료되었다. 이 예시의 답은 5 가 되겠다. X 배열은 항상 오름차순으로 정렬되어있어 이진 탐색이 가능하다. 나중에 다른 문제에 요긴하게 쓰일 곳이 있을 것 같다.

 

이 알고리즘은 3가지 케이스만 고려하면 된다.

 

for i=2 -> x then

    for j=1, X[j] != 0, j++ then

 

case 1: arr[i] == X[j]

- result[i] = j

- 더 이상 X를 순회 할 필요가 없으므로 break;

 

case 2: arr[i] < X[j]

- result[i] = j

- X[j]의 값보다 더 작은 arr[i]로 대체 (X[j] = arr[i])

- 더 이상 X를 순회할 필요가 없으므로 break;

 

case 3: arr[i] > X[j]

- result[i] = j + 1

- 만약 X[j+1] == 0 then X[j+1] = arr[i]

---

# Whole Code </> - Java 11

public class Main {

    static int[] arr = new int[1001];

    static int getAnswer(int x){

        int[] result = new int[x+1];
        int[] X = new int[x+1];
        int maxIdx = 1;

        result[1] = 1;
        X[1] = arr[1];

        for(int i=2; i<=x; i++)
            for(int j=1; X[j] != 0; j++)
                //case 1: arr[i] == X[j]
                if(arr[i] == X[j]){
                
                    result[i] = j;
                    break;
                }
                //case 2: arr[i] < X[j]
                else if(arr[i] < X[j]){
                
                    result[i] = j;
                    X[j] = arr[i];
                    break;
                }
                //case 3: arr[i] > X[j]
                else{
                    result[i] = j + 1;
                    
                    if(X[j+1] == 0) {
                    
                        X[j + 1] = arr[i];
                        maxIdx = j + 1;
                    }
                }
/*
        Arrays.stream(result).forEach(a -> {
            if(a != 0)
                System.out.println(a);
        });
        
        System.out.println("==================");
        
        Arrays.stream(X).forEach(a -> {
            if(a != 0)
                System.out.println(a);
        });
*/
        return maxIdx;
    }
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int x = sc.nextInt();
        if(x < 1 || x > 1000) System.exit(0);
        
        for(int i=1; i<=x; i++){
            arr[i] = sc.nextInt();
            
            if(arr[i] < 1 || arr[i] > 1000) System.exit(0);
        }

        System.out.printf("%d\n", getAnswer(x));
        sc.close();
    }
}