Dynamic Programming

smsh0722·2022년 2월 23일
0

Dynamic Programming

목록 보기
1/13

Dynamic Programming

복잡한 문제를 잘게 쪼개, 이를 풀어나가는 과정에서 답을 재사용하는 방법

아래의 두 가지 특성을 기억해야 한다.
1) Overaping Subproblems
2) Optimal Structure

1) Overaping Subproblems

Divide and Conquer처럼, DP도 sub-problems를 이용한다.
이때, subproblems이 반복해서 나온다면, DP로 풀 수 있다.
반면에, subproblems이 반복해서 나오지 않는다면, 굳이 결과를 저장해가며 DP로 풀 이유가 없다.

피보나치 수열을 생각해보자.
fib(5)를 구한다고 하면, 아래와 같이 recursive 하게 풀 수 있다.

             		 		fib(5)
                   /        		 	\
             fib(4) 					  fib(3)
           /        \     				 /      \
        fib(3)      fib(2) 			 fib(2)   fib(1)
        /     \     /     \    		/     \    
    fib(2) fib(1) fib(1) fib(0)  fib(1)  fib(0)
    /  \
fib(1) fib(0)

여기서 fib(3)가 두 번 나오는 것을 확인할 수 있는데, 첫 번째 fib(3) 값을 저장해 둔다면 다음번에 다시 계산하는 일을 생략할 수 있다.

이때, 저장하는 방법에는 두 가지가 있다.
a) Memoization
b) Tabulation

a) Memoization

위의 recursion 과정에서, 처음 계산하는 해를 따로 저장한 후에, 똑같은 문제가 나오면 답을 불러오면 된다.
recursive하게 위에서 아래로 계산을 진행하기 때문에, Top-Down 방식으로도 불린다.

b) Tabulation

Memoization은 구현하기 쉽지만, recursive calls이 깊어지면 속도, 메모리 그리고 StackOverFlow 측면에서 이슈가 생긴다.

이를 해결하기 위해서, fib(0)과 같은 base-case부터 시작해 iterative 하게 table을 작성해나가며 풀 수 있다.
이를 Bottom-Up 방식이라 한다.

2) Optiaml Structure

주어진 problem의 해를, subproblems의 최적해로 구할 수 있는 경우를 말한다.

EXAMPLES

  1. LCS(Longest Common Subsequence)
  2. LIS(Longest Increasing Subsequence)
  3. 0-1 Knapsack problem
    ..
profile
Military service - May 31, 2022 ~ Nov. 30, 2023

0개의 댓글