ndb796
p314 만들 수 없는 금액 문제 질문 있습니다!
-
해당 문제의 풀이인 p511의 step3에서 화폐 단위 3인 동전으로 target을 4에서 7로 업데이트 하는 부분이 이해되지 않습니다. 어떤 부분 때문에 1부터 6까지의 모든 금액을 만들 수 있다는 정당성을 얻을 수 있나요?
-
또한 그리디 알고리즘이 현재 상태에서 매번 가장 좋아 보이는 것만을 선택하는 알고리즘이라고 배웠는데 해당 문제에서 매 상황에 어떠한 것을 선택하여 그리디 알고리즘으로 분류 되는 건가요??
제가 독해력이 부족하여 해당 문제 해설을 여러번 보았는데도 아이디어를 이해하지 못해 질문드립니다. 감사합니다.
현재 상태(State)에서 다양한 상태(경우)로 이동할 수 있는 상황에서, 현재 상태를 기준으로 특정한 조건에 따라서만 다음 상태로 이동(현재 상태에서 최적이라고 생각되는 것을 선택)하는 접근 방법을 이용한다면 그리디 알고리즘으로 분류할 수 있습니다.
책에서는 독자분들의 이해를 위하여, 현재 상태에서 특정한 조건에 따라 이동한다는 의미를 현재 상태에서 가장 좋아 보이는 것만을 골라서 이동한다고 쉽게 풀어 적었습니다.
정당성 분석에 관하여
우리는 현재 1부터 target - 1까지의 모든 금액을 빠짐없이 만들 수 있는 상태에서 그다음 금액에 해당하는 target도 만들 수 있는지 검사하기 위해 target이라는 변수를 사용합니다.
예를 들어 1, 2원짜리 동전이 있을 때 우리는 1원부터 3원까지를 빠짐없이 채울 수 있습니다.
| 만들고자 하는 금액 | 동전 조합 |
|---|---|
| 1원 | 1원 |
| 2원 | 2원 |
| 3원 | 1원 + 2원 |
이어서 3원짜리 동전이 더 있다고 해봅시다. 이때 1원부터 6원까지를 빠짐없이 채울 수 있게 됩니다.
이게 가능한 이유는 우리가 현재 1부터 target - 1까지의 모든 금액을 빠짐없이 만들 수 있으므로, 새로 확인하는 동전 x가 target 이하이기만 하다면 1부터 target + x - 1까지의 모든 금액을 빠짐없이 만들 수 있기 때문입니다.
그러면 여기에서 또 "왜 동전 x가 target 이하이기만 하다면 1부터 target + x - 1까지의 모든 금액을 빠짐없이 만들 수 있는가?"라는 궁금증이 생길 수 있습니다. 여기에 대해서도 답을 드리겠습니다.
새 동전 x가 있다면, 지금까지 만들 수 있었던 모든 금액에 x를 더해준 금액들도 모두 만들 수 있게 됩니다.
예를 들어 1원, 2원, 3원을 만들 수 있는 상태에서 3원짜리 동전이 더 있다고 하면, 우리는 4원, 5원, 6원 또한 만들 수 있는 것입니다.
단, x가 target보다 크다면 중간에 비는 금액이 생깁니다.
예를 들어 1원, 2원, 3원을 만들 수 있는 상태에서 5원짜리 동전이 더 있다고 하면, 우리는 5원, 6원, 7원, 8원 또한 만들 수 있습니다. 이때 5원짜리 동전 하나만 써도 되기 때문에 5원도 만들 수 있습니다. 하지만 전체 원소를 보면 {1원, 2원, 3원, 5원, 6원, 7원, 8원}으로서 4원이 비게 됩니다!
더 자세한 설명을 위해 조금 더 수학적으로 정당성 분석을 해봅시다. 우리가 가지고 있는 동전들(수열)을 coins라고 합시다. 이제 하나의 집합 possibles를 정의해 볼게요.
possibles = coins에서 원소 몇 개를 뽑아서 그것을 모두 더한 값을 원소로 삼는 집합
예를 들어 coins = [1, 2]라면, possibles = {1, 2, 3}이겠죠.
이제 possibles = {1, 2, 3, ..., target - 1}이라고 합시다. 이걸 현재 상태(State)라고 보아도 됩니다.
새로운 동전 x가 주어지면, 우리는 possibles의 각 원소에 x를 더한 값의 원소 집합인 {x, 1 + x, 2 + x, 3 + x, ..., target - 1 + x} 또한 만들 수 있다는 것은 자명합니다. 이때 x 하나만 써도 되므로 x 또한 집합에 포함됩니다.
이 두 집합을 나란히 적어 봅시다.
{1, 2, 3, ..., target - 1}와 {x, 1 + x, 2 + x, 3 + x, ..., target - 1 + x}입니다.
바로 여기에서, target >= x인 조건만 만족한다면
{1, 2, 3, ..., target - 1 + x}의 모든 원소(자연수)를 빠짐없이 가질 수 있다는 것을 알 수 있습니다!
알고리즘 유형에 관하여
마지막으로 이 문제가 왜 그리디 문제로 분류될 수 있는가에 대한 내용입니다.
현재 상태(State)를 1부터 target - 1까지의 모든 금액을 빠짐없이 만들 수 있는 상태라고 정의해보겠습니다. 이제 새로운 원소 x가 주어졌을 때, target >= x의 조건만 만족한다면 현재 상태를 1부터 target - 1 + x까지의 모든 금액을 빠짐없이 만들 수 있는 상태로 업데이트 할 수 있습니다.
본 알고리즘을 확인해 보면 현재 상태를 기준으로 특정한 조건만 고려하면서 (탐욕성) 현재 상태를 다른 상태로 이동합니다. 또한 그렇게 했을 때 최종적인 상태는 최적의 해가 됩니다. 그러므로 본 문제에서는 해당 그리디 알고리즘으로 해결할 수 있습니다.
그리디 문제는 직관적으로 풀이 방법을 떠올려서 해결하곤 합니다. 다만 엄밀한 수학적 정의로 그 정당성을 분석하는 것은 상당히 어려운 경우가 많습니다.
책에서는 최대한 수학적 개념을 적게 쓰고자 노력을 했습니다. 이 부분이 일부 독자분들에게는 오히려 이해에 방해가 되었던 것 같기도 합니다. 좋은 피드백 감사드리며, 답변이 도움이 되었으면 좋겠습니다.
감사합니다. 나동빈 드림
