[실전 알고리즘] 0x10강 - 다이나믹 프로그래밍

1. 알고리즘 설명 다이나믹 프로그래밍(Dynamic Programming, DP) - 여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘 문제를 해결하기 위한 점화식을 찾아낸 후 점화식의 항을 밑에서부터 차례로 구해나가서 답을 알아내는 형태의 알고리즘이다. dp를 푸는 과정 1. 테이블 정의하기 2. 점화식 찾기 3. 초기값 정하기 2. 연습 문제 BOJ 1463번: 1로 만들기 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 1. 테이블 정의하기 d[i] = i를 1로 만들기 위해 필요한 연산 사용 횟수의 최솟값 2. 점화식 찾기 d[12] = ? 3으로 나누거나 (d[12] = d..

2022.02.23