[Python] 동적계획법(Dynamic Programming), 탐욕알고리즘(Greedy)

동적계획법(Dynamic Programming), 탐욕알고리즘(Greedy)

 

 

 

동적계획법(Dynamic Programming)

 

 

동적계획법

 

• 복잡한 문제를 간단한 여러개의 문제로 나누어 푸는 방법
• Greedy보다 시간적으로 효율적이지 못할지모르나 결과에 대해서는 효율적인 값을 구할수있다.
• 문제의 일부분을 풀고 그결과를 재활용하는 방법이다.
• 하나의 문제를 중복되는 서브문제로 나누어 푸는 방법
• 분할정복과 유사한 개념
  • DP는 문제를 분할하는 경우 중복되는 서브문제가 있고, 분할정복은 분할된 서브문제가 독립적이다.
  • 분할정복은 부분 문제간에 서로 중복이 없는 것이고, 동적 프로그래밍은 부분 문제가 서로 중복되어, 상위 문제 해결 시 재활용된다.
  • DP는 서브문제가 같은 경우에 메모이제이션을 활용하여 같은 문제에 대해 해결할 수 있고, 분할정복은 서브문제가 다르기 때문에 메모이제이션을 활용하지 않는다.
  • DP를 활용하면 해결할 수 있는 문제의 범위가 넓어진다.
• DP에 두 가지 방법론이 존재한다.
  • 메인문제를 분할하면서 해결하는 방법으로 하향식 방법인 메모이제이션(하향식방법)
  • 가장 작은 문제를 먼저 해결하고 최종적으로 메인 문제를 해결하는 방법으로 상향식 방법인 태뷸레이션(상향식방법)
  • 메모이제이션 또는 태뷸레이션의 공통 특징은 계산을 진행했던 항들을 저장하고 재방문시 계산과정 없이 저장된 값을 리턴한다.
  • 공통점은 둘 다 부분 문제의 중복에서 오는 비효율을 제거하기 위함이다.
• DP는 문제를 작은 단위로 분할하여 해결한 후, 해결된 중복문제들의 결과를 기반으로 전체문제를 해결한다.

 

 

 

 

탐욕알고리즘(Greedy)

 

탐욕알고리즘

• 최적해를 구하는데에 사용되는 근사적인방법
• 눈앞에 있는것들을 하나씩해결
• 발견법(heuristic method)의 방법 중 하나
  • 발견법 : 최선, 최적의 답을 찾기보다도 주어진 상황을 한단계씩 빠른 시간 내에 해결하기 위해 사용하는 방법론
• 각 단계마다 최적해를 찾는 문제로 접근한다.
• 해결해야 할 전체 문제의 갯수를 줄이기위해 개별적으로 문제를 해결해 나간는 선택을 한다.