Dynamic Programming 동적프로그래밍

[ttobaegi]

동적 프로그래밍

큰 문제를 작은 문제로 나누고 작은 문제의 결과를 사용해 큰 문제를 푸는 문제 해결 방법

• 작은 문제의 결과를 반복해서 구하는 것을 피하기 위해 메모이제이션(memoization) 을 사용한다.
  • 재귀와는 달리, 작은 문제의 결과를 저장한 것을 불러오는 것으로 메모리는 사용하지만, 실행 속도에서 매우 큰 장점을 가진다.
• 최소/최대, 경우의 수를 구하는 문제인 경우, 거의 DP로 해결 가능하다.

동적 프로그래밍 구현 방식 : Bottom-up, Top-down

DP 구현 방식	Bottom-up	Top-down
접근방법	작은 문제부터 큰 문제로 답을 구해나가는 방법	큰 문제부터 작은 문제로 답을 구해나가는 방법, 큰 문제를 풀 때 작은 문제가 아직 풀리지 않았다면, 그제서야 작은 문제를 해결하는 방법
구현방법	일반적으로 반복문으로 구현	일반적으로 재귀함수로 구현

[ttobaegi]

• TESTCASE 절반 이상 맞았지만, 시간 초과 되는 경우 DP를 사용해본다.
• Base Case 기저 케이스를 반드시 고려
  • 기저 케이스 결과를 리턴하는 조건을 함수 처음에 작성한다.
• 문제의 조건을 배열 요소로 처리하여 DP배열을 생성한다.
  • 문제에 주어진 조건이 2개인 경우, 2차원 배열을 만들어야 할 수도 있고, 해석 방식에 따라 1개로도 줄일 수 있다.
  • Bottom-up 일 경우, DP 의 초기 배열값(0 또는 1)을 반드시 저장한다.
  • 하나의 루프(처리 프로세스)에서 해당 DP 값을 전부 채워야 한다.
  • DP[i][2][2] 크기라면 (0,0), (0,1), (1,0), (1,1) 을 매 프로세스마다 전부 채운다.