어렵다.. dp..
근데 중요한 건.. 더 어려운 놈들이..
기다리고 있다는 것... 생각보다 시간이 더 걸릴 것 같다..
그만큼 확실하게 짚고 넘어가자..!
예제2 정리 시작!
-
* 가장 긴 증가하는 부분 수열(mid): LIS라고도 불리는 유명한 문제다. 기억해뒀다가 필요할 때 써먹자.
11053번: 가장 긴 증가하는 부분 수열
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이
www.acmicpc.net
|
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
|
#include <iostream>
using namespace std;
int a[1001], d[1001];
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
d[i] = 1;
}
int lis = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j < i; j++) {
if (a[i] > a[j] && d[i] < d[j] + 1) {
d[i] = d[j] + 1;
}
}
if (lis < d[i]) lis = d[i];
}
cout << lis << '\n';
return 0;
}
|
cs |
- 14: 모든 d를 1로 초기화 한다. 뒤에 증가하는 수가 없더라도 자기 혼자 수열일 가능성은 다 있으니까.
- 20: i번째 수가 j번째에서 이어지는 증가 수열인지 확인하고 i번째에 +1 해준다.
- 24: 최댓값을 조사한다.
* 가장 긴 증가하는 부분 수열 4 (mid) : LIS를 직접 출력하는 것이 추가 되었다.
14002번: 가장 긴 증가하는 부분 수열 4
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이
www.acmicpc.net
|
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
#include <iostream>
#include <stack>
using namespace std;
int a[1001], d[1001], v[1001];
stack<int> s;
/*
void show(int x)
{
if (x == -1)
return;
show(v[x]);
cout << a[x] << ' ';
}
*/
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
d[i] = 1;
}
int lis = 1, ldx;
v[1] = -1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j < i; j++) {
if (a[i] > a[j] && d[i] < d[j] + 1) {
d[i] = d[j] + 1;
v[i] = j;
}
}
if (lis < d[i]) {
lis = d[i];
ldx = i;
}
}
cout << lis << '\n';
for (int i = n; i >= 1; i--) {
if (d[i] == lis) {
s.push(a[i]);
lis -= 1;
}
}
while (!s.empty()) {
cout << s.top() << ' ';
s.pop();
}
return 0;
}
|
cs |
- 6 : 이전 인덱스를 저장하는 v 배열을 추가했다.
- 37 : LIS의 길이를 사용해 뒤에서부터 순서대로 스택에 담고, pop 해주면 된다.
=> v를 사용해서 역추적 하는 함수를 사용하는 것이 모범 답안이었으나, 온라인 저지에서 시간초과가 떠서 스택으로 구현했다. (오히려 스택이 더 편한 것 같다) show의 인수에는 42에서 구한 lis 길이의 인덱스 값을 넣어주면 된다.
* 연속합 (high) : 연속된 수의 합 중 가장 큰 합을 구하는 문제다.
1912번: 연속합
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
www.acmicpc.net
- 일차원 배열 a에 수를 저장하고 d[i]를 i번째까지 합의 최댓값이라고 생각하면, d[i]에 들어갈 수 있는 수는 2가지로 생각할 수 있다.
- d[i-1]+a[i] > a[i] : i-1번째까지 합의 최댓값에 i번째 수를 더하는 것이 i번째부터 더하기 시작하는 것보다 더 클 때, 큰 놈이 d[i]에 들어간다. i부터 시작하는 게 더 크다면 a[i]를 그대로 넣어주면 되겠다.
|
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
|
#include <iostream>
using namespace std;
int a[100001], d[100001];
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
d[1] = a[1];
int dmax = d[1];
for (int i = 2; i <= n; i++) {
d[i] = a[i];
if (d[i - 1] + a[i] > a[i]) {
d[i] = d[i - 1] + a[i];
}
if (dmax < d[i]) dmax = d[i];
}
cout << dmax << '\n';
return 0;
}
|
cs |
* 제곱수의 합 (mid) : 입력 받은 자연수를 최소 몇개의 제곱수 합으로 나타낼 수 있는지 구하는 문제다.
1699번: 제곱수의 합
어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다
www.acmicpc.net
- d[i]를 i가 나타낼 수 있는 제곱수의 최솟값이라고 생각해보자. 늘 그랬듯이 마지막에 어떤 것이 더해질지 생각하면 해결책이 보인다.
- 1^2, 2^2, 3^2, ... 어떤 제곱수가 마지막에 더해졌는지 모르니 j^2이라고 두고 점화식을 세워보면,
- d[i] = d[i-j^2] + 1 로 나타낼 수 있다. 1이 더해진 이유는, 하나의 제곱수가 마지막에 더해졌기 때문이다.
- i-j^2 >= 0 이라는 조건도 알 수 있는데, 이를 코딩할 때 활용하면 반복문 횟수를 줄일 수 있다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
#include <iostream>
using namespace std;
int d[100001];
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
d[i] = i;
for (int j = 1; j*j <= i; j++) {
if (d[i] > d[i - j*j] + 1)
d[i] = d[i - j*j] + 1;
}
}
cout << d[n] << '\n';
return 0;
}
|
cs |
=> 내가 짠 코드가 너무 지저분 해서 모범 답안을 참고해서 풀어봤다.
- 13 : d[i]는 아무리 커도 i를 못 넘는다. 1^2로 i번 더하는 게 최대이기 때문이다.
- 14 : 아까 언급한 i - j^2 >= 0 를 활용했다.
* 합분해 (high) : 0부터 n까지의 정수 k개를 더해서 그 합이 n이 되는 경우의 수를 구하는 문제다. 헤맸다
2225번: 합분해
첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.
www.acmicpc.net
- 진짜 조건 그대로 식을 세우면 된다. 0부터 n까지의 정수 k개를 더한 값 -> d[k][n]으로 생각하면 된다. 이 말을 하면서 백준 님이 이번 강의 문제까지는 조건만으로 점화식을 세울 수 있어서 쉽다고 했는데 살짝 자괴감이 왔다..
- d[k][n]을 0부터 n까지의 값을 k개 더해서 n을 만드는 경우의 수라고 생각하고 점화식을 세우면,
- d[k][n] = ∑ d[k-1][n-l] : 맨 뒤에 더해진 값을 l이라고 생각하면, 0부터 n-l까지의 값을 k-1개 더해서 n-l를 만드는 경우를.. l이 0일 때부터 n일 때까지 다 더해보면 된다.
|
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
|
#include <iostream>
using namespace std;
long long d[201][201];
const long long mod = 1000000000;
int main()
{
int n, k;
cin >> n >> k;
d[0][0] = 1;
for (int i = 1; i <= k; i++) {
for (int j = 0; j <= n; j++) {
for (int l = 0; l <= j; l++) {
d[i][j] += d[i - 1][j - l];
}
d[i][j] %= mod;
}
}
cout << d[k][n] % mod << '\n';
return 0;
}
|
cs |
- 13 : 0까지의 정수 0개를 써서 0을 만드는 방법이 하나라고 생각하면 되겠다.
-
dp는 문제를 쪼개는 재미가 있는 것 같다. 물론 풀려야 재밌다.
고민하는 시간이 길어져 진도가 좀 더딘 것 같은데, 늦더라도 차근차근 잘근잘근 씹으면서 따라가자.
다음 단원, 그 다음 단원도 문제 풀이 강의다. 그만큼 문제 풀이 능력이 중요한 챕터인듯 하다.
계속 풀어보자!
'알고리즘 > 백준 알고리즘 강의' 카테고리의 다른 글
| 백준 알고리즘 기초 - 다이나믹 프로그래밍 (도전) (0) | 2020.07.12 |
|---|---|
| 백준 알고리즘 기초 - 다이나믹 프로그래밍 (연습) (0) | 2020.07.11 |
| 백준 알고리즘 기초 - 다이나믹 프로그래밍 (예제1) (0) | 2020.07.09 |
| 백준 알고리즘 기초 - 다이나믹 프로그래밍 1 + 기초 예제 (0) | 2020.07.08 |
| 백준 알고리즘 기초 - 수학1 (연습) (0) | 2020.07.07 |
