이 게시글은
서울대학교 데이터사이언스대학원
조요한 교수님의
데이터사이언스 응용을 위한 컴퓨팅 강의를
학습을 위해 재구성하였습니다.
Dynamic Programming에 대해
배운 내용을 정리해보도록 하겠다
학창시절을 보내다보면 한 번쯤은 들어봤을
피보나치 수열
피보나치 수열은 각각의 숫자가 앞의 두 숫자의 합으로
이루어져있는 수열로
피보나치 수열을 위와 같이 점화식으로 나타낼 수 있다
이는 대표적인 Divide and Conquer 방식인데
일반적으로 어떤 problem을 작은 subproblem으로 나누는것이다
위 ppt에서의 코드를 보면
피보나치 함수를 정의해놓고 있다
Fib함수 내에서 계속해서 Fib를 호출하면서
recursive하게 구현하였고
n이 0이거나 1일 때 0 또는 1의 값을 리턴한다
이렇게 구현한 피보나치 함수의 call stack을
트리로 표현하면 ppt의 오른쪽처럼 표현할 수 있다
저 tree를 자세히 보면 같은 subproblem을
여러 번 반복해서 푼다는 것을 알 수 있다
Fib(n-2)는 앞에서 풀었는데
뒤에서 반복해서 또 풀고있는 것을 볼 수 있다
이러한 방식의 time complexity는
O(2 n제곱)이다
왜냐하면 n이 1 또는 0이 될때까지
진행되기 때문이다
그렇다면 이 Fib 함수에서
이미 앞에 계산한 Fib 값이 뒤에서도
반복해서 나온다는 것을 알았으니
미리 계산한 Fib 값을 저장해주도록 하자
그래서 그 값을 저장한 F라는 list를 생성한다
이렇게 해주면 이전에 한 번 계산했던 값이라면
그냥 list에서 index를 찾아서 반환하게 된다
이렇게 하면 총 n번만 계산을 하면 되므로
time complexity는 O(n)이 걸리고
함수 실행 시 call stack을 트리로 나타내면
오른족과 같아진다
이렇게 이전에 계산한 값을 미리 저장해 놓고
이후 연산에서 사용하는 것을
dynamic programming에서 memoization이라고 하는데
dynamic programming에서 굉장히 중요한 개념이다
dynamic programming에서의 다른 예시를 살펴보자
위와 같이 총 n칸의 계단을
1칸 또는 2칸씩만 움직여서 모두 올라가려고한다
올라갈 수 있는 모든 방법의 개수는 몇 개일까?
이러한 문제를 풀 때 어떻게하면 효율적인 코드를 작성하는지
고민하는 것도 중요하지만
너무 효율적인 코드에 집착하기보단
그냥 하나하나 해본다면 어떻게 되는지 생각해보는 것도 중요하다고 한다
만약 나에게 무한의 시간과 무한의 공간이 주어진다면
이 문제를 어떻게 해결할 것인지
고민하는 과정에서 알고리즘 실력이 늘 수 있을 것 같다
우선 위 같은 경우는에서는
ways[i]를 총 i칸 올라가는 방법이라고 한다면
i보다 1번째 적은 칸에 도착해서 남은 1칸을 더 가는 것
i보다 2번째 적은 칸에 도착해서 남은 2칸을 더 가는 것
위 두개의 합이 총 i칸을 올라가는 방법의 개수가 될 것이다
따라서 이걸 점화식으로 나타내면
ways[i] = ways[i - 1] + ways[i -2]가 된다
그 다음에 base case를 정의를 해주는데
기본적으로 0층에 도달하는 방법은
그냥 안움직이는 방법 1개이므로 1가지 방법
1층에 도달하는 방법도 1가지 방법이므로
ways[0] = 1
ways[1] = 1
이렇게 정의를 해준다
이러한 방법의 time complexity는
O(n)이 된다
Dynamic Programming
Dynamic Programming이란 복잡한 문제를
해결해가는 테크닉이다
기본적인 아이디어는 큰 problem을
작은 subproblem으로 나누어서 해결하고,
subproblem들의 결과값이 다른 문제들을 푸는데 계속 사용되는 것이다
궁극적으로 구하고자 하는 optimal solution이
subproblem의 optimal problem으로 해결이 가능할 때
dynamic programming이 굉장히 유용해진다
여기서 programming이라는 단어는
우리가 아는 단순 코딩 programming은 아니고
tabular method를 말하는 것이다
그렇다면 divide and conquer 방식과의 차이점은 무엇일까?
merge sort는 대표적인 divide conquer 방식인데
array의 반을 잘라서 sort하고
다시 merge해서 sort하는 방식이다
divide conquer는 기본적으로 subproblem들이
각각 independent하다
subproblem들을 recursive하게 풀어서
combine하는 것은 같지만
subproblem들 간에 share하는 informaion이 없다
반면에 dynamic programming은
subproblem을 overlapping한다
이 말은 즉, subproblem의 solution을
나중에 다시 reuse한다는 것이다
이것이 가장 핵심적인 차이이다
Dynamic Programming에는 4가지 step이 있다
1. state define하기
subproblem을 어떻게 정의할 것인가
그리고 어떻게 나타낼 것인가를 정하는 단계이다
위의 예시에서 보자면
ways[i]는 i칸 올라가는 방법의 개수라고
정의를 내린 것이 이 단계이다
2. establish recursive relation
large problem을 small problem으로 정의하는 과정이다
problem을 어떻게 함수로 나타낼 수 있을지를 결정한다
ways[i] = ways[i-1] + ways[i-2]로 정의한 것이
이 과정에 해당한다
3. Define Base Case
base case를 정의하는 과정이다
함수가 Recursive하게 수행되다가 어느 순간 멈춰야하는데
그걸 정의해주는 것이 base case이다
따라서 simplest instance가 무엇인지 찾아서 정의해주고
그 친구들이 문제의 foundation이 된다
위 예시에서는 ways[0] = 1, ways[1] = 1이
base case가 된다
4. implement the solution iteratively or recursively
bottom-up(iteratively)으로 구현할건지
top-down(recursively)로 구현할건지와 같이
구체적인 구현을 수행하는 부분이다
이 부분에서는 memoization이 매우 중요한 역할을 한다
이제 Dynamic Programming의 다른 예시를 살펴보고
같이 풀어보자
길이가 n인 토막이 있고
길이 i에 따라 Pi는 얻을 수 있는
Revenue이다
길이 n인 토막을 어떻게 자르면
가장 많은 돈을 벌 수 있을까?
만약 총 길이 n이 4라고 해보자
그러면 총 8가지의 자리는 방법이 있다
아예 안자르면 길이가 4가 되므로 revenue는 9
1/3만큼 자르면 1 + 8 = 9
2/2만큼 자르면 5 + 5 = 10
...
이런식으로 진행되게 된다
따라서 위 경우를 모두 살펴보면
2/2가 10으로 가장 높은 수익을 준다는 것을 알 수 있다
우선 길이 n의 나무 토막을 자르는 방법은 몇 개가 있을지 생각해보자
기본적으로 n-1개를 자를 수 있는 가능성이 있고
각각의 position에서 자를 수도 있고 안 자를 수도 있다
그렇게 때문에 총 경우의 수는 2의 n-1제곱 개가 되고
정말 근본적으로 한다면 모든 경우의 수를 다 구해볼 수도 있을 것이다
하지만 dynamic programming을 이용해서
조금 더 효율적으로 해결방안을 찾아보고자한다
우선 state를 정의해보자
r(n)은 길이가 n일 때의 maximum revenue이다
rod를 젤 앞에서 한 토막을 내면 나머지는 n-1토막이 된다
그럼 p(1) + r(n-1)이 이 경우에 가장 최적의 수익이 될 것이다
앞에서 2토막을 내면
p(2) + r(n-2)가 가장 최적의 수익이 될 것이다
이러한 식으로 마지막에는 한 개도 자르지않는 경우인
p(n)이라는 식이 나오게 되고
이 총 n개의 식 중에서
결과값이 가장 큰 것이
r(n)이 되는 것이다
따라서 이 식의 점화식은
r(n) = max(처음 토막 길이만큼의 가격 + 남은 토막의 수익의 최댓값)
이 되는 것이다
naive한 algorithm의 pseudo code를 한 번 보자
cut-rod라는 함수를 만들고
각각의 토막별 가격을 담고있는 p와 토막의 길이인 n을 받아온다
n이 0인 경우는 그냥 0이고
i는 1부터 n까지 처음의 시작 길이를
처음 길이를 몇으로 자를건지를 나타낸다
따라서 q의 값은 위와 같은 식이 나오고
q를 리턴해주는 형태가 된다
이전에 나온 결과값을 저장하고 있지 않기 때문에
똑같은 것을 반복해서 계산하고 있어서
조금 느릴 수는 있지만 정확하게 풀 수 있다
subproblem들이 작동하는 원리를 tree로 나타낸 것이다
n이 4라고 가정해보자
각각의 노드는 cut-rod의 인자들이고
cut-rod 4가 호출이 되면 cut-rod 3이 호출이 되고
이렇게 recursive하게 호출이 된다
위 tree를 확인해보면
계속 똑같은 문제를 recursive하게 반복을 해서
호출을 하는 것을 확인할 수 있다
그런데 naive algorithm에서는 이전에 계산했던 것을
따로 저장해두지 않기 때문에 계속해서 계산을 하게된다
naive algorithm의 time complexity를 보자
T(n)이 cut-rod가 호출되는 횟수인데
recursive하게 돌면서 호출을 해서
T(n) = T(n-1) + T(n-2) + ... + T(0)이 된다
저 상태에서 T(n)에서 T(n-1)을 뺴주면
T(n)은 2의 n제곱이 되고
time complexity는 n의 exponential이 된다
memoization을 이용한 dynamic programming으로
top-down 방식으로 구현을 해보자
처음에 4가 호출된다면 그 다음에는 3이 호출된다
그리고 3이 호출되면 2->1->0 이 순서로 호출이 된다
그러면 3, 2, 1의 값은 이때 다 계산이 되어서
어딘가에 결과값이 저장이 되어있을 것이다
0까지 마친 뒤 다시 위로 올라가면
2번째 height에서 2로 가게 된다
그런데 2는 이미 사전에 계산을 해뒀으니
그 값을 가져온다
또한 원래대로라면 2->1->0으로 내려가야하지만
이미 밑의 값들 모두 계산이 되어있어서
계산을 해줄 필요가 없이 값만 가져오면 된다
따라서 굳이 내려가줄 필요가 없다
이런식으로 memoization을 활용하면
호출 횟수가 확 줄어들게 된다
top-down approach의 pesudo code이다
크게 2가지로 나눌 수 있다
첫 번째 코드는 단순하게 계산의 결과값을
저장할 공간을 만들어주는 코드이다
그런 다음 밑 부분에서 recursive하게
cut-rod 메소드를 수행하는데
r(n)이 0이상이라는 소리는 처음 초기화했던 - 무한대값에서
한 번 업데이트가 된 적이 있다는 뜻이고
이는 이미 계산된 결과가 있다는 것을 의미한다
따라서 그럼 저장된게 있다고 판단을 하는 것이고
코드 전체를 실행하지 않고 그냥 값을 가져와서 실행을 하게 된다
top-down approach는 오른쪽과 같은 식으로
그 관계를 그릴 수 있다
처음에는 아무 것도 저장된게 없어서 4 3 2 1을 가다가
끝나면 돌아온다
그 다음에 2로 가는데
이 부분은 이미 다 호출이 된 부분이기 때문에
바로 0으로 갔다가 다시 올라온다
이러한 과정을 반복해서 보면
결과적으로 각각의 subproblem은 각 1번씩만 풀리게 된다
따라서 이 방식에서는 총 time complexity는
n + (n-1) + ... + 1 = n2제곱이 되어서
O(n2제곱)이 된다
이제 bottom-up approach를 한 번 보자
아래에서부터 위로 채워나가는 방식이다
짧은 rod를 계산하고 그 다음 더 큰 rod를 계산한다
따라서 rod가 0, 1일 때를 먼저 계산한다
그럼 rod2는 0과 1에서 참조를 해서 쭉쭉 계산하고
그런 방식으로 문제를 해결해나가는 방식이다
보통은 bottom-up 방식이 top-down방식보다
implementation이 조금 쉽다
그리고 recursively 구현하는 top-down방식에 비해
overhead도 조금 편이다
왜냐하면 recursive하게 구현하게 되면 메모리 stack에서 계속
pop, push, pop, push가 반복되고
그렇게 되면 하드웨어에서 시간이 오래 걸릴 수가 있다
하지만 bottom-up은 그런 경향이 상대적으로 적다
bottom-up approach의 pseudo code이다
q를 계산해서 r[j]에 저장한다
여기서 중요한 것은 recursive call이 되지 않는다는 것이다
top-down과 bottom-up approach는 asymptotic하게는
동일한 running time을 갖고 있다
하지만 bottom-up은 recursion을 사용하지 않으면서
call stack을 절약할 수 있고
0부터 순차적으로 접근을 하기 때문에
메모리 locality로 인해 접근 속도도 빠르다
반면에 recursive는 어떻게 구현을 하냐에 따라서
메모리 여기 저기에서 가져올 수가 있어
상대적으로 접근효율이 떨어진다
그렇다고 해서 bottom-up이 항상 좋은건 아니고
case by case이다
지금까지는 max revenue를 구하는 문제만 풀었다
하지만 이제 궁금한건
max revenue에 도달하는 실제 cut의 configuration을
어떻게 구할 것인지 이다
따라서 s라는 것을 반환할건데
이 s는 길이가 j인 것을 잘라서 max revenue를 얻고 싶은데
앞에서 몇 번째 위치에 잘라야 max revenue가 되는지를
나타내는 값이다
구현은 위와 같이 한다고 한다
앞에서 봤던 코드와 비슷하지만 s가 추가되었다
max값이 되었을 때 i를 s에 함께 저장한다
그런 다음 r과 s를 함께 반환한다
이런식의 코드를 사용하면 solution을 reconstruct가 가능하다
i가 0이라고 하면 토막의 길이가 0일 때의 가격이다
i가 3일 때의 max revenue는
s가 3인걸 보아하니 그냥 3을 통째로 자른 값이
max revenue가 되는 것을 알 수 있다
중요한 것은 i = 4부터이다
max revenue가 s가 2일 때 발생했다
가장 첫 토막을 2개로 잘랐더니
max revenue인 10이 발생했다는 소리이다
길이가 5일 때도 살펴보자
s = 2인 것을 보니 앞에서 2칸을 잘랐을 때
길이가 max가 되었다는 뜻이다
따라서 max revenue는 13이다
i가 6인 경우는 그냥 6을 통째로 갖는 경우가
max revenue인 17이 되고
i가 7인 경우는 앞에서 1칸 잘랐을 때가 가장 수익이 커졌고
그래서 p(1)의 값인 1과
남은 길이인 16의 max revenue인 17이 더해져
총 max revenue가 18이 된 것을 볼 수 있다
간단하게 greedy algorithm에 대해 살펴보고
오늘의 수업내용 정리는 마무리를 해보려고한다
dynamic programming은 앞에 나왔던 subproblem에서
optimal solution을 찾고 그걸 이용해서
미래에 일어날 일에 대해 informed choice를 만드는 것이었다
하지만 greedy algorithm은 그렇게 하지 않고
그냥 initial greedy choice를 만들고
남은 subproblem을 푸는 방식이다
중요한 가정은 locally optimal한 choice가
globally optimal한 solution으로 이어진다는 것이다
어떤 global한 optimal solution이 subproblem의 optimal solution으로
이어질 수 있을 때 이걸 greedy algorithm이라고 부른다
그냥 각각의 순간마다 best choice라고
여기는 선택을 하는 것이다
그리고 이 것은 뒤에 나올 problem들의 결정에 대해서
아무런 영향을 주지 않는다
이러한 과정을 반복하면 결국 가장 좋은 결과를
선택할 수 있게 된다