동적계획법?

• 하나의 큰 문제를 여러 개의 공통되는 작은 문제로 나누어서 작은 문제의 정답들을 결합하여 알고리즘을 푸는 과정
  • 간단 명료하게 이 전에 부분 문제를 메모리에 기록, 한번 계산한 부분 문제를 다시 계산 X
    
    
• 규칙(점화식)을 찾는 문제
  • f(n) = f(n-1) + f(n-2)처럼 작은 문제가 점점 큰 규모의 문제를 구성하는 구조
    
    
• DFS, BFS의 너무 많은 연산횟수를 줄이기 위해
  • 일반적인 재귀를 사용해 작은 문제들이 여러번 반복되는 비효율적인 계산 줄일 수 있다
    
    
• 위에서 언급한 배경을 기반으로 DP는
  1. 큰 문제를 작은 문제로 나눌 수 있는 경우
  2. 작은 문제에서 구한 정답이 그것을 포함하는 큰 문제에서도 동일한 경우
     의 조건에서 가능하다

방식

Bottom Up, 상향식

• 반복문 이용해 작은 문제에서 큰 문제로 반복문 이용해 작은 문제에서 큰 경우로 규모 증가시키며 문제 해결하는 경우
• 주로 권장하는 방법
  • 일반적으로 재귀보다 반복문이 오버헤드를 줄일 수 있어 성능이 더 좋다
    
    

Top Down, 하향식

• 큰 문제 해결하기 위해 재귀 이용해 작은 문제부터 해결하는 것
  
  

메모이제이션(Memoization)

• 자주 사용되는 기법 중 하나
  
  
• 값을 저장하는 방법으로 캐싱(Caching)이라고도 한다
  
  
• Top Down에서 중복 연산 방지를 위한 기술
  
  
• 앞에 했던 계산결과를 저장해두고 필요한 경우 불러서 다시 사용
  • DP 테이블 : 저장용 리스트
    
    
• 배열 혹은 해쉬를 사용
  
  
• 참고 문제 : https://velog.io/@sung-ik-je/%EB%B0%B1%EC%A4%80-1463

문제 접근 방법

• DP 유형인지 파악
  • 완전 탐색 알고리즘을 사용한 경우 시간이 매우 오래 걸리면 DP를 적용할 수 있는지, 중복 여부 확인
• 재귀보단 반복문 권장

분할 정복과 DP

• 분할 정복(Devide and Conquer)와 DP의 차이점은 두 알고리즘 모두 문제의 규모를 변화시켜 문제를 해결하지만 분할 정복의 경우는 규모 바꾸기 이전과 이후 문제 서로 영향 주지 않지만 DP의 경우는 문제의 규모가 변화했을 때 이전 문제가 현재 문제에 영향을 끼친다
  
  
• 이는 DP의 경우는 한번 해결된 문제를 다시 접근하는 작업 존재
  • 물론 메모리제이션을 이용해 접근해도 바로 종료하는 방법으로 개선