[Algorithm] Dynamic Programming

한동안은 공채시즌이라서 알고리즘 공부를 좀 해야할 것 같아 코딩테스트용 알고리즘의 간단한 이론과 함께 연습을 해야겠다.

 

이번에 알아볼 알고리즘은 Dynamic Programming(줄여서 DP)이다.

 

Dynamic Programming이란??

 

수학과 컴퓨터 과학, 그리고 경제학에서 동적 계획법(動的計劃法, dynamic programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.

- 출처 : 위키백과

 

 동적 계획법은 문제를 여러개의 하위 문제로 나누어 푼 다음, 그것을 다시 결합하여 최종적 목표에 도달하는 것이다. 각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결할 수 있도록 한다.

 

https://coding-all.tistory.com/2

동적계획법(Dynamic Programing, DP)

이 분의 블로그가 공부하는데 많은 도움이 되었다.

 

DP에서는 메모이제이션이라는 기법을 사용한다.

메모이제이션(memoization)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이 되는 기술이다. 메모아이제이션이라고도 한다.

이 메모이제이션을 사용하면, 중복된 함수호출을 방지하여 성능을 개선할 수 있다.

 

top-down 방식

- 재귀처럼 위에서 아래로 내려오는 방식이다.

 

bottom-up 방식

- 반복문을 이용하여 처음값부터 다음값을 계산해 나가는 방식이다.

 

https://www.acmicpc.net/problem/2839

2839번: 설탕 배달

나는 문제를 다음과 같이 해결하였다. (top-down)

1. 설탕 N키로그램을 최대한 5키로그램짜리 자루에 담는다.

2. 이후, 만약 3키로그램에 남은설탕을 모두 담을 수 있다면 모두 담고,

3. 3키로짜리에 모두 담을 수 없다면, 5키로짜리 포대를 하나씩 찢어서 3키로짜리에 담을 수 있는지 확인하고, 넣는다.

4. 만약 5키로짜리 포대를 모두 찢었는데 3키로짜리에 다 들어가지 않는다면 -1이다. 아니면 갯수 출력

int main() 
{

int inputCnt = 0;
int threeKg = 0;
int fiveKg = 0;
int remain = 0;

cin >> inputCnt;

fiveKg = inputCnt / 5;

while (true)
{
if (fiveKg < 0)
{
break;
}

// 1. 5키로짜리에 전부 들어갈 경우, 그냥 끝내면 됨.
if ((inputCnt - fiveKg * 5) == 0)
{
break;
}
// 2. 5키로짜리에 전부 들어가지 않으면, 현재 남아있는 설탕이 3키로짜리에 다 들어가는지 확인
else
{
remain = inputCnt - fiveKg * 5;
if (remain % 3 == 0)
{
// 3키로짜리에 들어가면, 굿. 
inputCnt -= 3;
threeKg++;
}
else
{
// 안들어간다면, 해체한다.
fiveKg--;
}
}
}

int finalOutput = fiveKg+threeKg;
if (finalOutput == 0)
{
finalOutput = -1;
}

cout << finalOutput;
return 0;
}

 

한 두 문제만으로 익숙해질 수 없는 유형이므로, 여러 유형의 문제를 풀어 보는 것이 중요할 듯 싶다.

 

------ 수정 21.10.18 -> 얘는 DP로 해결한게 아니라, Greedy로 해결한 케이스다. 다시 DP로 풀어봐야 될 듯 싶다.

 

#include <iostream>
#define MAX_KG 5000

using namespace std;

int min(int a, int b)
{
return a < b ? a : b;
}

int main()
{
int dp[MAX_KG];

int N;

cin >> N;
// 3키로 봉지와 5키로 봉지에 나눠 담아야함.

for (int i = 0; i < MAX_KG; i++)
{
dp[i] = 99999;
}

dp[3] = 1;
dp[5] = 1;
// 3일때 1, 5일때 1

for (int i = 6; i <= N; i++)
{
dp[i] = min(dp[i - 3] + 1, dp[i - 5] + 1) ; // 이전의 dp케이스에 1을 더해주면 됨.
}

if (dp[N] > 99999) // 만약 dp[N]이 99999보다 클 경우, 3,5의 배수가 아닌 것.
{
cout << -1 << '\n';
}
else
{
cout << dp[N]<<'\n';
}


return 0;
}

 

-- 이게 DP의 Memoization을 이용한 풀이다. 꼭 기억해두자.