챕터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]가 뒤에 무조건 붙는 것이기 때문.
@ 위의 점화식을 그림으로 이해하기 위한 예시
@ 과정을 좀 더 쉽게 이해할 수 있도록 표로 도식화 한 예시
- 아래는 A[1]~A[6]이 주어졌을 때, 이전항들을 이용해 가장 긴 증가하는 부분 수열의 길이를 찾는 과정
이제 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)이 된다.