DP는 문제를 풀면서 이해하는게 좋다고 한다. 이번 강의에서는 비교적 쉽게 할 수 있는 다이나믹 프로그래밍 문제들이다. 다이나믹 프로그래밍 문제를 풀 때 기본은 점화식을 세우는 것인데, 이 문제들은 문제에서 나온 내용 그대로를 점화식으로 옮기면 되거나, 작은 문제를 만드는 방법이 문제에 나와있어 쉽게 풀 수 있다!
<1463번 / 1로 만들기>
정수 X를 1로 만들어 주는 연산을 하는 문제다. 대애박 하기싫어,,,,ㅎ_ㅎ
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
- X가 3으로 나누어 떨어지면, 3으로 나눈다.
- X가 2로 나누어 떨어지면, 2로 나눈다.
- 1을 뺀다.
이 문제를 해결하려면 우선 큰 문제인 X를 1로 만드는 것을 작은 문제로 쪼개서 생각해줘야 한다. 저 3가지 방법에서 3으로 나누는게 가장 빨리 1이 되는 방법이기 때문에 N/1, N/2, N-1 순으로 만들어보면 N이 10일 때 반례가 생긴다. 따라서 이 방법으로는 정답을 구할 수 없다. 그럼 점화식을 세워서 구해보도록 하자.
점화식은 문제에서 주어진 그대로 세운다면 D[N]은 N을 1로 만드는 최소 연산 횟수가 된다. (D[N]이 점화식) 그리고 작은 문제를 만드는 방법 세가지로 구분하면 N을 3으로 나누거나, 2로 나누거나, 1을 빼는것이다. 만약 3을 나눈다고 하면 나누는 과정 1번과 그 뒤에 1까지 만드는 과정은 D[N/3]이 된다. 이를 2,1모두 적용하면 아래와 같고, 이 들의 최솟값이 최소 연산 횟수가 된다. 따라서 점화식은 D[N] = min(D[N/3], D[N/2], D[N-1]) + 1 이라고 할 수 있다.
이 문제의 시간 복잡도는 "함수의 호출횟수 * 함수의 시간 복잡도"인데 함수의 호출횟수는 문제의 개수와 같기 떄문에 N이고, 함수의 시간복잡도는 문제 1개를 푸는데 필요한 시간복잡도이므로 O(1)이다.(한번 연산하기만 하면 되니깐) 따라서 둘을 곱하면 O(N)이라는 시간 복잡도가 나온다.
이제 코드를 구현해본다면 Top-down방식과 Bottom-up방식 두 가지로 풀 수 있다. 여기서 둘 다 memoization방식을 사용하며 이 때, D[N-1]을 먼저 구한다. D[N-1]은 2와 3으로 나누는 방식이 나눠 떨어질때만 가능한 반면 모든 수에 적용이 가능하기 때문에 먼저 구해서 값을 저장해놓고 2와 3으로 나누는 알고리즘에서 비교의 대상이 된다. 그리고 n이 1인 경우는 연산할 필요가 없기 때문에 예외처리를 해주고 d[1]=0이 된다.
아래는 먼저 Top-down 방식으로 구현한 코드이다. (재귀 함수 사용)
#include <iostream>
using namespace std;
#define MAX 1000000
int d[MAX];
int go(int n)
{
if (n == 1)
{
d[1] = 0;
return 0;
}
if (d[n] > 0)
return d[n];
d[n] = go(n - 1) + 1;
if (n % 2 == 0)
{
int t = go(n / 2) + 1;
if (d[n] > t)
{
d[n] = t;
}
}
if (n % 3 == 0)
{
int t = go(n / 3) + 1;
if (d[n] > t)
{
d[n] = t;
}
}
return d[n];
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
cout << go(n) << '\n';
return 0;
}아래는 Bottom-up 방식으로 구현한 코드이다. (반복문 사용)
#include <iostream>
using namespace std;
#define MAX 1000000
int d[MAX];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
d[1] = 0;
for (int i = 2; i <= n; i++)
{
d[i] = d[i - 1] + 1;
if (i % 2 == 0 && d[i] > d[i / 2] + 1)
{
d[i] = d[i / 2] + 1;
}
if (i % 3 == 0 && d[i] > d[i / 3] + 1)
{
d[i] = d[i / 3] + 1;
}
}
cout << d[n] << '\n';
return 0;
}<11726번 / 2*n 타일링>
2*n 직사각형을 1*2, 2*1 타일로 채우는 방법의 수를 구하는 문제이다. 그러면 점화식 D[N]은 2*n 직사각형을 채우는 방법의 수이다. 이 때 직사각형의 가장 오른쪽 타일이 채워지는 경우로 쪼개서 생각한다.
오른쪽에 타일을 놓을 수 있는 방법은 총 2가지가 있다. 이는 더 쪼갤 수 없으므로 가장 작은 문제가 된다.
이를 이용해 각 점화식을 구하고 전체 점화식을 구하면 D[N] = D[N-1] + D[N-2]가 된다.
이제 코드로 구현해보자
- Top-down 방식(재귀함수)
여기서 배열에 10007로 나눈 나머지를 저장안하고 그냥 값을 저장하고 출력할 때 10007로 나눴더니 틀렸다. 아마 배열에 저장할 수 있는 정수의 범위를 넘어서 그런것같다. 그래서 10007로 나눈값을 저장하였더니 맞았다ㅜㅅㅜ
#include <iostream>
using namespace std;
#define MAX 1001
int d[MAX];
int go(int n)
{
if (n == 0) return 0;
if (n == 1) return 1;
if (n == 2) return 2;
if (d[n] != 0)
return d[n];
d[n] = (go(n - 1) + go(n - 2)) % 10007;
return d[n];
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
if (n == 1)
{
cout << 1 << '\n';
return 0;
}
d[0] = 0;
d[1] = 1;
d[2] = 2;
cout << go(n) << '\n';
return 0;
}- Bottom-up 방식(반복문 사용)
단순 반복문으로 구현 가능하다. 위에 방법보다 쉬운듯?
#include <iostream>
using namespace std;
#define MAX 1001
int d[MAX];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
d[0] = 0;
d[1] = 1;
d[2] = 2;
for (int i = 3; i <= n; i++)
{
d[i] = (d[i - 1] + d[i - 2]) % 10007;
}
cout << d[n] << '\n';
return 0;
}<11727번 / 2*n 타일링>
이건 위 문제에서 2*2타일이 추가된 경우로 위의 점화식에서 2*2타일이 오른쪽에 놓이는 경우만 추가하면 된다. 이는 D[N-2]이므로 전체 점화식은 D[n] = D[n-1] + 2*D[n-2]가 된다.
-Top-down 방식
#include <iostream>
using namespace std;
#define MAX 1001
int d[MAX];
int go(int n)
{
if (n == 0) return 0;
if (n == 1) return 1;
if (n == 2) return 3;
if (d[n] != 0)
return d[n];
d[n] = (go(n - 1) + go(n - 2) * 2) % 10007;
return d[n];
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
d[0] = 0;
d[1] = 1;
d[2] = 3;
cout << go(n) << '\n';
return 0;
}-Bottom-up 방식
#include <iostream>
using namespace std;
#define MAX 1001
int d[MAX];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
d[0] = 0;
d[1] = 1;
d[2] = 3;
for (int i = 3; i <= n; i++)
{
d[i] = (d[i - 1] + d[i - 2] * 2) % 10007;
}
cout << d[n] << '\n';
return 0;
}<9095번 / 1, 2, 3 더하기>
정수 n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제이다. 이 문제의 점화식 D[N]은 n을 1, 2, 3의 합으로 나타내는 방법의 수이다. 이를 작은 문제로 나누는 방법은 마지막에 뭐가 더해지느냐에 따라 나눈다. 그러면 총 3가지의 경우(1, 2, 3)의 경우로 나뉜다. 그러면 점화식은 D[N] = D[N-1] + D[N-2] + D[N-3]이 된다.
이 때 D[0]은 1이다. 왜냐하면 0일때는 아무것도 더하지 않는 경우가 1개 있는것이므로 1로 처리한다.
자 이제 코드로 구현해봅시당
> Top-down 방식
#include <iostream>
using namespace std;
#define MAX 1001
int d[MAX];
int go(int n)
{
if (n == 0) return 1;
if (n == 1) return 1;
if (n == 2) return 2;
if (d[n] != 0)
return d[n];
d[n] = go(n - 1) + go(n - 2) + go(n - 3);
return d[n];
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
d[0] = 1;
d[1] = 1;
d[2] = 2;
while (n--)
{
int k;
cin >> k;
cout << go(k) << '\n';
}
return 0;
}> Bottom-up
#include <iostream>
using namespace std;
#define MAX 1001
int d[MAX];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
d[0] = 1;
d[1] = 1;
d[2] = 2;
while (n--)
{
int k;
cin >> k;
for (int i = 3; i <= k; i++)
{
d[i] = d[i - 1] + d[i - 2] + d[i - 3];
}
cout << d[k] << '\n';
}
return 0;
}다음다음!! 넘어가 너머가!!
'코딩테스트 > 알고리즘 기초 강의' 카테고리의 다른 글
| 4강 다이나믹 프로그래밍 1 - 합분해까지 (0) | 2020.08.24 |
|---|---|
| 4강 다이나믹 프로그래밍 1 - 이친수까지 (0) | 2020.08.22 |
| 4강 다이나믹 프로그래밍 1 - 다이나믹 프로그래밍 소개 (0) | 2020.08.21 |
| 3강 수학 1 - 참고 (0) | 2020.08.20 |
| 3강 수학 1 - 연습 (0) | 2020.08.20 |
댓글