Dynamic Programming : 개요

개요

동적 계획 알고리즘이란?

• 최적화 문제를 해결하는 알고리즘

최적화 문제: 최대, 최소 등을 구하는 문제

해결방식

• 입력 크기가 작은 부분 문제들을 모두 해결한 후에, 그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결한다.

분할정복 vs 동적계획

• 분할 정복 알고리즘

  • 부분 해들을 각자 따로 취합하여, 보다 큰 문제의 해를 구한다.

  • 부분 문제의 해는 중복하여 사용하지 않는다.

• 동적 계획 알고리즘
  • 최소 단위의 부분 문제의 해들 중 필요한 모든 해들을 활용하여 보다 큰 문제의 해를 구한다.
  • 부분 문제들 사이에 의존적 관계가 존재한다.

  • 함축적인 순서

    

동적 계획 알고리즘이 적합한 경우

• 최적의 원리

  • “어떤 문제에 대한 최적해”가 그 문제를 분할한 “부분문제에 대한 최적해”를 항상 포함하고 있을 때

  • 즉, “작은 문제의 최적해” ⊂ “큰 문제의 최적해”

• 재귀적 해법이 부적절한 경우 (top-down 방식이 부적절한 경우)
  • 분해된 문제가 서로 독립적이지 않은 경우 ⇒ 중복 호출 발생

    ex) 피보나치 문제 등

---

• 성결대학교 컴퓨터 공학과 임태수 교수님 (2021)
• 양성봉, 『알기 쉬운 알고리즘』

본 게시글은 위 강의 및 교재를 기반으로 정리한 글입니다.