[동적 계획법 1]

동적 계획법 (Dynamic Programming)

• 별표 5개!
• 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 문제.
• 작은 문제에 대해 저장한다는 점이 가장 중요! -> 메모이제이션(Memoization)
• 재귀와는 달리 저장하여 불러오므로 메모리는 사용하지만 실행 속도에서 매우 큰 장점을 가짐.

간단한 예시 1
피보나치 함수

• 피보나치는 앞에서 재귀로 구현한 적 있지만
• n이 일정 수준을 넘어가는 경우, 실행 속도의 문제로 사용이 불가능
• 이럴 경우, 저장을 통해 속도를 비약적으로 상승 가능!

간단한 예시 2
길 찾기

• 5*5의 길에서 [0][0]의 위치에서 [4][4]의 위치로 가려고 함.
• 가는 길마다 걸리는 시간이 다르다면 가장 빠른 시간에 도착하는 방법은 ?
• 이를 해결하는 방법이 동적 계획법!
• 각 위치마다 저장한 길들의 최솟값을 인용하여 계산
• 참고 블로그

유명한 예시 1 LCS

• 1차원 배열들에 대해 2차원 배열로 생각할 수 있을까 ?
• 관련 문제 : 백준 9251. LCS

유명한 예시 2 배낭에 물건 담기

• 제한된 무게 안에서 최대의 가치 담기!
• 관련 문제 : 백준 12865. 평범한 배낭
• 추가로, 물건을 쪼개서 넣을 수 있다면은 어떻게 될까 ?

관련 문제

• 백준 14단계. 동적계획법 1