챕터3-12. DP | 문제 풀이3 - (1) 백준 No.11053 : 가장 긴 증가하는 부분 수열

가장 긴 증가하는 부분 수열 문제

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

문제요약

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열의 길이를 구하는 문제
부분 수열이란?  수열에서 일부를 선택한 수열이다.
ex) A = {10, 20, 10, 30, 20, 50}
      가장 긴 증가하는 부분 수열 A = {10, 20, 10, 30, 20, 50}
      => 길이는 4

해결 방법

1. D[N]에 어떤 값을 저장할 것인지 문장으로 정의해줘야한다.

다른 문제에서와 마찬가지로 D에 저장되는 값은 분할된 문제의 해답이다.

즉, D[N] 그 자체가 문제에서 원하는 최종 결과값을 의미하지 않는다.
이런 맥락에서 D[i]를 아래와 같이 정의한 뒤 이들의 최대값을 통해 문제가 원하는 해답을 구할 수 있다.

D[i] = "A[1], A[2], ... , A[i]까지 있을 때, A[i]를 마지막 원소로 포함하는 가장 긴 증가하는 부분 수열의 길이"

이제 이 정의를 이용하여 max(D[1], D[2], ,,,, D[N])을 구하면 해답을 구할 수 있는 것이다.

 

2. D[N]의 값을 어떻게하면 찾을 수 있을지 점화식을 생각한다.
- 점화식을 만들 때는 항상 이전항의 값과 연관지어 만들어야 한다. 그래야 다음항을 연달아 구할 수 있기 때문에.
- 그러면 아래와 같은 점화식이 나올 수 있다.

- D[i] = max(D[1]+1, D[2]+1, ..., D[j]+1)  (단, j < i 이며, D[1]~D[j]은 A[j] < A[i] 를 만족하는 것만 해당됨)
- (+ 1) 은 A[i]가 뒤에 무조건 붙는 것이기 때문.

 

@ 위의 점화식을 그림으로 이해하기 위한 예시

(max(D[1], D[3]) + 1의 표현은 max(D[1] + 1, D[3] + 1)과 같은것임)

@ 과정을 좀 더 쉽게 이해할 수 있도록 표로 도식화 한 예시
- 아래는 A[1]~A[6]이 주어졌을 때, 이전항들을 이용해 가장 긴 증가하는 부분 수열의 길이를 찾는 과정

혼자이므로 D[1] = 1

A[1]은 A[2]보다 작으므로 D[2] = max(D[1] + 1)를 넣어줌

A[1] ~ A[2] 모두 A[3] 보다 작거나 같으므로 혼자일 때의 값 1을 넣어줌

A[1]~A[3] 모두 A[4]보다 작으므로 D[4] = max(D[1] + 1, D[2] + 1, D[3] + 1)

A[1]~A[4] 중 A[5] 보다 작은 것은 A[1], A[3] 뿐이므로 D[5] = max(D[1] + 1, D[3] + 1)

A[1]~A[5] 중 A[6] 보다 작은 것은 A[1]~A[5] 모두 이므로 D[6] = max(D[1] + 1, D[2] + 1, D[3] + 1, D[4] + 1, D[5] + 1)

이제 D[1]~D[6] 값 중에서 가장 큰 값이 문제의 답이되는데 이땐 4이다.

 

3. 다이나믹 프로그래밍 방법을 적용할 수 있는 문제인지 확인 => 1, 2번을 거쳐야 이게 잘 보임.
- 위와 같이 큰 문제를 작은 문제로 쪼갤 수 있으며, 작은 문제도 큰 문제와 같은 방법으로 풀 수 있고, 작은 문제들이 겹친다.
   (Overlapping SubProblem)
- 문제의 정답을 작은 문제의 정답으로부터 구할 수 있으며, 문제의 크기에 상관없이 어떤 한 문제의 정답은 일정하다.
   (Optimal Substructure)

 

4. 코드구현

이 방법을 사용하면 N개의 칸을 채워야 하고, 한칸 D[i]의 값을 채울 때 A[i]번을 A[1] ~ A[i-1]번과 모두 비교하므로 
시간복잡도는 N * O(N) = O(N^2)이 된다. 따라서 이중 for문 구조가 만들어질 것이라 예상할 수 있다.

<Bottom-up 방식>

(1) 구현
-> 'for문을 이용한 반복문'으로 구현

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    
    vector<int> d(n);    
    vector<int> a(n);
    
    for (int i=0; i<n; i++)
        cin >> a[i];

    for (int i=0; i<n; i++) 
    {
        d[i] = 1;
        for (int j=0; j<i; j++) 
        {
            if (a[j] < a[i] && d[j]+1 > d[i])
                d[i] = d[j]+1;                 // A[j] < A[i]를 만족하는 d 들 중 최대값 + 1이 들어감.
        }
    }
    
    cout << *max_element(d.begin(),d.end()) << '\n';
    return 0;
}

 

(2) 시간복잡도
= for 문의 반복 횟수 

이 방법을 사용하면 N개의 칸을 채워야 하고, 한칸 D[i]의 값을 채울 때 A[i]번을 A[1] ~ A[i-1]번과 모두 비교하므로 
시간복잡도는 N * O(N) = O(N^2)이 된다.