10주차 - 동적 프로그래밍

동적 프로그래밍

정의

• 재귀 성질을 가진 문제를 중복 호출을 줄이며 해결하는 기법

사용 예시

• 재귀적 방법이 좋은 예시

  • 정렬 알고리즘(퀵정렬, 병합정렬…)

  • 팩토리얼 구하기

  • DFS 그래프

• 재귀적 방법이 나쁜 예시

  • 피보나치 수 구하기

    ​ 차수가 증가할 수록 중복 호출이 크게 증가함

적용 요건

• 최적 부분 구조
  • 큰 문제의 최적 솔루션에 작은 문제의 최적 솔루션이 포함되어야 함
• 재귀 호출 시 중복
  • 재귀적 해법으로 풀면 같은 문제에 대한 재귀 호출이 심하게 중복됨