화폐로 알아보는 경우의 수(feat. Dynamic Programming) (TIL 73일차)
"가상화폐 시대의 지폐 알고리즘"
Intro
오늘은 알고리즘 문제를 풀어가는 과정을 블로깅 해보려고 합니다. 접하는 알고리즘이 대부분 코드스테이츠의 과제와 관련이 있다 보니, 알고리즘을 풀더라도 가급적 블로깅은 하지 않는 편인데요. 이번 문제는 레퍼런스 코드로 제시된 풀이가 이제까지 경험해보지 못한 방식이어서, 블로깅을 통해 제것으로 만들어보려는 의도에서 풀이를 쓰게 되었습니다.
문제를 그대로 옮겨적지는 않았습니다만 알고리즘 코플릿과 관련한 힌트가 제법 담겨있는 편이니, 스포일러가 싫으시다면 여기에서 멈춰주셔도 괜찮습니다.
풀이에 앞서 사족을 달자면, 신용카드, **페이, 그리고 가상 화폐가 등장한 이 시점에 화폐를 다루는 문제가 과연 어울리는 것인가 하는 쓸데 없는 고민이 들었습니다. 어쩌면 5년, 10년만 지나도 문제를 바꿔야 하는거 아닌가 싶은...
문제
화폐의 종류가 담긴 배열 money 와 만들어야 하는 총 금액 amount 가 있을 때, money 에 담긴 화폐들로 amount 를 만들 수 있는 경우의 수는 모두 몇 개나 될까요?
조금 더 구체적인 예시로 위의 문제를 풀어보면 이렇습니다. 만약 당신에게 1원, 2원, 5원이라고 하는 3가지 종류의 화폐가 있습니다. 이를 이용해서 5원이라는 금액을 만들어야 한다면, 경우의 수는 모두 몇 개일까요?
구체적인 예시를 대입해보면 1원, 2원, 5원이 담긴 배열이 money가 되고, 5원이라는 금액이 amount 가 되겠죠. 이를 코드로 적어보면 다음과 같습니다.
let money = [1, 2, 5];
let amount = 5;수도코드
코드를 작성하기에 앞서 5원을 만들 수 있는 경우의 수가 몇 개인지를 생각해봅시다.
(1) 1원짜리 화폐를 5개 사용할 수도 있고,
(2) 1원짜리 하나와 2원짜리 2개,
(3) 1원짜리 3개와 2원짜리 1개,
(4) 5원짜리 하나,
이렇게 총 4 개의 경우의 수가 있겠네요.
처음에는 1원짜리가 하나일 때 2원짜리와 5원짜리를 조합해 5원을 만들 수 있는 경우의 수를 찾아보고, 그 다음에는 1원짜리가 2개일 때, 3개일때, 이렇게 차례로 수를 늘려가며 찾는 방법을 생각했었습니다. 그러려면 중첩된 반복문이나 재귀를 활용해야 되겠다고 생각했었죠.
여러가지로 도전하다가 레퍼런스 코드를 보게 되었는데, 아니 이건?! 진짜 이런 알고리즘은 배워야만 알 수 있는 알고리즘인 것 같아요. 그래서 그 풀이 과정을 코드와 함께 정리해보려고 합니다.
코드와 풀이 과정
처음부터 하나씩 풀어가다가 너무 늘어지는 것 같아 과감히 지우고, 코드 그 자체로 이해할 수 있는 부분들은 간단하게만 정리했습니다.
let money = [1, 2, 5];
let amount = 5;
let arr = new Array(amount + 1).fill(0);
// [0, 0, 0, 0, 0, 0]; 0부터 amount 5까지의 index 를 갖는 배열
arr[0] = 1;
for(let i = 0; i < money.length; i++) {
for(let j = 1; j < arr.length; j++) {
if(money[i] <= j) {
arr[j] = arr[j] + arr[j - money[i]];
}
}
}
console.log(arr[5]); // 5 원을 만드는 경우의 수는?
arr 은 주어진 종류의 화폐들로 만들 수 있는 경우의 수를 저장하기 위한 배열이라 0으로 초기화해줍니다. arr 배열의 index 가 만들 수 있는 금액이 되는 개념이죠. arr[0] 을 1로 설정해주는 것은 이 알고리즘이 작동할 수 있도록 하는 기초값입니다. 이 지점은 if 문 내부를 이해할 때 다시 한 번 살펴보겠습니다.
바깥의 for 문은 화폐의 종류를 순차적으로 반복하고, 안쪽의 for 문은 그 화폐로 금액을 만들 수 있는 경우의 수를 위한 반복문입니다. 예시를 기준으로 하면 1원부터 5원까지 1원짜리만 써서 만들 수 있는 경우의 수를 먼저 저장하고, 다음으로 2원짜리로 만들 수 있는 경우의 수를 저장하고, 마지막으로 5원짜리로 만들 수 있는 경우의 수를 저장하는 것이죠.
if(money[i] <= j) {
arr[j] = arr[j] + arr[j - money[i]];
}조건문 내부의 이 코드가 제가 블로깅을 해야겠다고 생각한 이유입니다. 제 생각에는 이 알고리즘의 핵심이라고 보이는데요. 바로 arr[j] 를 만들 수 있는 경우의 수를 할당할 때, 기존의 경우의 수 + arr[ j - money[i] ] 를 해주는 것입니다.
예시를 가지고 차근차근 살펴보겠습니다. money[i] 가 1원짜리인 경우에는 모든 경우의 수가 1이 됩니다. 실제로 1원짜리로 1원부터 5원까지의 금액을 만드는 경우의 수는 모두 1이 되겠죠. 2원짜리일 때를 생각해보면 왜 코드가 이렇게 동작할 수 있는지를 이해할 수 있습니다.
// 0, 1, 2, 3, 4, 5 <= arr 의 인덱스
// arr = [1, 1, 1, 1, 1, 1]; j === 1 일 때, 다시 말해 2원짜리로 1원을 만드는 경우의 수는 불가능하니 조건문에서 걸러지고 j === 2 일 때부터 조건문 내부의 코드가 실행되겠네요. 2원짜리로 2원을 만드는 방법은 2원짜리 하나를 사용하는 겁니다. 그러면 남은 금액은 0원이 되어 다른 경우의 수를 생각할 필요가 없습니다. 경우의 수가 1만큼 늘어나게 되죠. 앞서서 0원 이라는 인덱스에 1 이라는 경우의 수를 할당해준 이유가 여기에 있습니다.
j === 3 일 때도 마찬가지입니다. 우리는 2원짜리를 사용하는 경우의 수를 파악하고 있으니, 3원짜리를 만들때 2원짜리를 사용하면 어떻게 되는지를 알아야 합니다. 2원짜리를 하나 사용하면 1원이 남겠네요? 2원으로는 더 이상 1원을 만들 수 없지만, 1원짜리를 사용하면 3원이 만들어집니다. 그래서 1원을 만드는 경우의 수를 지금의 경우의 수에 더해주었습니다.
// j === 3 까지 반복문이 돌아갔을 경우
// 0, 1, 2, 3, 4, 5 <= arr 의 인덱스
// arr = [1, 1, 2, 2, 1, 1]; 저는 j === 4 까지 보고 나서야 알고리즘을 완전히 이해할 수 있었는데요. 키워드는 바로 만들어야 하는 금액에서 한 가지 화폐 하나를 무조건 사용할 경우 입니다.
4원을 만들어야 할 때, 2원짜리 하나를 무조건 사용한다고 정하면 어떻게 될까요? 그러면 2원이 남게 되니, 남은 2원을 어떻게 만들 수 있는지 경우의 수를 따져보면 될 것 같습니다. 이 때, 우리는 이미 2원을 만드는 경우의 수를 앞에서 찾았고 저장까지 해두었죠. 그 값을 더해주기만 하면 됩니다. 코드 상에서 arr[ j - money[i] ] 가 의미하는 바가 바로 이런 뜻인거죠.
// 반복문이 종료된 이후
// 0, 1, 2, 3, 4, 5 <= arr 의 인덱스
// arr = [1, 1, 2, 2, 3, 4];이 방법을 사용하면 깊게 재귀를 들어갈 필요 없이, 간단한 이중 반복문 만으로 우리가 원하는 결과를 찾을 수 있습니다. 반복문이 돌아간 이후 우리가 원하는 금액을 index로 해서 arr[index] 의 값을 불러오면 됩니다. 간결하면서도 효율적으로 원하는 결과를 찾을 수 있게 된 것이죠.
알고리즘 공부하는 꿀팁
코드스테이츠 크루 분에게 얻은 꿀같은 조언에 제 생각을 약간 첨가해 말씀드리자면, 일단 처음에는 무조건 잘 작성된 코드를 보는게 좋다고 생각합니다. 아예 모르는 개념을 뚝딱 코드로 풀어낼 수 있는 사람이라면 아니겠지만, 우리 대부분은 그런 사람이 아니니까요. 게다가 개발업계의 명언처럼 바퀴를 재발명할 필요는 없습니다.
그렇지만 잘 작성된 코드를 보고 그 다음으로 꼭 연계해서 해야하는 과정이 바로 잘 작성된 코드를 내 것으로 만드는 일입니다. 그냥 읽는게 아니라, 참고할 수 있는 코드를 멀리 치워둔 상태로 직접 코드를 다시 작성하면서 알고리즘을 풀어보는 것이죠. 눈으로만 보거나, 복붙해서 가져와서 쓰는 것은 의미가 없습니다. 참고자료 없이도 내가 알고리즘을 풀어내는 코드를 작성해나갈 수 있을 때 의미가 있어지는 거죠.
분명 누군가는 거인이 될 수도 있겠지만, 그게 아니라면 거인의 어깨에 올라타면 그만입니다. 이 편이 아주 많이 효율적인 것 같구요. 알고리즘을 풀다가 좌절하셨거나, 아예 알고리즘을 멀리 하고 계시다면 한 번 이렇게 공부방법을 바꿔보시는 건 어떨까요?
