[알고리즘] DP (Dynamic Programming, 동적 계획법)

문다연·2023년 1월 4일
0

dev.moon

목록 보기
2/3
post-thumbnail

다이나믹 프로그래밍

큰 문제를 반복되는 작은 문제로 나누어 해결하는 방법


다이나믹 프로그래밍은 다음의 가정 하에 사용할 수 있다.

1. 큰 문자를 반복되는 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

즉, 크고 어려운 문제가 있으면 먼저 잘게 나누어 해결한 뒤에 나중에 전체의 답을 구하는 것이다.

분할 정복 기법과 유사하나, 메모이제이션 Memoization이 사용된다는 점에 분할 정복과 다르다. 분할 정복은 큰 문제를 해결하기 어려워 단지 작은 문제로 나누어 푸는 방법인데, 이 작은 문제 간 반복이 없다는 특징이 있다.

반면 다이나믹 프로그래밍은 반복되는 모든 작은 문제들을 한번만 풀어야 한다. 따라서 정답을 구한 작은 문제를 메모하고, 다시 그보다 큰 문제를 풀 때 똑같은 작은 문제가 나타나면 앞서 메모해두었던 작은 문제의 결과값을 이용한다. 이를 메모이제이션 Memoization이라고 한다.


함께 풀어볼만한 DP 문제

BOJ 24416. (Bronze 1) 알고리즘 수업 - 피보나치 수 1
BOJ 11048. (Silver 2) 이동하기

Ref.

https://blog.naver.com/ndb796/221233570962
https://galid1.tistory.com/507

profile
ios-moon.tistory.com 이전했어요 🚛

0개의 댓글