[Algorithm] DP - Coin change

안녕하세요 :)

개발자 sean입니다. 

휴가 다녀오고 오랜만에 포스팅을 하는 것 같습니다. 

2주간 코드는 거들떠 보지도 않고 놀다 오니 코드 감각이 떨어진 듯하여 오늘은 감을 끌어올릴 겸 dp 문제를 풀어보았습니다. 

아니나 다를까 코딩 실력이 default로 돌아갔더군요...

 

 

The Coin Change Problem이란 문제를 풀어보았는데 결국에는 못풀어서 다른 사람의 풀이를 참고해 풀었습니다. 

이럴 땐 정말 자괴감이 들곤 합니다만 뭐 어쩌겠습니까 배울 것이 많이 남아 있다는 건 성장할 수 있는 여지가 많이 남아있다는 것이고, 

또 어플만드는데는 전혀 문제가 되지 않는걸요 껄껄.. ㅠㅠ

 

그래도 포기하지 않고 끝까지 풀이에 성공한것을 위안 삼아 멘탈 잡고 한번 풀이를 해보도록 하겠습니다. 

 

제가 풀이한 정답은 아래와 같습니다. 

 

function getWays(n, c) {
    // Write your code here
    const memo = Array.from(Array(c.length + 1), () => new Array(n+1).fill(-1));
    
    const recursive = (row, column) => {
        if (column === 0) return memo[row][column] = 1;
        if (row === 0) return 0;        
        if (memo[row][column] !== -1) return memo[row][column];
        
        if (c[row-1] <= column) {
            return memo[row][column] = recursive(row, column - c[row-1]) + recursive(row - 1, column);
        } else {
            return memo[row][column] = recursive(row - 1, column);
        }
    }
    
    recursive(c.length, n);
    
    return memo[c.length][n];
}

 

우선 이 문제는 대놓고 다이나믹 프로그래밍 문제라고 적혀있습니다. ㅎㅎ 

 

여기서 다이나믹 프로그래밍이라고 한다면 이해하기가 다소 어려울 수 있습니다. 서울대 교수님께서는 저서에서 이를 '기억하기 프로그래밍'으로 설명한다고 하신다던데 개인적으로 이게 더 와닿는 것 같습니다. 

 

메모라이제이션이든 어떤 방법으로 똑같은 결과가 나오는 값을 '저장해' 사용하는 것이 중요합니다. 

 

따라서 맨 처음 줄에 이전의 값을 저장할 memo 배열을 아래와 같이 준비해 주었습니다. 

    const memo = Array.from(Array(c.length + 1), () => new Array(n+1).fill(-1));

Array.from을 사용하니 map과 같이 구구절절이 적지 않아 편하네요 :)

 

이렇게 되면 아래와 같은 테이블이 하나 만들어 집니다. 

	column1	column2	column3	column4	column5
row1	-1	-1	-1	-1	-1
row2	-1	-1	-1	-1	-1
row3	-1	-1	-1	-1	-1

 

여기서 저는 Top-down 방식을 이용해 문제를 풀어보려고 합니다. 

별다른 이유는 없고 그냥 재귀함수를 호출해 dp를 푸는게 익숙하기 때문입니다. 

 

만약에 n이 4이고 c가 {1,2,3}이라고 가정해 보겠습니다.

 

그렇다면 위의 표는 아래와 같이 생각해 볼 수 있겠습니다. 

	0	1	2	3	4
0	-1	-1	-1	-1	-1
1	-1	-1	-1	-1	-1
2	-1	-1	-1	-1	-1
3	-1	-1	-1	-1	-1

여기서 행과 열의 의미를 이해하는 것이 중요합니다. 

행은 조합할 수 있는 동전의 종류를 의미하고 열은 동전의 종류를 조합해 만들 수 있는 금액을 의미합니다. 

예를 들어 memo[1][1]이란 동전 하나를 이용해 1원을 만들 수 있는 방법의 수를 의미하는 거죠. 

 

여기까지는 다른 분들이 이렇게 설명을 하고 있긴한데 제가 생각하기엔 정확하게 옳은 표현은 아닌 것 같습니다.

저는 위 표를 아래와 같이 약간 변형을 해보았습니다. 

	0	1	2	3	4
0: []	-1	-1	-1	-1	-1
1: [1]	-1	-1	-1	-1	-1
2: [1,2]	-1	-1	-1	-1	-1
3: [1,2,3]	-1	-1	-1	-1	-1

제가 생각하기에 옳은 표현으로 다시 설명해 보겠습니다. 

 

열의 []란 아무 동전을 조합하지 않았을 때 만들수 있는 금액의 경우의 수이며. 

[1]은 1원 짜리를 조합했을 때, 

[1,2]는 1원과 2원을 조합했을 때입니다. 

 

따라서 우리가 구해야하는 값은 1원 2원 3원 모두를 조합하여 4원을 만들 수 있는 경우의 수 바로 memo[3][4]입니다.

 

memo[3][4]는 한 번 더 나누어 생각해 볼 수 있습니다. 

 

1원 2원 3원을 조합해 4원을 만들 수 있는 경우의 수 =

1원 2원을 조합해 4원을 만들 수 있는 경우의 수 + 1원 2원 3원을 조합해 1원을 만들 수 있는 경우의 수

 

이 부분이 약간 헷갈릴 수 있습니다. 

 

1원 2원을 조합해 4원을 만들 수 있는 경우의 수는 이해가 되는데 1원 2원 3원을 조합해 1원을 만들 수 있는 경우의 수 이부분이 저는 헷갈렸습니다. 생각해 보면 간단합니다. 3원을 더해서 4원을 만들어야 한다고 한다면 1원에 3원을 더하는 방법밖엔 없겠죠. 그렇다면 1원을 만드는 방법의 수가 곧 3원을 더해서 만들 수 있는 방법의 수가 되는 것입니다. 

 

다음부터는 지루한 초기화 작업과 예외처리를 해주시면 됩니다. 

 

코드를 천천히 읽으면 아마 이해가 다들 되시리라 생각됩니다.