Dynamic Programming - Concept

 

 

 

해당 문제는 "이것이 코딩 테스트이다" 책을 참고하여 제작하였습니다.

 

다이나믹 프로그래밍(DP)

- 메모리 공간을 더 사용해 연산속도를 늘리는 방법

- 탑다운, 보텀업

- 메모이제이션(캐싱)

 

 

다이나믹 프로그래밍을 사용할 수 있는 조건

- 큰 문제를 작은 문제로 나눌 수 있다.

- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

"예전에 구한 값이 지금 구하는 연산에 영향을 주는 경우에 이를 기록해놓는 메모이제이션을 통해 DP를 구현한다."

 

 

탑다운

- 큰 문제를 해결하기 위해 작은 문제를 호출한다.

- 메모이제이션

- 재귀함수를 이용해 구현

 

보텀업

- 작은 문제에서부터 차근차근 답을 도출한다.

- DP 테이블

- 반복문을 이용해 구현

 

유형 정리

- 예전에 구한 값들이 지금 계산할 값에 영향을 줄 때 !

- 점화식을 만들어서 구현한다.