Algorithm/문제풀이
[백준/Swift] 2294 동전 2
문제 정보 문제 출처: 백준 온라인 저지 문제 링크: 2294 동전 2 제출 언어: Swift 알고리즘 분류: 다이나믹 프로그래밍 풀이 다이나믹 프로그래밍 전체 문제의 최적해가 부분 문제의 최적해로부터 만들어지는 알고리즘이다 하나의 문제를 단 한 번의 연산으로 해결하기 위해, 즉 전체 문제를 풀 때, 동일한 계산을 반복하지 않기 위해 Table에 부분문제의 solution을 저장한다 항상 최적의 해를 보장하지만 Table에 부분문제의 solution을 저장하므로 많은 메모리를 차지한다 알고리즘 설계 해당 문제의 예시로 dp 배열을 생성해보면 다음과 같다. dp[0] = 0 dp[1] = 1 (1) dp[2] = 2 (1+1) dp[3] = 3 (1+1+1) dp[4] = 4 (1+1+1+1) dp[5] ..
