용's

이전 포스팅에서는 Change Making 문제를 다뤘다. 이번 동적 프로그래밍 문제에서는 '주어진 동전의 종류를 이용하여 목표치(W)를 만드는 경우의 수 카운트' 문제를 풀어보도록 한다. 알고리즘을 단번에 생각해내기가 상당히 어렵다. 차근차근 이 문제를 접근해보자 예를 들어 설명하는 것이 가장 빠를 듯 하다. 1원 2원을 이용하여 4원(W)을 만드는 경우의 수는 몇 가지인가? 1+1+1+1 = 4 2+1+1 = 4 2+2 = 4 이렇게 총 3가지가 된다. 1원 2원을 이용하여 5원(W)을 만드는 경우의 수는 몇 가지인가? 1+1+1+1+1 = 5 2+1+1+1 = 5 2+2+1 = 5 이렇게 총 3가지가 된다. 자세히 보면, 1원으로 W를 만드는 경우의 수 + 2원을 이용하여 W를 만드는 경우의 수로 ..

change making problem [https://en.wikipedia.org/wiki/Change-making_problem] 위키피디아에서 알 수 있듯이 이 문제는, '주어진 동전의 종류를 조합하여 목표 금액을 만들고자 할 때, 최소의 동전 개수를 구하는 문제' 예를 들면, 다음 문제와 같다. '1원 5원 10원을 가지고 15원을 만들고자 할 때, 15원을 만드는 조합 중 최소의 동전 개수는?' Greedy한 방식으로도 풀 수 있지만 이 문제는 가장 기초적인 동적 프로그래밍(Dynamic Programming)로 해결할 수 있는 문제 중 하나이다. 아이디어는 다음과 같다. 1원이 포함된 n가지 동전으로 W원을 만들고자 할 때, W원을 만드는 최소의 동전 개수는 다음 두가지 경우의 수 중 최소값..

순열을 만드는 아이디어는 다음과 같다 N Permutation 1 a 2 ba ab 3 cba bca bac cab acb abc ... ... 표를 자세히 보면 N이 1에서 2가 될 때, a를 사이에 두고 b가 앞 뒤쪽으로 하나씩 생겨 2개의 순열이 생겨났다. N이 2에서 3이 될 때, O b O a O 의 O에 c가 하나씩 생겨 3개의 순열이, O a O b O 의 O에 c가 하나씩 생겨 3개의 순열이 생겨 총 6개의 순열이 생겼다. 여기서 ba, ab는 N=1 -> N=2로 될 때 만들어 진 것. 따라서 Recursive Call 방법으로 순열을 만들 수 있을 것이다. (N! 이면, '(N-1)!은 내가 만드니 N만 니가 처리해줘' 라는 방식) 코드를 짜봤지만, 그 다지 깔끔한 코드가 아닌 듯 하다..