일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
- iOS14
- Django란
- 입출력 패턴
- Django의 편의성
- EOF
- 입/출력
- 표준 입출력
- 엑셀
- c++
- 자료구조
- UI한글변경
- scanf
- correlation coefficient
- string 메소드
- 구조체와 클래스의 공통점 및 차이점
- 연결요소
- 시간복잡도
- vscode
- Django Nodejs 차이점
- 장고란
- 이분그래프
- 백준
- 매크로
- 프레임워크와 라이브러리의 차이
- 2557
- string 함수
- getline
- k-eta
- double ended queue
- 알고리즘 공부방법
- Today
- Total
Storage Gonie
챕터3-13. DP | 문제 풀이3 - (2) 백준 No.11055 : 가장 큰 증가 부분 수열 본문
챕터3-13. DP | 문제 풀이3 - (2) 백준 No.11055 : 가장 큰 증가 부분 수열
Storage Gonie 2019. 5. 15. 19:10가장 큰 증가 부분 수열 문제
- https://www.acmicpc.net/problem/11055
문제요약
수열 A가 주어졌을 때 증가 부분 수열 중에서 가장 수열의 합이 큰 것을 구하는 문제
부분 수열이란? 수열에서 일부를 선택한 수열이다.
ex) A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8}
합이 가장 큰 증가 부분 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8}
=> 총 합은 1 + 2 + 50 + 60 = 113
해결 방법
* 바로 이전 문제를 조금 수정해서 풀 수 있다.
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], D[2], ..., D[j]) + A[i] (단, j < i 이며, D[1]~D[j]은 A[j] < A[i] 를 만족하는 것만 해당됨)
@ 과정을 좀 더 쉽게 이해할 수 있도록 표로 도식화 한 예시
이제 D[1]~D[10] 값 중에서 가장 큰 값이 문제의 답이되는데 이땐 113이다.
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] = a[i];
for (int j=0; j<i; j++)
{
if (a[j] < a[i] && d[j]+a[i] > d[i])
d[i] = d[j]+a[i]; // A[j] < A[i]를 만족하는 d 들 중 최대값 + a[i]이 들어감.
}
}
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)이 된다.
'알고리즘 > 알고리즘 기초(코드플러스)' 카테고리의 다른 글
챕터3-15. DP | 문제 풀이3 - (4) 백준 No.11054 : 가장 긴 바이토닉 부분 수열 (0) | 2019.05.15 |
---|---|
챕터3-14. DP | 문제 풀이3 - (3) 백준 No.11722 : 가장 긴 감소하는 부분 수열 (0) | 2019.05.15 |
챕터3-12. DP | 문제 풀이3 - (1) 백준 No.11053 : 가장 긴 증가하는 부분 수열 (0) | 2019.05.15 |
챕터3-11. DP | 문제 풀이2 - (5) 백준 No.2156 : 포도주 시식 (0) | 2019.05.09 |
챕터3-10. DP | 문제 풀이2 - (4) 백준 No.9465 : 스티커 (0) | 2019.05.09 |