동적계획법_DP(DynamicProgramming)

동적계획법(DP : Dynamic Programming)

• 작은 문제들을 풀면서 그 결과를 저장해 나아가면서 전체 문제를 해결하는 알고리즘
• 중복 계산을 줄여서 계산속도를 높일 수 있으며 경우의 수가 많은 경우에도 효율적으로 계산할 수 있다 일반적으로 재귀로 구현되며 메모이제이션(memoization) 기법을 사용하여 중복 계산을 피한다
  • 메모이제이션 - 이전에 계산된 결과를 저장하고 다음에 동일한 계산에 필요할 때 저장된 결과를 이용하여 중복계산을 피함으로서 성능을 향상 시킬 수 있다.

구현단계

1. 문제를 하위 문제로 쪼갠다
2. 하위 문제를 재귀적으로 해결한다
3. 결과를 저장한다(메모이제이션, 테블레이션)
4. 저장된 결과를 이용해 큰 문제를 해결한다.

동적 계획법 조건

1. 최적부분구조(Optimal Substucture)
   1. 전체 문제의 최적해가 부분 문제의 최적해로 구성 될 수 있는 경우
   2. 전체 문제를 작은 부분 문제로 나누어 각각의 부분 문제에서 최적의 해를 구한 다음 이를 조합해 전체 문제의 최적해를 구하는 것을 의미
2. 중복부분문제(Overlapping Subproblems)
   1. 동일한 작은 문제를 반복적으로 해결해야하는 성질

동적계획법 종류

1. 탑 다운(Top-down) : 큰 문제를 해결하기 위해 작은 문제를 호출하는 형식
   1. 장점 : 작은 문제들의 결과값을 저장함으로써 동일한 계산을 반복하지 않아 시간복잡도도 감소한다 - 메모이제이션
   2. 단점 : 스택오버플로우 발생 가능성이 있다 - 재귀 때문에
2. 바텀 업(Bottom-up) : 작은 문제부터 차례대로 해결해 나가는 방식
   1. 장점 : 부분 문제의 해를 저장하고 이를 활용하여 다음 문제를 해결함으로써 시간복잡도도 감소한다. - 테블레이션
   2. 단점 : 초기값을 설정해줘야 하고, 작은 문제들의 결과값을 임시적으로 저장해둘 공간이 필요하다.