2022. 2. 23. 15:41ㆍAlgorithm/7강
1. 알고리즘 설명
다이나믹 프로그래밍(Dynamic Programming, DP) - 여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘
문제를 해결하기 위한 점화식을 찾아낸 후 점화식의 항을 밑에서부터 차례로 구해나가서 답을 알아내는 형태의 알고리즘이다.
dp를 푸는 과정
1. 테이블 정의하기
2. 점화식 찾기
3. 초기값 정하기
2. 연습 문제
1463번: 1로 만들기
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
www.acmicpc.net
1. 테이블 정의하기
d[i] = i를 1로 만들기 위해 필요한 연산 사용 횟수의 최솟값
2. 점화식 찾기
d[12] = ?
3으로 나누거나 (d[12] = d[4] + 1)
2로 나누거나 (d[12] = d[6] + 1)
1을 빼거나 (d[12] = d[11] + 1)
-> d[12] = min(d[4] + 1, d[6] + 1, d[11] + 1)
3. 초기값 정하기
d[1] = 0
#include <bits/stdc++.h>
using namespace std;
int dist[10000000];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int n;
cin >> n;
dist[0] = 0;
dist[1] = 0;
for (int i = 2;i<=n;i++){
dist[i] = dist[i-1] + 1;
if (i%3 == 0){
dist[i] = min(dist[i], dist[i/3]+1);
}
if (i%2 == 0){
dist[i] = min(dist[i], dist[i/2] + 1);
}
}
cout << dist[n];
return 0;
}
9095번: 1, 2, 3 더하기
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.
www.acmicpc.net
1. 테이블 정의하기
d[i] = i를 1,23의 합으로 나타내는 방법의 수
2. 점화식 찾기
d[4] = ?
1+1+1+1, 3+1, 2+1+1, 1+2+1, (3을 1,2,3의 합으로 나타내는 방법) + 1, d[3]
1+1+2, 2+2, (2를 1,2,3의 합으로 나타내는 방법) +2, d[2]
1+3 (1을 1,2,3의 합으로 나타내는 방법) +3, d[1]
d[4] = d[1] + d[2] + d[3]
3. 초기값 정하기
d[1] = 1, d[2] = 2, d[3] = 4
d[i] = d[i-1] + d[i-2] + d[i-3]이니 초기값이 최소 3개는 주어져야 한다.
#include <bits/stdc++.h>
using namespace std;
int d[100000];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t, n;
d[0] = 0;
d[1] = 1;
d[2] = 2;
d[3] = 4;
for (int j = 4; j < 11; j++)
{
d[j] = d[j - 1] + d[j - 2] + d[j - 3];
}
cin >> t;
for (int i = 0; i < t; i++)
{
cin >> n;
cout << d[n] << '\n';
}
return 0;
}
2579번: 계단 오르기
계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점
www.acmicpc.net
1. 테이블 정의하기
d[i] = i번째 계단까지 올라섰을 때 점수 합의 최댓값
d[i][j] = 현재까지 j개의 계단을 연속해서 밟고 i번째 계단까지 올라섰을 때 점수 합의 최댓값, 단 i번째 계단은 반드시 밟아야 함.
2. 점화식 찾기
d[k][1] = max(d[k-2][1]], d[k-2][2]) + s[k]
d[k][2] = d[k-1][1] + s[k]
3. 초기값 정하기
d[1][1] = s[1], d[1][2] = 0,
d[2][1] = s[2], d[2][2] = s[1] + s[2]
#include <bits/stdc++.h>
using namespace std;
int d[302][2];
int stair[302];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int n;
cin >> n;
for (int i = 0;i<n;i++){
cin >> stair[i];
}
if (n==1){
cout << stair[0];
return 0;
}
d[0][0] = stair[0];
d[0][1] = 0;
d[1][0] = stair[1];
d[1][1] = stair[0] + stair[1];
for (int i = 2;i<n;i++){
d[i][0] = max(d[i-2][0], d[i-2][1]) + stair[i];
d[i][1] = d[i-1][0] + stair[i];
}
cout << max(d[n-1][0], d[n-1][1]);
return 0;
}
2579_v2
1. 테이블 정의하기
d[i] = i번째 계단까지 올라섰을 때 밟지 않을 계단의 합의 최솟값, 단 i번째 계단은 반드시 밟지 않을 계단으로 선택해야 함.
2. 점화식 찾기
| 1 | 2 | 3 | 4 | 5 |
| 10 | 20 | 15 | 35 | 25 |
d[k] = min(d[k-2], d[k-3]) + s[k]
3. 초기값 정하기
d[1] = s[1], d[2] = s[2], d[3] = s[3]
#include <bits/stdc++.h>
using namespace std;
int d[302];
int stair[302];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int n;
cin >> n;
int ans = 0;
for (int i = 0;i<n;i++){
cin >> stair[i];
ans += stair[i];
}
if (n <= 2){
cout << ans;
return 0;
}
d[0] = stair[0];
d[1] = stair[1];
d[2] = stair[2];
for (int i = 3;i<n;i++){
d[i] = min(d[i-2], d[i-3]) + stair[i];
}
cout << ans - min(d[n-2], d[n-3]);
return 0;
}
1149번: RGB거리
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나
www.acmicpc.net
1. 테이블 정의하기
d[i][0] = i번째 집까지 칠할 때 비용의 최솟값, 단 i번째 집은 빨강
d[i][1] = i번째 집까지 칠할 때 비용의 최솟값, 단 i번째 집은 초록
d[i][2] = i번째 집까지 칠할 때 비용의 최솟값, 단 i번째 집은 파랑
2. 점화식 찾기
d[i][0] = min(d[k-1][1], d[k-1][2]) + r[k]
d[i][1] = min(d[k-1][0], d[k-1][2]) + g[k]
d[i][2] = min(d[k-1][0], d[k-1][2]) + b[k]
3. 초기값 정하기
d[1][0] = r[1]
d[1][1] = g[1]
d[1][2] = b[1]
#include <bits/stdc++.h>
using namespace std;
int d[1002][3];
int r[1002], g[1002], b[1002];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin >> n;
for (int i = 0; i<n;i++){
cin >> r[i] >> g[i] >> b[i];
}
d[0][0] = r[0];
d[0][1] = g[0];
d[0][2] = b[0];
for (int i = 1; i < n; i++)
{
d[i][0] = min(d[i - 1][1], d[i - 1][2]) + r[i];
d[i][1] = min(d[i - 1][0], d[i - 1][2]) + g[i];
d[i][2] = min(d[i - 1][0], d[i - 1][1]) + b[i];
}
// cout << *min_element(d[n-1], d[n-1]+3);
cout << min({d[n-1][0], d[n-1][1], d[n-1][2]});
return 0;
}
11726번: 2×n 타일링
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
www.acmicpc.net
1. 테이블 정의하기
d[i] = 2 * i 크기의 직사각형을 채우는 방법의 수
2. 점화식 찾기
d[n] = d[n-1] + d[n-2]
3. 초기값 정하기
d[1] = 1
d[2] = 2
#include <bits/stdc++.h>
using namespace std;
int d[1002];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int n;
cin >> n;
d[0] = 1;
d[1] = 2;
for (int i = 2;i<n;i++){
d[i] = (d[i-1] + d[i-2]) % 10007;
}
cout << d[n-1];
// cout << d[n-1]%10007; // int overflow
return 0;
}
11659번: 구간 합 구하기 4
첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j
www.acmicpc.net
d[i] = a[1] + a[2] + ... + a[i]
d[i] = d[i-1] + a[i]
a[i] + a[i+1] + ... + a[j]
= (a[1] + a[2] + ... + a[j]) - (a[1] + a[2] + ... + a[i-1])
= d[j] - d[i-1]
#include <bits/stdc++.h>
using namespace std;
int a[100002], d[100002];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int n,m;
cin >> n >> m;
for (int i = 0; i<n; i++){
cin >> a[i];
d[i] = d[i-1] + a[i];
}
for (int k = 0;k<m;k++){
int i,j;
cin >> i >> j;
cout << d[j-1] - d[i-2]<<"\n";
}
return 0;
}
12852번: 1로 만들기 2
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다.
www.acmicpc.net
#include <bits/stdc++.h>
#define MAX 100000
using namespace std;
int d[1000001];
int a[1000001];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int n;
cin >> n;
a[1] = 0;
for (int i = 2;i<=n;i++){
a[i] = a[i-1] + 1;
d[i] = i-1;
if (i%2 == 0 && a[i] > a[i/2] + 1){
a[i] = a[i/2] + 1;
d[i] = i/2;
}
if (i%3 == 0 && a[i] > a[i/3] + 1){
a[i] = a[i/3] + 1;
d[i] = i/3;
}
}
cout << a[n] << '\n';
int cur = n;
while(1){
cout << cur << ' ';
if (cur == 1) break;
cur = d[cur];
}
return 0;
}참고자료
[실전 알고리즘] 0x0D강 - 시뮬레이션
[실전 알고리즘] 0x0D강 - 시뮬레이션
안녕하세요, 이번 차시에서는 시뮬레이션을 다룹니다. 사실 코딩테스트에서 시뮬레이션 유형이라는 표현을 많이 쓰긴 하는데 이 유형의 문제들이 공통적인 특징을 가지고 있지는 않습니다. BFS
blog.encrypted.gg