📚 다이나믹 프로그래밍(DP)
- 다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법
- 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 게산하지 않도록 합니다
- 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탑다운과 보텀업)으로 구성됩니다
- 동적계획법이라고도 한다
DP는 문제가 다음의 조건을 만족할 때 사용할 수 있다
- 최적 부분 구조 (Optimal Substructure)
- 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다
- 중복되는 부분 문제 (Overlapping Subproblem)
- 동일한 작은 문제를 반복적으로 해결해야 한다
📕 피보나치 수열
첫 번째 항과 두 번째 항이 1이며 그 뒤의 항은 바로 앞 두 항의 합인 수열이다
#include <iostream>
using namespace std;
int fibo(int x)
{
if (x == 1 || x == 2)
return 1;
return fibo (x - 1) + fibo(x - 2);
}
단순 재귀 함수로 피보나치 수열을 구현하면 지수 시간 복잡도를 가지게 된다
위 사진과 같이 f(2)가 여러 번 호출되는 것을 확인할 수 있다. (중복되는 부분)
시간 복잡도 O(2^N)
📘 메모이제이션(Memoization)
- 메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 하나
- 한 번 계산한 결과를 메모리 공간에 메모하는 기법
- 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져옵니다
- 값을 기록해 놓은다는 점에서 캐싱(Caching)이라고도 합니다
탑다운 vs 보텀업
- 탑다운(메모이제이션)방식은 하향식이라고도 하며 보텀업 방식은 상향식이라고도 합니다
- 다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식입니다
- 결과 저장용 리스트는 DP 테이블이라고 부릅니다
- 엄밀히 말하면 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 의미합니다
- 따라서 메모이제이션은 다이나믹 프로그래밍에 국한된 개념은 아닙니다
- 한 번 계산된 결과를 담아 놓기만 하고 다이나믹 프로그래밍을 위해 활용하지 않을 수 있습니다
보텀업 dp 코드
#include <iostream>
using namespace std;
long long d[100];
int main()
{
d[1] = 1;
d[2] = 1;
int n = 50;
for (int i = 3; i <= n; i++)
d[i] = d[i - 1] + d[i - 2];
cout << d[n] << "\n";
return 0;
}
이미 계산관 결과를 저장해서 다음과 같이 색칠된 노드만 처리가능하다
📚 예제
📕 1로 만들기
정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지이다.
X가 5로 나누어떨어지면, 5로 나눈다.
X가 3으로 나누어떨어지면, 3으로 나눈다.
X가 2로 나누어떨어지면, 2로 나눈다.
X에서 1을 뺀다정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오
수정전 코드
#include <iostream>
using namespace std;
int X;
int cnt = 0;
int arr[3] = {2, 3, 5};
int main()
{
cin >> X;
while (X != 1)
{
int min = 2147483647;
int save = 0;
int mod = 0;
for (int i = 0; i < 3; i++)
{
if (X / arr[i] < min && X / arr[i] != 0)
{
min = X / arr[i];
mod = X % arr[i];
save = arr[i];
}
}
X /= save;
if (mod == 4)
cnt += 2;
else if(mod == 1 || mod == 2 || mod == 3)
cnt++;
if (X == 1)
break;
cnt++;
}
cout << cnt << "\n";
return 0;
}뭔가 접근이 크게 잘못된거 같다 단순히 2,3,5를 나누면서 몫이 제일 작을때값을 저장시키면서 반복문을 돌려보려고 했는데 만들다가 머리가 터져버렸다 그냥 만들다가 포기하고 저자의 코드를 참고해보았다
#include <iostream>
using namespace std;
int d[30001];
int x;
int main()
{
cin >> x;
for (int i = 2; i <= x; i++)
{
d[i] = d[i - 1] + 1;
if (i % 2 == 0)
d[i] = min(d[i], d[i / 2] + 1);
if (i % 3 == 0)
d[i] = min(d[i], d[i / 3] + 1);
if (i % 5 == 0)
d[i] = min(d[i], d[i / 5] + 1);
}
cout << d[x] << '\n';
}좀 이해가 가지않는다 공부가 좀 더 필요한거 같다...
📘 개미 전사
- 개미 전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 합니다 메뚜기 마을에는 여러개의 식량창고가 있는데 일직선으로 이어져 있다
- 각 식량창고에 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정입니다. 이때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있습니다
- 따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 합니다.
점화식 ai = max(a(i-1), a(i-2) + ki)
한칸 이상 떨어진 식량창고는 항상 털 수 있으므로 (i - 3) 이하는 고려할 필요가 없음
첫번째와 두번째 원소에 대한건 확정이니 미리 넣고 N항까지 넣게 된다
#include <iostream>
using namespace std;
int arr[100];
int arr2[100];
int N;
int main()
{
cin >> N;
for (int i = 0; i < N; i++)
cin >> arr[2];
arr[0] = arr2[0];
arr[1] = max(arr2[0], arr2[1]);
for (int i = 2; i < N; i++)
arr[i] = max(arr[i - 1], arr[i - 2] + arr2[i]);
cout << arr[N - 1] << "\n";
return 0;
}📗 바닥 공사
가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다. 태일이는 이 얇은 바닥을 1 X 2의 덮개, 2 X 1의 덮개, 2 X 2의 덮개를 이용해 채우고자 한다.
전 문제랑 비슷한듯 아닌듯 그런 문제이다 dp문제같은경우 dp테이블을 만들고 점화식을 새운다음 접근을 해야한다는걸 이해가 가기는하는데 막상 문제를 접할때는 어떤식으로 접근해야할지 아에 떠오르지가 않는다 많은 문제를 풀어보고 경험을 해봐야 이런 문제를 풀 수 있을꺼라 생각이 든다
왼쪽부터 i - 1까지 길이가 덮개로 이미 채워져 있으면 2 X 1의 덮개를 채우는 하나의 경우밖에 존재하지 않는다
왼쪽부터 i - 2까지 길이가 덮개로 이미 채워져 있으면 1 X 2 덮개 2개를 넣는 경우, 혹은 2 X 2의 덮개 하나를 넣는 경우로 2가지 경우가 존재한다. 참고로 2 X 1 덮개 2개를 넣는 경우를 고려하지 않는 이유는 1에서 고려되었기 때문이다
이를 바탕으로 점화식을 새우면
ai = a(i-1) + a(i-2) * 2
#include <iostream>
using namespace std;
int d[1001];
int n;
int main()
{
cin >> n;
d[1] = 1;
d[2] = 3;
for (int i = 3; i <= n; i++) {
d[i] = (d[i - 1] + 2 * d[i - 2]) % 796796;
}
cout << d[n] << '\n';
}📙 효율적인 화폐 구성
➕ 9095 1, 2, 3 더하기
정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.
- 1+1+1+1
- 1+1+2
- 1+2+1
- 2+1+1
- 2+2
- 1+3
- 3+1
정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.
먼저
N 이 1, 2, 3인 경우에는 기본 값으로 주어진다
n을 표현할수 있는 경우의 수를 A(n)이라고 한다면
A(1) = 1
A(2) = 2
A(3) = 4
만약 N = 4라고 한다면
1 + 3 [A(3)]
2 + 2 [A(2)]
3 + 1 [A(1)]
총 표현할수 있는 경우의 수는 A(3) + A(2) + A(1)이 된다
이말은 즉
A(i) = A(i - 1) + A(i - 2) + A(i - 3) 으로 표현할수 있다
#include <iostream>
using namespace std;
int arr[12] = {0, 1, 2, 4, };
int N;
int dp(int x)
{
if (x < 4)
return arr[x];
else
return arr[x] = dp(x - 1) + dp(x - 2) + dp(x - 3);
}
int main()
{
cin >> N;
for (int i = 0; i < N; i++)
{
int x;
cin >> x;
cout << dp(x) << "\n";
}
return 0;
}이 문제에서는 N의 최대값이 12밖에 안되는데 만약 좀더 커지게 된다면 시간복잡도에서 좋은 결과를 얻지 못할거라 생각이 든다 그래서 메모이제이션으로 개선하면 좀더 좋은 코드가 될거 같다
