동전 교환 알고리즘


개념


편의점 아르바이트생인 A는 야간에 편의점 알바를 하고 있어요. 막상 편의점에 도착해서 보니까 동전이 없습니다. 그래서 사장님께 전화를 걸었으나, 이미 술취해서 뻗어버린 상태입니다. 할 수 없이 일단 가지고 있는 동전으로 거스름돈을 주며 내일 아침 사장님이 올때까지 뻐겨야하는 상황이 발생했습니다.

그러기 위해서는 거스름돈에 사용되는 동전의 갯수를 최소로 사용하여 주어야하는데 어떻게 최소 동전 갯수를 구할 수 있을까요?


현실에서는 10원, 50원, 100원, 500원의 동전이 있지만 여기서는 1, 4, 5, 6원의 동전이 있다고 가정하도록 하겠습니다. 만약 23원의 거스름돈을 위의 동전을 최소로 사용해 거슬러준다면 어떻게 거슬러주면 될까요? 여러가지가 있지만, 우선 가장 큰 값인 6을 먼저주고 남은것은 그 다음 큰 동전으로 사용한다면 6원 3개, 5원 1개로 23원을 만들 수 있습니다. 동전을 최소로 사용해서 준 것 맞습니까?




네, 가장 최소의 동전을 사용해서 준 것이 맞습니다.

항상 최대값의 동전을 우선적으로 사용해서 얻은 결과가 바로 답일까요? 일리있어 보이지만 항상 그렇지 않습니다.


14원을 예로 한번 들어보도록 합시다.

위의 방식대로 한다면 6원 2개, 1원 2개, 4개의 동전을 사용해서 14원을 만들 수 있습니다.

하지만 5원부터 주게되면 5원 2개, 4원 1개로 3개의 동전을 사용해서 14원을 만들 수 있습니다.


이제부터 어떻게 구할지 생각해보도록 하겠습니다.

우선 동전 하나를 가지고 얼마를 만들 수 있을지 생각합시다. 우선 1원입니다. 1원은 모든 수를 전부 만들 수 있습니다. 그렇다면 아래의 표와 같겠네요.


1원 사용시


 거스름 돈

동전 갯수(1원 갯수, 4원 갯수, 5원 갯수, 6원 갯수) 

 1

 1(1,0,0,0)

 2

 2(2,0,0,0)

 3

 3(3,0,0,0)

 4

 4(4,0,0,0)

 5

 5(5,0,0,0)

 6

 6(6,0,0,0)

 7

 7(7,0,0,0)

 8

 8(8,0,0,0)

 9

 9(9,0,0,0)

 10

 10(10,0,0,0)

 11

 11(11,0,0,0)

 12

 12(12,0,0,0)

 13

 13(13,0,0,0)

 14

 14(14,0,0,0)



4원을 사용한다면 4원은 당연히 한개로 만들 수 있고, 5원은 그 전의 1원과 합쳐서 만들 수 있습니다. 그렇다면 5원은 2개로 만들 수 있겠군요. 8원은 그전의 4원 2개로 만들 수 있습니다.

9원은 어떻겠습니까? 그전에 5원을 2개의 동전으로 구했었습니다. 1원과 4원을 합쳐서 말입니다. 여기에 4원을 더 얹으면 9원 아닌가요? 그래서 1원 1개, 4원 2개로 9원을 만들 수 있습니다. 그렇다면 표가 다음과 같이 바뀝니다.


4원 사용시


 거스름 돈

동전 갯수(1원 갯수, 4원 갯수, 5원 갯수, 6원 갯수) 

 1

 1(1,0,0,0)

 2

 2(2,0,0,0)

 3

 3(3,0,0,0)

 4

 1(0,1,0,0)

 5

 2(1,1,0,0)

 6

 3(2,1,0,0)

 7

 4(3,1,0,0)

 8

 2(0,2,0,0)

 9

 3(1,2,0,0)

 10

 4(2,2,0,0)

 11

 5(3,2,0,0)

 12

 3(0,3,0,0)

 13

 4(1,3,0,0)

 14

 5(2,3,0,0)



이제 5원을 사용하도록 합시다. 5원을 사용하게 되면 5원은 동전 한개로 만들 수 있고, 6원은 1원의 동전화 합쳐서 만들 수 있겠습니다. 10원은 5원 두개로 만들 수 있고 11원이 그 전의 6원을 만들었던 것에서 5원을 추가하여 만들 수 있답니다. 




5원 사용시


 거스름 돈

