작은 부분 문제부터 해결하고 이들을 이용해서 보다 큰 크기의 부분 문제를 해결하여 최종적으로 원래 주어진 문제를 해결하는 알고리즘 설계 기법
recursive하게 일어나는 점화식을 유도해내는 것이 관건
점화식 : 각각 항들의 관계를 나타낸 식
필요 요건
중복 부분 문제 구조
작은 부분으로 쪼개서 해당 부분의 결과가 다른 부분의 결과를 도출하는데 사용
작은 문제 먼저 해결 → 작은 문제의 최적해를 이용하여 순환적으로 큰 문제 해결
점화식 유도가 가능해야 한다.
순환적인 성질 때문에 이전에 계산했던 문제의 해가 다른 곳에서도 필요하게 되는데 이를 위해 DP에서는 저장 공간(table)에 해를 저장하게 된다.
저장된 해들이 다시 필요할 때 마다 table에서 참조하여 중복된 계산을 피한다.
최적 부분 문제 구조
최솟값, 최댓값, 경우의 수
💡 DP는 만능인가요? 아니다. 계산값을 저장하는 것이 계속 반복되기 때문에 수행 횟수가 늘어나면 시간적으로 유리하지 않을 수 있다. 하향식 접근을 하면 계산을 요구하는 값만 계산을 하게 되지만 상향식 접근은 사용되지 않는 값도 계산하기 때문에 더 느려질 수 도 있다. 최적의 원칙이 적용되는 않는 예 : 최장 경로 문제
피보나치
피보나치를 구하는 재귀함수
상태 공간 트리
답을 구하기 위해 거치는 중간 과정들이 표현 된 트리
피보나치의 상태 공간 트리는 모든 가지들을 거쳐야지 답이 나온다.
시간 복잡도 계산이 가능하다
선택지의 재귀깊이 승
중복 연산 체크가 가능하다
메모이제이션 활용
확인 할 수 있는 점
엄청난 중복 호출이 존재한다!
메모이제이션
이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하는 기술
실행속도 감소
동적 계획법의 핵심
알고리즘
fibo(n)
if n>=2 and memo[n] = 0 //메모여부 체크
memo[n] <- fibo(n-1) + fibo(n-2)
return momo[n]
메모를 위한 배열 memo[n] 할당
memo 배열 모두 0으로 초기화
연산되어서 나올 수 없는 값 활용!
0, -1,-2…
memo[0]은 0으로 memo[1]은 1으로 초기화
1째항 2째항은 기저조건이다.
메모 여부 체기
메모가 안되어 있으면 연산
메모가 되어있다면 메모값 활용
단점
추가적인 메모리 공간 필요
공간 복잡도 증가, 시간복잡도 감소 (trade-off)
재귀 함수 호출로 인한 시스템 호출 스택을 사용하기 때문에 실행 속도 저하와 오버 플로우 발생 가능성이 있다.
