[알고리즘] 동전 교환 알고리즘

동전 교환 알고리즘

   최소의 갯수로 거스름돈을 주는 방법에 대해 알아보자.

 

그리디 알고리즘

   동전교환 문제를 풀기 위해 그리디 알고리즘을 사용할 수 있다. 하지만 그리디 알고리즘은 가장 적은 동전 수의 최적해를 항상 찾는 것은 아니다. 예를 들어보자, 동전의 종류가 [1, 3, 4] 이렇게 존재하고 9원을 거스름돈으로 준다고 하면, 그리디 알고리즘은 4원 1개, 3원 1개, 1원 2개를 선택할 것이다. 하지만 3원 3개를 거스름돈으로 주는 방식이 가장 적은 동전의 개수를 이용한 최적해이다.  

 

그렇다면 항상 최적해를 찾기 위해 어떤 알고리즘을 이용해야 할까?

 

DFS

   DFS 알고리즘을 이용할 수 있다. 위와 같이 [1,3,4] 동전 종류가 있고, 9원을 거스름돈으로 거슬러 준다고 해보자. 각 코인마다 3개의 가지가 뻗는다고 생각할 수 있다. (동전 합계, 갯수)로 표현하면 트리모양은 다음과 같은 형태를 가질 것이다.

 

(0, 0) --> (1, 1) --> (2, 2) --> (3, 3)   --> (4, 4) -->

         |                 |                  |                --> (6, 4) -->

         |                 |                  |                --> (7, 4) -->

         |                 |                  | --> (5, 3) --> (6, 4)

                                                                --> (8, 4)

                                                                --> (9, 4)

         |                 |                  | --> (6, 3)

         |                 | --> (4, 2)

         |                 | --> (5, 2)

         | --> (3, 1) 

         | --> (4, 1)

 

 

이를 코드로 표현하면 다음과 같다. (만약 합계가 거슬러 줘야 할 액수보다 크면 return 해야 한다.) 

int[] coins = new int[3];

public void DFS(int sum, int count){
	if(sum >"거스름 액수") return;
	if(sum==m){
		answer=Math.min(answer, count);
	}
	else{
		for(int i=0; i<n; i++){
			DFS(sum+arr[i], count+1);
		}
	}	
}

 

위의 코드를 조금 개선해보자. 만약 뻗어나가는 트리의 count가 answer의 count보다 크다면 맨 마지막 가지의 count는 answer의 count보다 클 것이기 때문에 더 이상 뻗어나갈 필요가 없다. 따라서 다음 코드를 추가하자.

if(count > answer) return;

 

 

코드를 좀 더 개선해보자. 위의 코드에서는 가장 작은 동전인 1부터 시작한다. 그러면 answer가 9가 되는데 만약, 크기가 가장 큰 동전인 4부터 시작하면 answer가 3이 될 것이다.(4,4,1). answer가 일단 3이 되면 if(count > answer)에 의해 많은 가짓수들이 없어지므로 시간이 크게 감소한다. 이를 위해 coins의 배열을 가장 큰 수부터 정렬한다.

 

 

이를 반영한 최종 코드는 다음과 같다. 

int[] coins = new int[3];

public void DFS(int sum, int count){
	if(sum >"거스름 액수") return;
    if(count > answer) return;
	if(sum==m){
		answer=Math.min(answer, count);
	}
	else{
		for(int i=0; i<n; i++){
			DFS(sum+arr[i], count+1);
		}
	}	
}

public static void main(String[] args) {
	...
    Arrays.sort(coins, Collections.reverseOrder());
    DFS(0,0);
}

 

DP 알고리즘

   동전 알고리즘에 가장 이상적인 알고리즘은 DP 동전 알고리즘이다. 먼저 동전 거스름돈 액수 만큼의 배열 크기를 가진 배열을 준비한다. 

       1    2    3    4    5    6    7    8    9

1     0    0    0    0    0    0    0    0   0

3     0    0    0    0    0    0    0    0   0                          

4     0    0    0    0    0    0    0    0   0    

 

1원 짜리 동전을 이용하여 1원 부터 9원까지 필요한 경우의 수를 각각 채워 넣는다. 1원을 만들기 위해 1원짜리 1개, 2원을 만들기 위해 1원짜리 2개가 필요하며, 9원을 만들기 위해서는 9원이 필요하다.

 

       1    2    3    4    5    6    7    8    9

1      1    2    3    4    5    6    7    8    9

3     0    0    0    0    0    0    0    0   0                          

4     0    0    0    0    0    0    0    0   0    

 

3원 짜리 동전을 이용하여 같은 방법으로 채워 넣는다. 3원 짜리 동전을 만들기 위해 3원짜리 1개, 4원은 3원짜리 1개, 1원짜리 1개가 필요하다.

 

        1    2    3    4    5    6    7    8    9

1      1    2    3    4    5    6    7    8    9

3     1    2    1    2    3    2    3    4    3                            

4     0    0    0    0    0    0    0   0    0    

 

4원도 같은 방법으로 채워 넣으면 최종은 다음과 같다.

 

       1    2    3    4    5    6    7    8    9

1     1    2    3    4    5    6    7    8    9

3    1    2    1    2    3    2    3    4    3                          

4    1    2    1    1    2    2    3     2    3                

 

여기서 코드 구현을 위해 4원짜리가 채워지는 방법을 조금 깊게 들여다 보자. 세로열의 값들은 거스름 돈을 구성하기 위한 동전의 갯수를 의미한다. 즉, 1원 짜리는 1개, 2원짜리는 2개, 3원짜리는 1개가 필요하다는 것을 의미한다.

5원 : 4원 + 1원,     6원 : 4원 + 1원 + 1원,      7원 : 4원 + 3원이 필요한데, 5-4를 빼면 1원을 만들기 위한 갯수가 나오고, 6-4를 하면 2원을 만들기 위한 갯수가 나온다. 이를 코드로 표현하면 다음과 같다.

 

// 먼저 check 배열을 Integer.MAX_VALUE로 초기화한다. 

check = new int[m + 1];
for(int i = 1; i <= m; i++) {
	check[i] = Integer.MAX_VALUE;
}

for(int coin : coins) {
        check[coin] = 1;
        for(int idx = coin; idx <= m; idx++) {
        check[idx] = Math.min(check[idx], check[idx-coin] + 1);
}