동전 갯수(1원 갯수, 4원 갯수, 5원 갯수, 6원 갯수)  

 1

 1(1,0,0,0)

 2

 2(1,0,0,0)

 3

 3(1,0,0,0)

 4

 1(0,1,0,0)

 5

 1(0,0,1,0)

 6

 2(1,0,1,0)

 7

 3(2,0,1,0)

 8

 2(0,2,0,0)

 9

 2(0,1,1,0)

 10

 2(0,0,2,0)

 11

 3(1,0,2,0)

 12

 3(0,3,0,0)

 13

 3(0,2,1,0)

 14

 3(0,1,2,0)


이제 감이 오시나요?


결국 현재의 동전만큼을 뺀 거스름돈에서 현재 동전하나를 추가하여 만드니까 그 전의 거스름돈에 1을 더하면 됩니다. 

하지만 이미 구해진 거스름돈이 더 적은값을 가지고 있다면 현재의 값을 유지하면 되는 것입니다. 그래서 이런 식이 나오게 됩니다.


dp[j] = MIN(dp[j], dp[j - coin[i]] + 1); 


dp[j]는 현재 구할 거스름돈의 값입니다. 그래서 현재 거스름돈에서 현재 동전을 뺀 값이 dp[j-coin[i]]를 의미합니다. 그래서 현재 거스름돈 dp[j]와dp[j-coin[i]]+1을 비교하여 작은 값이 답이 됩니다.


이제 5도 했으니 6도 해봅시다. 위의 식대로 구한다면 다음의 표가 완성되겠습니다.


6원 사용시


 거스름 돈

동전 갯수(1원 갯수, 4원 갯수, 5원 갯수, 6원 갯수)   

 1

 1(1,0,0,0)

 2

 2(2,0,0,0)

 3

 3(3,0,0,0)

 4

 1(0,1,0,0)

 5

 1(0,0,1,0)

 6

 1(0,0,0,1)

 7

 2(1,0,0,1)

 8

 2(0,2,0,0)

 9

 2(0,1,1,0)

 10

 2(0,0,2,0)

 11

 2(0,0,1,1)

 12

 2(0,0,0,2)

 13

 3(1,0,0,2)

 14

 3(0,1,2,0)



이제 모든 동전을 사용해서 14원이 3개의 동전으로 교환될 수 있다는 것을 알았습니다.




구현

구현은 뭐 위에서 설명한 것을 그대로 코드로 옮기면 되는데 몇몇 설명할게 아직은 남아있습니다. 전체 소스코드를 보면서 이야기 해보도록 하겠습니다.

#include <stdio.h>
#define MIN(a,b) a<b ? a:b
#define N 4
#define M 14
#define INF 987654321;
int dp[M+1];
int coin[N] = { 1,4,5,6 };
int main() {
	int i, j;

	for (i = 1; i <= M; i++)
		dp[i] = INF;

	for (i = 0; i < N; i++) {
		printf("동전 %d 사용시\n",coin[i]);
		for (j = coin[i]; j <= M; j++) {
			dp[j] = MIN(dp[j], dp[j - coin[i]] + 1);
			printf("%d %d\n", j, dp[j]);
		}
		printf("\n\n");
	}
	printf("%d\n", dp[M]);
}




우선 dp를 아주 큰 값으로 초기에 설정합니다. 그렇지 않으면 0이 되니까요. MIN 매크로 함수를 통해서 작은 값을 구해야하는데 dp가 0이 되버리면 MIN은 항상 0을 반환하게 됩니다.
위에서 이야기한대로 코드로 옮겼습니다.


반응형
블로그 이미지

REAKWON

와나진짜

,

동적계획법(Dynamic Programming)


동적계획법(Dynamic Programming)이라는 것은 알고리즘에서 아주 자주 등장하는 주제입니다. 줄여서 DP라고도 부릅니다.

DP의 특징은 어떤 부분 문제는 두 개 이상의 문제를 푸는 데 사용될 수 있습니다. 그래서 "답을 여러 번 계산하는 대신 한번 만 계산한다!" 입니다.  

개인적으로 DP를 보면 항상 먼저 떠오르는게 바로 재활용이라고 생각합니다. 재활용을 통해서 속도를 빠르게 향상 시킬 수 있는 방법입니다.


어떻게 재활용을 할 수 있을까요? 가장 유명한 피보나치 수열을 한 번 보도록 해봅시다. 피보나치의 정의는 아래와 같습니다. 간단합니다.




이 피보나치 수열을 재귀함수로 정의해보겠습니다. 





int fibo(int n) {
	if (n == 0) return 0;
	if (n == 1) return 1;
	return fibo(n - 1) + fibo(n - 2);
}

