동적 프로그래밍 기초


난이도 쉽게
자주 묻는 질문 인포시스 MAQ
동적 프로그래밍 이론

동적 프로그래밍 기초에서는 DP의 기초와 Greedy 방법, Divide and Conquer and Recursion과의 차이점을 다룹니다.

동적 프로그래밍은 재귀와 분할 및 정복과 같은 접근 방식입니다. 문제를 하위 문제로 나눕니다. 그러나 분할 및 정복 및 재귀와 같이 이러한 하위 문제를 독립적으로 해결하는 대신 중복 문제라고도하는 유사한 계산에 이전 하위 문제의 결과를 사용합니다.

프로그램 최적화에 사용됩니다. 이전에 계산 된 결과를 사용하므로 지수 시간 복잡도를 사용하여 다항식으로 줄일 수 있습니다. 예를 들어-Ugly Numbers의 재귀 솔루션의 시간 복잡도는 지수 적이며 DP 솔루션의 시간 복잡도는 선형입니다.

DP의 몇 가지 기본적인 문제

  • 못생긴 숫자 문제
  • 동전 변경
  • 피보나치 수
  • 벨 숫자 문제
  • 하노이의 탑
  • 벨 번호
  • 배낭 문제

동적 프로그래밍 (DP) 대 Greedy 방법

DP에서 각 단계는 최적의 솔루션을 얻기 위해 현재 솔루션과 이전 솔루션을 고려하여 솔루션을 평가합니다. 하지만 욕심쟁이 알고리즘에서는 현재 상황만을 고려하여 최적의 옵션을 선택합니다.

탐욕스러운 방법은 일반적으로 DP보다 빠르며 향후 사용을 위해 이전에 계산 된 값을 저장하지 않기 때문에 메모리 효율성도 높지만 최적의 솔루션을 보장하지는 않습니다.

동적 프로그래밍 (DP) 대 분할 및 정복 방법

나누기와 정복에서 우리는 문제를 하위 문제로 나누고 각 하위 문제를 독립적으로 해결합니다. 그러나 DP에서는 문제를 독립적으로 해결하기보다는 이전에 얻은 결과를 새로운 계산에 사용합니다. 즉, Divide and Conquer + Memoization = 하향식 동적 접근이라고 말할 수 있습니다.

(Memoization은 이전에 계산 된 결과를 일반적으로 해시 맵에 저장하여 동일한 문제를 반복해서 계산하는 것을 방지하는 기술을 말합니다.)

동적 프로그래밍 (DP) 대 재귀 방법

DP는 이전에 계산 된 솔루션을 저장하여 재 계산을 방지하기 위해 나중에 다시 필요할 때 사용합니다. 그러나 재귀에서는 값을 저장하지 않기 때문에 불필요한 재 계산이 발생할 가능성이 있습니다.

재귀는 문제를 여러 번 재 계산하므로 이러한 경우 재귀의 시간 복잡성은 항상 DP 솔루션보다 큽니다.

이 기사에서 우리는 동적 프로그래밍 기초. 다음 기사에서는 DP에 대한 몇 가지 기본적인 문제를 다룰 것입니다.

참고 면접 질문