다이나믹 프로그래밍 문제 관련 질문 드립니다.

Question

dp 문제 중 효율적인 화폐 구성이라는 문제가 있는데요. k개의 화폐로 n원을 만들 때 가작 작은 화폐 개수를 구하는 문제입니다.예를 들어, k &#61; 2, 3, 5로 구성되어 있고, n &#61; 7, 정답이 a(n)이라면,7 &#61; 2 &#43; 5이므로, a(7) &#61; 2 개가 되는 문제입니다. 여기서 점화식은 a(n) &#61; min( a(n), a(n-k) &#43; 1 ),a(n-k) &#43; 1: 화폐 k원을 반드시 사용하는 경우를 의미위의 예시에 점화식을 적용해본다면, 시작 전 a(n)을 모두 INF 값으로 초기화,a(7) &#61; min( a(7), a(7-2)&#43;1, a(7-3)&#43;1, a(7-5)&#43;1 ) &#61; min( a(7), a(5)&#43;1, a(4)&#43;1, a(2)&#43;1 ) 여기까지는 이해가 됐습니다.근데 설명이나 코드를 보면 반복문의 위치가 제가 생각한거랑 반대로 돼있더라구요ㅠㅠ저는 n에 대한 루프 안에 k의 루프가 와야 위의 점화식과 같은 방식이 된다고 생각했지만,설명에서는 k &#61; 2일 때 n&#61;0~7까지 a(n)을 쫘르륵 구하고, 그다음 k &#61; 3일 떄 쫘르륵, 마지막 k&#61;7일 때 쭉 구해서 최종답을 구합니다.제가 이해한 바로는, &#34;dp의 핵심은 작은 문제의 정답은 이미 구해져 있다고 가정한다.&#34; 즉, a(7-2), a(7-3), a(7-5)가 이미 구해져 있고 거기서 비교해서 작은 값을 고르는 개념이라고 생각했습니다.하지만 k 루프가 바깥에 있으면 k&#61;2일 때 a(7)은 INF가 되지만, 만약 k&#61;5일 때를 먼저 구하고나서 k&#61;2일 때를 구해보면 a(7) &#61; 2가 됩니다.이런 식으로 순서에 영향을 받게 되니까 k 루프가 바깥에 있으면 안될 거 같다는 생각이 들었습니다. 하지만 실제로는 왜 반복문 위치가 이렇게 바뀌는 건가요?? 제가 뭔가 잘못 생각하고 있는 걸까요?아시는 분 답변 주시면 공부하는데 정말 큰 힘이 될 거 같습니다ㅠㅠ감사합니다.

monotonicity · Answer

각 화폐를 최대 한번만 사용할수 있는건가요? 문제 요구사항에 따라 달라집니다.

monotonicity · Answer

한번만 사용할수 있다면 k에 대한 루프가 밖에 있는것과 동시에 n루프도 역순으로 돌려야 합니다 (0-1 knapsack 문제).그게 아니라면 k 루프가 밖에 있던 안에 있던 상관 없습니다.

야4885 · Answer

&#64;monotonicity답변 남겨주셔서 정말 감사합니다. 화폐는 여러번 사용할 수 있습니다.혹시 k루프 위치가 관계 없는 이유가 무엇인가요? 저는 k루프가 밖에 있으면 k를 2부터 확인하는지, 5부터 확인하는지에 따라서 k &#61; 2일때의 a(7)의 값이 달라지니까, 바깥에 있으면 안될 거 같다는 생각이 듭니다. 예를 들어서, k루프가 밖에 있을 때, k를 2부터 확인하면 k&#61;2일때의 a(7) &#61; a(5) &#43; 1 &#61; INF &#43; 1k를 5부터 확인하고 2를 확인하면 k&#61;2일때의 a(7) &#61; a(5) &#43; 1 &#61; 2 하지만 k루프가 안에 있으면, k&#61;2일때의 k(7)의 값이 항상 2가 되잖아요. 근데 어떻게 하든 결국 같은 결과가 나온다는 게 제 머리로는 이해가 안됩니다ㅠㅠ

다이나믹 프로그래밍 문제 관련 질문 드립니다.

3개의 답변

#dp 목록