대학원에서의 한학기가 벌써 지나갔다.
시간이 너무 빨라서 어떻게 해야 할지도 모르겠다.
각설하고 기말고사 과제로 그리디 알고리즘과 동적프로그래밍에 대해서 준비하게 되었다.
내용은 최소 동전 개수 알고리즘을 그리디와 DP로 구성해서 구현하는 것이다.
원래는 프림이나 크루스칼 알고리즘으로 생각하고 있었는데 다행히(?) 나오지 않았다.
문제를 알아보고 해결 방법을 설명하는 방식으로 진행해보겠다.
1. 그리디 알고리즘 기법으로 최소 동전 개수 교환 알고리즘을 구현 했을 때 최적 해결책을 구할 수 없었던 이유를 설명하라.
미국 동전 4총사가 있다.
1센트 페니, 5센트 니켈, 10센트 다임, 25센트 쿼터
우리는 38센트를 거스름돈으로 거슬러 줄 때 동전을 최소한 써서 거슬러 주고 싶다.
어떻게 접근해야할까?
그리디 알고리즘은 매순간 최적의 선택을 하게 설계된다.
그렇다면 우리는 매순간 거스름돈이 가장 작게 남는 경우를 도출하는 것이 그리디 알고리즘이 추구하는 방향이라고 생각하면 된다.
- 거스름돈이 가장 작아질 수 있도록 가장 가치가 큰 25센트 동전으로 나누어 준다.
(부분 최적해는 25센트:1개)
- 다음 가치가 가장 큰 10센트 동전으로 나머지를 나누어 준다.
(부분 최적해 25센트:1개, 10센트:1개)
- 5센트 동전이 다음으로 가장 가치가 크지만 남은 3센트를 지불할 방법이 없기 때문에 1센트로 나누어 준다.
(부분 최적해 25:1개, 10센트:1개, 1센트:3개)
- 38센트의 최소 동전 개수는 5개라는 해가 도출된다.
5개라는 최적해가 도출되었지만 과연 이 값이 정말 최적해인지 의심해야한다.
구현한 코드를 살펴보자
// C++ program for coin change problem.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> coin = {1,5,10,25};
int GreedyAlgorithmCentMaker(int target) {
int remain = target;
int result = 0;
sort(coin.begin(), coin.end());
reverse(coin.begin(), coin.end());
for (int i = 0; i < coin.size(); i++)
{
if (remain >= coin[i])
{
result += remain / coin[i];
remain = remain % coin[i];
}
}
return result;
}
int main()
{
GreedyAlgorithmCentMaker(58);
}
무난하게 코인을 내림차순으로 정렬하고 순차적으로 반복문을 돌면서 나머지가 해당 코인보다 크거나 같다면 나누고 몫과 나머지를 처리하도록 구현했다.
앞에서도 언급했듯이 과연 부분의 최적해가 전체의 최적해일까?
해당 4총사는 센트의 차이가 매우 큰값이 하나 존재하기 때문에 그리디 알고리즘으로도 충분히 최적해가 도출된다.
하지만 그 값의 크기가 달라진다면 그리디가 최적해를 내놓는지 살펴볼 필요가 있다.
12 센트, 10센트, 5센트, 1센트 동전 구성일 때,
- 35센트를 구성했을 때, (12:2, 10:1, 1:1)가 도출되지만 (10:3, 5:1) 구성도 최적해가 될 수 있다.
- 16센트를 구성했을 때, (12:1, 1:4)가 도출되지만 (10:1, 5:1, 1:1) 구성이 전체에 대한 최적해가 된다.
- 28센트를 구성했을 때, (12:2, 1:4)가 도출되지만 (10:2, 5:1, 1:3) 구성도 최적해가 될 수 있다.
최소 동전 개수 알고리즘을 그리디 알고리즘으로 구현했을 때, 최적해를 항상 도출하는 것이 아니므로 최적 해결책을 구할 수 없다는 결론이 나온다.
2. ’최소 동전 교환 알고리즘’을 동적 계획 기법을 이용하여 작성하고 시간복잡도를 도출하여 성능을 증명하시오.
일단 동적계획법으로 구현된 피보나치를 살펴보겠다.
// C++ program for coin change problem.
#include <iostream>
#include <vector>
using namespace std;
int Fibo(int n)
{
vector<int> DP(n + 1, 0);
DP[1] = 1;
for (int i = 2; i <= n; i++)
{
DP[i] = DP[i - 1] + DP[i - 2];
}
return DP[n];
}
int main()
{
std::cout << "Hello World!\n";
}
상향식 방식으로 부분의 값을 구하고 다시 그 부분으로 다음 부분의 값을 구한다.
다음은 최소 동전 교환 알고리즘을 동적 걔획법으로 구현했다.
// C++ program for coin change problem.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX 99999
int DP(int target) {
vector<int> coin = { 1,5,10,25 };// 코인 구성
vector<int> arr(target + 1, MAX);
arr[0] = 0;
for (int i = 0; i < coin.size(); i++)
{
for (int j = coin[i]; j <= target; j++)
{
arr[j] = min(arr[j], arr[j - coin[i]] + 1);
}
}
return arr[target];
}
int main()
{
DP(38);
}
가장 작은 페니부터 시작해서 모든 거스름돈 경우에 할당한다.
그리고 이를 자신의 크기 아래의 (자신과 배수 차이인 곳의 인덱스를 조회) 인덱스와 비교하면서 작은 값을 할당한다.
이는 단순해 보이지만 최적해를 아주 훌륭하게 도출해준다.
시간복잡도는 동적 계획법을 사용할 때 연산 시간을 제외하고 a(n-a) = an-a^2 가 나오고 이를 최고차항만 남기고 상수항을 없애면 O(N)이 나오게 된다.
3. 동적 계획 기법을 이용한 ‘최소 동전 교환 알고리즘’을 프로그래밍 언어를 통해 구현하여 제출하시오.
네가지 언어로 구현했다.
타입스크립트로 작성해보기
// TypeScript program for coin change problem.
const max = 99999;
function DP(target:Number):Number{
const coin:Array<Number> = [1,5,10,25]
const arr:Array<Number> = new Array(target).fill(max);
arr[0] = 0;
for (let i = 0; i < coin.length; i++) {
for (let j = +coin[i]; j <= target; j++) {
arr[j] = Math.min(+arr[j],+arr[j-(+coin[i])]+1);
}
}
return arr[+target];
}
파이썬으로 작성해보기
# Python program for coin change problem.
Max = 99999
def DP(target):
coin = [1,5,10,25]
arr = [Max] * (target+1)
arr[0]=0
for i in range(0,len(coin)):
for j in range(coin[i],target+1):
arr[j] = min(arr[j],arr[j-coin[i]]+1)
return arr[target]
print(DP(38))
C#으로 작성해보기
// C# program for coin change problem.
using System;
using System.Collections.Generic;
using System.Linq;
namespace Problem22
{
internal class Program
{
private static int Max = 99999;
static void Main(string[] args)
{
Console.WriteLine(DP(58));
}
public static int DP(int target)
{
List<int> coin = new List<int>{ 1, 5, 10, 25 };
List<int> arr = Enumerable.Repeat(Max, target + 1).ToList();
arr[0] = 0;
for (int i = 0; i < coin.Count; i++)
{
for (int j = coin[i]; j <= target; j++)
{
arr[j] = Math.Min(arr[j], arr[j - coin[i]] + 1);
}
}
return arr[target];
}
}
}
CPP로 작성해보기
// C++ program for coin change problem.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX 99999
int DP(int target) {
vector<int> coin = { 1,5,10,25 };// 코인 구성
vector<int> arr(target + 1, MAX);
arr[0] = 0;
for (int i = 0; i < coin.size(); i++)
{
for (int j = coin[i]; j <= target; j++)
{
arr[j] = min(arr[j], arr[j - coin[i]] + 1);
}
}
return arr[target];
}
int main()
{
DP(38);
}
우원 /
우원입니다.
