알고리즘/동적 계획법 (DP)
[이코테] 실전 문제
DP 문제는 수식을 생각해 줘야하는데 어려운 문제에서는 그게 참 어렵다. 책의 실전 문제에서는 아직 엄청나게 어려운 문제는 없었다. 1로 만들기 주어진 정수 X를 1로 만드는 연산의 최소 횟수를 구하는 문제였다. 연산 종류 X%5 == 0 이면 5로 나누기 X%3 == 0 이면 3으로 나누기 X%2 ==0 이면 2로 나누기 X - 1 하기 DP 문제를 풀 때는 초깃값을 설정할 수 있는 것은 설정하고, 나머지는 가장 큰 값으로 채우거나 비워놓아야 한다. 이 문제에서는 1,2,3,5 index의 값을 1로 설정할 수 있다. 문제의 수식은 4번째 값을 구할 때 찾아낼 수 있다. dp[4] = min(dp[4-1]+1 , dp[4/2]+1) 연산을 할 수 있다면 dp[연산 결과]+1을 비교해 최솟값을 찾아내는 ..
