알고리즘 유형: DP

윤뿔소·2022년 12월 10일
0

Algorithm

목록 보기
4/13

DP(동적 계획법)

하나의 문제는 단 한 번만 풀도록 하는 알고리즘
1. 주어진 문제를 여러 개의 (작은) 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법을 결합하여 최종 문제를 해결. 2. 하위 문제를 계산한 뒤 그 해결책을 저장하고, 3. 나중에 동일한 하위 문제를 만날 경우 저장된 해결책을 적용해 계산 횟수를 줄인다.

Dynamic Programming(DP, 동적 계획법)은 탐욕 알고리즘(Greedy)과 함께 언급하는 알고리즘으로, 줄임말로 DP 라고 하는 이 알고리즘은, 탐욕 알고리즘과 같이 작은 문제에서 출발한다는 점은 같다. 그러나, 탐욕 알고리즘이 매 순간 최적의 선택을 찾는 방식이라면, DP는 모든 경우의 수를 조합해 최적의 해법을 찾는다.

그리고 다이내믹 프로그래밍은 다음 두 가지 가정이 만족하는 조건에서 사용할 수 있다.

  • Overlapping Sub-problems : 큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제가 중복해서 발견된다.
  • Optimal Substructure : 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 같다. 즉, 작은 문제에서 구한 정답을 큰 문제에서도 사용할 수 있다.

예시

profile
코뿔소처럼 저돌적으로

0개의 댓글