인프런 동전교환 dp (1) 썸네일형 리스트형 [인프런 자바/java] 5. 동전교환(냅색 알고리즘) _디버깅의 눈물 체크 포인트 1. 다이나믹 프로그래밍(Dynamic Programming, 동적계획법)을 이용 -큰 문제를 여러 가지 작은 문제로 나누어 해결해보는 DP를 이용했다. -예시 1의 예를 들면, 3종류의 동전(1원, 2원, 5원)으로 15원을 만드는 최소의 동전개수를 구해야 한다. -동적 계획법에 따라, 작은 문제로부터 큰 문제에 대한 해결을 추론해 보았다. 1) 1원에서부터 15원까지 (1)1원, (2)1원+2원, (3)1원+2원+5원 세 가지 경우로 나누고, 구성할 수 있는 동전의 최소 개수를 구하며 규칙성을 찾아보았다. 해당 규칙성을 찾기 위해 M=0일 때는 동전의 종류에 상관없이 0을 입력했다. (1)1원을 이용한 동전의 최소 개수 M 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1.. 이전 1 다음