c++/ 자료구조&알고리즘 개념 복습하기 - 17 / 다이나믹 프로그래밍 (DP), min 함수

DP

• 여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘

• DP는 기본적으로 문제를 나누고 그 문제의 결과 값을 재활용해서 전체 답을 구한다. 그래서 동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능하다.

• 즉, DP는 부분 문제의 결과를 저장하여 재 계산하지 않을 수 있어야 하는데, 해당 부분 문제가 반복적으로 나타나지 않는다면 재사용이 불가능하니 부분 문제가 중복되지 않는 경우에는 사용할 수 없다.
  (참고링크 - https://hongjw1938.tistory.com/47)

---

DP를 푸는 과정

• 1. 테이블 정의하기
• 2. 점화식 찾기
• 3. 초기값 정하기

---

< 예제 >

BOJ - 1463
https://www.acmicpc.net/problem/1463

• 1. 테이블 정의
     D[i] = i를 1로 만들기 위해 필요한 연산 수의 최솟값
     
     
• 2. 점화식 찾기
     D[k] = ?
     k가 3으로 나누어지면 D[k] = D[k/3] + 1
     k가 2로 나누어지면 D[k] = D[k/2] + 1
     1을 빼는 경우는 D[k] = Dl[k-1] + 1

이 셋 중에서 최솟값이 정답!!

• 3. 초기값 정의하기
     D[1] = 0

---

min, max, minmax

참고링크 : https://notepad96.tistory.com/57

• min, max, minmax 는 algorithm 라이브러리에 포함!!