
[이코테] 다이나믹 프로그래밍(Dynamic Programming)
·
PS/이코테
다이나믹 프로그래밍이란? 큰 문제를 작은 문제로 쪼개고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다.다이나믹 프로그래밍을 구현하는 방법에는 작은 문제를 재귀적으로 호출하는 방식인 Top-Down(하향식)작은 문제부터 하나씩 해결해나가면서 답을 도출하는 방식인 Bottom-Up(상향식)예제 1) 1로 만들기정수 X가 주어지고 다음 연산을 적절히 사용해서 1을 만드려고 할 때, 연산을 사용하는 횟수의 최솟값을 출력하시오.- X가 5로 나누어 떨어지면, 5로 나눈다. - X가 3로 나누어 떨어지면, 3로 나눈다. - X가 2로 나누어 떨어지면, 2로 나눈다. - X에서 1을 뺀다. 문제 해설Bottom-Up 방식 사용문제의 규칙을 찾아보면 다음과 같다.f(1) = 0f(2) =..