이런식으로 정의가 될 것 같네요. 여기서 n은 무조건 양수라고 가정하겠습니다. 음수는 귀찮습니다. 만약 fibo(5)라는 값을 계산하려면 어떤 과정을 거칠까요?


fibo(5) = fibo(4) + fibo(3) 라는 것을 알 수 있고 이제 fibo(4)fibo(3)을 더해주기만 하면 됩니다.

그럼 왼쪽 fibo(4)부터 차근 차근히 계산을 해보도록 하겠습니다. 노가다로 해보겠습니다.

fibo(4) = fibo(3) + fibo(2) 


이것도 역시 fibo(3), fibo(2)를 계산해야 되겠군요


fibo(3) = fibo(2) + fibo(1) 이 되겠습니다.


fibo(2) = fibo(1) + fibo(0) 이 되어서 fibo(2) = 1이라는 것을 알게 됩니다.


그렇다면 fibo(3) = fibo(2) + fibo(1) 이니까 1+1 해서 fibo(3) = 2라는 것을 알 수 있겠네요.


fibo(4) = fibo(3) + fibo(2) 랍니다. 여러 분, 이제 슬슬 감이 오고 있나요? 노가다 하기 싫습니다.


fibo(4) = 2 + fibo(2)라는 것이 됩니다. fibo(3)을 방금전에 계산했거든요. 그러면 오른쪽 fibo(2)를 구해보도록 합시다.

fibo(2) = fibo(1) + fibo(0) 으로 fibo(2)=1입니다.


그럼 fibo(4) = 2+ 1 = 3 이라는 결과가 나옵니다. 이제 fibo(4) 구한 겁니다.


이제 fibo(3)을 구해볼까요?


이제 손가락이 아파서 못할 거 같고요

fibo(3) 뭐라고 했지요? 아까 계산했는데 말입니다.

2가 나왔죠?


이 같은 노가다를 막기 위한 것이 바로 DP의 큰 역할이라고 할 수 있겠습니다. 만약 위의 저 코드를 통해서 fibo(40)을 계산한다면 얼마나 걸릴까요? 아마 계산했던 결과를 또 계산하고 앉아있으니 오래 걸릴거라는 걸 짐작할 수 있나요?

네, 오래 걸립니다. 우리는 이제 계산된 값을 재활용 합시다. 이렇게요.




int dp[50];
int fibo(int n) {
	
	if (n == 0) return 0;
	if (n == 1) return 1;
	if (dp[n] != -1) return dp[n];
	return dp[n] = (fibo(n - 1) + fibo(n - 2));
}
int main() {
	memset(dp, -1, sizeof(dp));
	printf("fibo(40)=%d\n", fibo(40));
}

어떻습니까? 맨 처음 초기화값은 -1입니다. memset함수에 주목합시다. 이 함수는 dp라는 배열을 -1이라는 값으로 전부 초기화 시키는 역할을 하는 것이랍니다. 처음 계산하는 값이라면 dp[n]에 -1이라는 값이 들어있을 겁니다. 그렇지 않을까요? 이해 되십니까?


그리고 다음에 같은 값을 계산할때, 즉 또 같은 짓거리할 때 그때는 -1이라는 값이 아닌 0이나 1이상의 값이 들어있을 겁니다. 피보나치는 음수가 나올 수 없으니까요. 그렇단 얘기는, 즉 dp[n] != -1이라는 얘기는 앞 전에 이미 한번 계산이 된 값이니까 그냥 dp[n]을 바로 반환해버리면 fibo(n-1)과 fibo(n-2)를 더 이상 호출하지 않으니 시간을 절약할 수 있다는 이야기랍니다. 이미 계산된 결과를 재활용하는 것이죠.

★우리는 dp[n]을 이용하여 재활용합니다. 그러니까 dp[n]은 fibo(n)의 결과를 기억하고 있는 겁니다. 이것을 메모이제이션(memoization) 이라고 합니다. 메모이제이션! 기억해두세요. 여러모로 쓸일이 많을 겁니다.

맨 처음 코드와 dp를 적용한 코드를 한 번 실행시켜보고 비교해보세요. 차이가 확연히 드러날 겁니다.

DP는 그럼 어디에 쓰일까요? 동전 교환 알고리즘, 냅색 알고리즘 등 쓰임새는 아주 유용합니다. DP는 recursive(재귀적) 뿐만 아니라 iterative(반복적)하게도 사용될 수 있습니다. dp에 관한 기본적인 이론을 쉽게 풀어내느라고 좀 횡설수설한 거 같기도 합니다. 부족한글 읽어주셔서 감사합니다. 다음에는 본격적인 문제를 풀어보도록 합시다.


반응형
블로그 이미지

REAKWON

와나진짜

,