파이썬 알고리즘 인터뷰 다이나믹 프로그래밍 간단 정리

다이나믹 프로그래밍

• 다이나믹 프로그래밍 (Dynamic Programming, DP) 문제를 각각의 작은 문제로 나누어 해결한 결과를 저장해뒀다가 나중에 큰 문제의 결과와 합하여 풀이하는 알고리즘 예로 0-1 배낭 문제, 피보나치 수열, 다익스트라 알고리즘이 있음
  • 특징 최적 부분 구조와 중복된 하위 문제들이 있어야 함
    • 최적 부분 구조 매 순간의 답이 최적의 답이 되는 구조 최적 부분 구조가 아닐 경우 분할 정복, DP, 그리디로 풀이할 수 없음
    • 중복된 하위 문제들 반복적으로 동일한 하위 문제들이 발생하는 경우 중복 문제가 발생하지 않는 경우 병합 정렬은 분할 정복으로 분류됨
  • 방법론 방식에 따라 크게 상향식, 하향식으로 나뉨
    • 타뷸레이션 상향식 접근 방법 더 작은 하위 문제부터 살펴본 다음, 작은 문제의 정답을 이용해 큰 문제의 정답을 풀어나감
    • 메모이제이션 하위 문제에 대한 정답을 계산했는지 확인해가며 문제를 자연스러운 방식으로 풀어나감