DP란?

작은 값을 통해 더 큰 문제의 답을 계산하여 구하는 과정을 반복하여 최종적인 답까지 도달하는 과정

언제 DP로 문제를 접근하여 해결하면 좋을까?

1. 큰 문제를 작은 문제로 나눠서 푸는 알고리즘(예:피보나치 수)
2. Overlapping Subproblem(큰 문제와 작은 문제를 같은 방법으로 풀 수 있음), Optimal Substructure(문제의 정답을 작은 문제에서 풀 수 있음)
   • 혼합 제외, 어떤 항을 구하기 위한 전 항들을 완벽히 구할 수 있고, 그 항들을 이용하여 정의의 맞는 현재 항이 깔끔하게 정의가 될 때이다.
   • 다이나믹 프로그래밍. 한국어로 동적 계획법을 이용해 풀어야 하는 문제이다. 동적 계획법은 상향식과 하향식이 있는데, 처음 두 수를 알기 때문에 상향식으로 문제를 풀었다. 상향식은 제일 작은 인덱스의 수 부터 목표하는 값으로 향하는 것이고, 하향식은 맨 위의 값에서 재귀로 제일 작은 인덱스를 향하는 것이다. 이 동적 계획법이 최솟값을 구하는 면에서 그리디 알고리즘이랑 뭐가 다른가 싶었는데, 그리디 알고리즘은 내가 생각한 처음 최적의 방법이 끝까지 반례 없이 적용이 되는 경우에 이용하고, 동적 계획법은 가능성을 모두 두고 그 안에 최솟값을 찾을 수 있기 때문에 뭔가 그리디와 브루트포스의 중간 같은 느낌이다.

     Process of soloving DP

3. 문제 탐색
4. DP 식세우기
5. 검증 및 구현

Example of DP problem

1로 만들기(백준 & 이것이 코딩테스트다)

모르겠으면 일단 수를 나열해봐라

• 1->0
• 2->1
• 3->1
• 4->2
• 5->3
• 6->2
• 7->3
• 8->(7or4)->(7[3],4[2])->4’check’->3 즉, 일단 나열해보니, 규칙이 보인다. 현재 값 cur = min(cur/3,cur/2,cur-1) + 1 –> 점화식이면 dp!!
• python이면 bottomup이 좋다.

  def solve():
    n = int(input())
    arr = [0,0,1,1]
    for i in range(5,n+1):
        one,two,three = math.inf,math.inf,arr[i-1]
        if i % 3 == 0:
            one = arr[i//3]
        if i % 2 == 0:
            two = arr[i//2]
        arr.append(1+min(one,two,three))
    print(arr[n])