[Algorithm] Dynamic Programming

Y_Y·2023년 4월 28일
0

Algorithm

목록 보기
2/3

Dynamic Programming

사용조건

  1. 최적 부분 구조 (Optimal Substructure)
  • 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있습니다.
  1. 중복되는 부분 문제 (Overlapping Subproblem)
  • 동일한 작은 문제를 반복적으로 해결해야 합니다.

예시

  • 피보나치 수열

fibo(n) = fibo(n - 1) + fibo(n - 2) (a>=3,a1 = 1, a2 = 1)

시간복잡도 O(2^n)

Memoization

  • 메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 하나이다.
  • 한 번 계산한 결과를 메모리 공간에 메모하는 기법이다.
    • 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다.
    • 값을 기록해 놓는다는 점에서 캐싱(Cashing)이라고도 한다.
  • 피보나치 수열의 경우 메모이제이션을 이용할 때 시간복잡도가 O(n)으로 줄어든다

탑다운 vs 바텀업

  • 하향식, 상향식
  • DP의 전형적인 형태는 바텀업 방식
  • 엄밀히 말하면 메모이제이션은 이전에 계산된 결과를 일시적으로 록해 놓는 넓은 개념을 의미한다.
    • 메모이제이션은 DP에 국한된 개념이 아니다.
profile
남을 위해(나를 위해) 글을 쓰는 Velog

0개의 댓글