Dynamic Programming 수업 필기

2.

Divide and Conquer-> top down 해결법, 나누어진 부분들 사이에 상관관계가 없는 문제를 해결하는데 적합. 

ex) 피보나치 알고리즘에 d&c 방법을 사용하면 호율적 x. 

왜냐? 피보나치의 경우 나누어진 부분들이 서로 연관되어 있기 때문

3.

재귀적 해법. 

divide and conquer로 푸는 방법 중 가장 안좋은 예

4.

피보나치를 d&c로 풀면 심각하게 비효율적&엄청난 중복 호출.

5,6.

동적 프로그램이 solution. 

ex) 피보나치 수를 구하는 동적 프로그래밍 알고리즘

fibonacci(n)

{

f[0] = 0; f[1] = 1;

for (i =2; i<=n; i++)

f[i] = f[i-1] +f[i-2];

return f[n];

}

--------------------------------------

*탑다운 vs 바텀업*

탑다운: 가장 큰 문제를 방문 후 작은 문제를 호출하여 답을 찾는 방식

바텀업: 가장 작은 문제들 부터 답을 구해가며 전체 문제의 답을 찾는 방식

-탑다운은 재귀호출, 바텀업은 반복문을 이용해 구현.

ex)

int fibonacci(int n)

{

    if (n == 0) return 0;

    if (n == 1) return 1;

 

    if (dp[n] != -1) return dp[n];

 

    dp[n] = fibonacci(n - 1) + fibonacci(n - 2);

    return dp[n];

}

 # Top-down 방식이다. 재귀 호출을 이용해 구현했고, 함수 호출을 줄이기 위해 메모이제이션을 사용했다.

int fibonacci(int n)

{

    dp[0] = 0, dp[1] = 1;

    for (int i = 2; i <= n; i++)

        dp[i] = dp[i - 1] + dp[i - 2];

}

 # Bottom-up 방식이다. 반복문을 사용해 구현했다.

--------------------------------------

7.

다이나믹 프로그래밍이란, 

: 바텀업으로 계산하는 테크닉을 말한다. 

: 작은 결과 값을 이용해 더 큰 결과값으로 올라가 구하려는 결과값을 얻어 내는 알고리즘

& 중복되는 것은 기억해 두어서 skip (=메모이제이션)

8.

sequential decision process란,

The solution to a problem can be obtained from a

sequence of decision. (sequential decision process)

-Never making an erroneous decision/modification

-Making the decisions one at a time

10.

그리디vs다이내믹

In greedy method, only one decision sequence is ever

generated.

In dynamic programming, many decision sequence

may be generated

11.

dynamic 방법을 풀 때 반드시 고려되는 것

->principle of optimality

이 것이 성립되면 dynamic으로 풀 수 있음. 

부분이 아닌 전체에 대한 답(=최적의 답)이 있을 때 각각 부분에 대한 답 또한 optimal 해야 함 

12. 

하지만 모든 문제가 principle of optmality를 성립하진 않음. 

ex)

1. Principle of Optimality가 성립하는 예)

* Shortest path problem

- shortest path(optimal) from u to v :

(u, …, ip, …,iq, …, v)이고

any subpath (ip, …iq) contained in this path

is an optimal path from ip to iq이라면

=>principal of optimality가 성립함.

2. Principle of Optimality가 성립하지 않는 예)

* Longest Path 문제

longest path from ① to ⑦ : 1-2-3-4-5-6-7이라면

longest path from ⑤ to ⑦ : subpath 5-6-7인가? Not longest!

Insteads, 5-4-3-2-1-9-8-7 is longest.

=>This problem does not hold the “principle of optimality

14.

Only problems that satisfy “principle of optimality”

may be solved using dynamic programming.

15.

*최적화 문제(optimization problem)

주어진 문제에 대하여 하나 이상의 많은 해답이 존재할 때, 이 가운데에서 가장 최적인 해답(optimal solution)을 찾아야 하는 문제를 최적화 문제라고 한다.

ex) shortest path문제는 최적화 문제에 속한다. 

(shortest path문제=가중치 포함, 방향그래프에서 최단경로(길이) 찾는 문제)

16.

shortest path문제 - brutal-force algoritym(무작정 알고리즘)으로 풀기

:한 정점에서 다른 정점으로의 모든 경로의 길이를 구한 뒤, 그들 중에서 최소 길이를 찾는다

->절대적으로 비효율적

51분쯤

17.

shortest path문제 - dynamic programming으로 풀기

->

자료구조를 그래프의 인접행렬식으로 표현할 것임

즉, 만약 정점들이 {V1, V2, ~, Vk}가 있다면, 정점 i에서 (=Vi) 정점 j까지 (=Vj)가는 최단경로의 길이를 D위에(k)[i][j]라고 한다. 

여기서,  인접행렬식 w[i][j]  (=D위에0)은 3가지 종류의 값을 가질 수 있는데,

만약, 정점 i에서 정점 j로의 연결선이 있다면 edge's weight를

정점 i에서 정점 j로의 연결선이 없다면 무한대 값을

정점 i와 정점 j가 동일하다면 0의 값을 가질 수 있다. 

결국 최적의 해는 d0, d1, d2~해서 dk가 될 것임. 

이렇게 작은 것부터 해결해나가는 bottom 방식이 dynamic programming

=>같은말) D(0)= W이고, D(n)= D는 최종 해이다. 따라서 D를 구하

기 위해 D(0)를 가지고 D(n)을 구할 수 있는 방법을 고

안해 내어야 한다.

d0=아무것도 안 거치는 것

d1=1번 노드를 거치는 게 좋으냐 안 좋으냐 

d2는 d1을 이용해서 값들을 업데이트. 

->d1에서 1 거치는 게 안좋은 게 2에서도 안좋으면 그 값 그대로 

18-19 d0, d1, d2, d3, d4 해보기

(간선들의 edge 방향도 생각해야 함)

이 경우 d4의 인접행렬이 최단 경로의 길이이다! 

20-22

위를 하는 방법을 식으로 표현하자면,

Dk(i, j) = min{Dk-1(i, j), Dk-1(i, k) + Dk-1(k, j) } for k≥1 임. 

또한, 이건 principle of optimality를 지키고 있음

(여기서 Pij는 i~j사이의 최단경로를 뜻함)

“If the path Pij is optimal, then Pik and Pkj are optimal.”

Time Complexity : O(n3)

26.

All pairs shortest paths문제 

-Floyd/warshall algorithm

: 위에서 한 것.

: 가중치 그래프의 각 정점에서 다른 모든 정점까지의 최단거리를 계산.

=============================1108

29.

knapsack문제

: 한 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다.

30.

knapsack을 무작정 알고리즘으로 풀기

->n개의 물건에 대해 모든 부분집합 다 고려.

31.

knapsack을 그리디 알고리즘으로 풀기 1

->가장 비싼 물건부터 우선적으로 채운다

->최적이 아닐 수 있다. 

ex) 

W=30kg

품목   무게    값

item1 25kg 10 만원

item2 10kg 9 만원

item3 10kg 9 만원

라고 할 때)

Greedy 방법: item1 -> 25kg -> 10만원

최적인 해답: item2 + item3 ->20kg -> 18만원

32.

knapsack을 그리디 알고리즘으로 풀기 2

->무게 당 가치(이윤)가 가장 높은 물건부터 우선적으로 채운다

->최적이 아니다. 

ex) 

W=30kg

품목   무게    값   값어치

item1 5kg   50 만원    10만원/kg

item2 10kg  60 만원    6만원/kg

item3 20kg  140 만원   7만원/kg

라고 할 때)

Greedy 방법: item1 + item3 -> 25kg -> 190만원

최적인 해답: item2 + item3 -> 30kg -> 200만원

33.

knapsack을 그리디 알고리즘으로 풀기 3

->물건을 0-1이 아닌 잘라서 넣을 수 있는 fractional knapsack 방법

ex)

item1 + item3 + item2 *1/2 -> 30kg -> 220만원

최적이다!

34

knapsack을 dynamic programming으로 풀기

(0-1로 쪼갤 수 없는 경우 dynamic programming으로 풀 수 있다.)

p[i][w]->i와w는 (데이터가아닌)값.무게

ex) 

weight profit 1  2  3  4  5

1          5      5  5  5  5  5

2          7      5  7 12 12  12

3          8      5  7 12 13  15

4          9      5  7 12 13   15

설명)

1행: 가방의 용량이 1,2,3,4,5일때 (1,5)인 물건이 들어갈 때의 최대 이익.

2행: 가방의 용량이 1,2,3,4,5일때 (1,5), (2,7)인 물건이 들어갈 때의 최대 이익.

3행: 가방의 용량이 1,2,3,4,5일때 (1,5), (2,7), (3,8)인 물건이 들어갈 때의 최대 이익.

4행: 가방의 용량이 1,2,3,4,5일때 (1,5), (2,7), (3,8), (4,9)인 물건이 들어갈 때의 최대 이익.

이걸 식으로 나타내면) 

i > 0 이고 w > 0일 때, 전체 무게가 w가 넘지 않도록 i번째 까지

의 항목 중에서 얻어진 최고의 이익(optimal profit)을 P[i][w]라

고 하면,

P[i][w] = maximum(P[i-1][w], pi + P[i - 1][w - wi]) if(wi<=w)

P[i-1][w] if(wi>w)

여기서 P[i-1][w]는 i번째 항목을 포함시키지 않는 경우의 최고

이익이고, pi + P[i - 1][w - wi]는 i번째 항목을 포함시키는 경우

의 최고 이익이다. 위의 재귀 관계식이 최적화 원칙을 만족하는

지는 쉽게 알 수 있다.

35.

->w를 다 할 필요는 없음. 

="P[n][W]를 계산하기 위해서 (n-1)번째 행을 모두

계산할 필요가 없음을 염두에 두어라."

->즉, P[n-1][W]와 P[n-1][W-wn] 두 항만 계산하면 됨.

이것을 n = 1이나 w<=0일 때 까지 계속함.

이렇게 되면 빅오가 빅O(n * w)가 됨. 

36.

ex로 설명)

W=30kg

품목   무게    값   값어치

item1 5kg   50 만원    10만원/kg

item2 10kg  60 만원    6만원/kg

item3 20kg  140 만원   7만원/kg

=> P[3][30]을 계산해 보자. 개선된 알고리즘은 밑에처럼 7개 항만 계산하는데 비해서, 이전 알고리즘은 3 * 30 =

90항을 계산해야 한다.

P[3][30]=max(P[2][30], 140+P[2][10])=max(110, 140+160)=200

P[2][30]=max(P[1][30], 60+P[1][20])=max(50, 60+50)=110

P[2][10]=max(P[1][10], 60+P[1][0])=max(50, 60+0)=60

P[1][30]=50

P[1][20]=50

P[1][10]=50

P[1][0]=0

=============================1113(~48까지)

37.

이렇게 되면 빅오가 빅O(n * w)가 됨. 

이것의 최악의 경우는 빅O(2의 n승)

최악의 경우 수행시간은 빅O(minimum(2의 n승,n * w) 

38. 

0-1knapsack 문제를 divide&conquer로 풀 경우

최악의 경우 수행시간은 빅O(2의 n승)

39. (4분 40초)

binary search tree란?

이진탐색트리.  자료구조를 트리로 만듦. 이 트리에 라벨이 붙음. 어떤식으로 라벨틀 붙였냐. 

-> 왼쪽 subtree에 있는 각각의 모든 노드들은 l(v)의 왼쪽은 v보다 커야함.

-> 오른쪽은 v보다 커야함. 

ex) v가 30이라면, 왼쪽은 30보다 작고 오른쪽은 30보다 커야 함. 

이렇게 구성되어 있는 것이 binary search tree

search할 때 아주 좋게 구성되어 있는 것이 binary search tree. 

제일 큰 값이 제일 위에 있는 힙트리라고도 불림

 

optimal binary search tree

: 평균 탐색하는 횟수를 최소로 만드는 이진 탐색 트리를 말한다. 

40.

binary search tree 예

예) if, for, while, repeat, loop 이렇게 5개의 단어가 있다고 하자. 

if기준으로 봤을때 알파벳 순서로 만들어함. 왼쪽 오른쪽 트리 둘 다 됨. 

오른쪽 '모든 것'이 다 i보다 더 커야함. 

ex) while보다 reapeat, loop이 작음

ex) reapeat보다 loop은 작고 while은 큼. 

이 트리들 말고도 더 많은 트리들의 경우의 수가 있음. 

=>즉, binary search tree는 찾기 쉬우라고 만든 거임. 

5개의 단어를 가지고 이진 탐색 트리 만들 수 있는 경우의 수는 많다, 

하지만 이 5개의 단어를 가장 빨리 찾기 위해서 나온 개념이 바로

=>optimal binary search tree이다.  

ex) loop를 찾아보자

왼쪽) 4번만에 찾음

오른쪽) 3번만에 찾음. 

ex) while을 찾아보자

왼쪽) 2번만에 찾음

오른쪽) 3번만에 찾음

->그렇다면 왼, 오 중 뭐가 더 빨리 찾을 수 있는 트리임? 

무엇을 기준으로 찾아야함? 

=>사전에서 사람들이 제일 frequent하게 찾는 단어 순으로 생각. 

41.

앞 슬라이드 설명

찾고자 하는 게 X, 

If X < l(root of T), then Search (leftsubtree of T, X) 루트보다 작으면 왼쪽

If X > l(root of T), then Search (rightsubtree of T, X) 크면 오른쪽

If X = l(root of T), then return. 만약 찾는 게 나오면 걍 그 값 리턴.

그렇다면 어떻게 optimal이냐? 

원래가 a1, a2, ~, an이라면, 

각각의 값마다 사람들이 뭘 자주 찾는지 probablility가 있음. 

그런 확률을 P(i)라고 함. 

but, 내가 찾으려고 하는 값이 트리에 없을 수도 있음. 

그런 걸 Q(i)라고 함=> ai와 ai+1사이에 있는 없는 값을 찾을 확률. 

a0와 an+1은 더미 값으로 그냥 마이너스 무한대, 플러스 무한대로 냅둠. 

확률이라는 것은 모든 것을 더했을 때 1이 나와야 함. 

이걸 나타낸 식이 1번 식

42.

왼쪽)

a2를 찾을 확률 p2, a1을 찾을 확률 p1 ~~

a1보다 작은 것을 찾을 확률 q0

네모박스: external node 해당되는 무수히 많은 것들.  실제로는 없는 것들

internal node: 실제로 있는 것들 

ex) e0은 a1보다 작은 것들 다 뜻함. 

43.

최종목표: cost of a binary search tree를 제일 작게, minimum하게 하는 것

cost란? 

cost를 정의한 식이 2번식.

여러 binary search tree에서 2번식이 제일 작은 것이 optimal binary search tree이다. 

식 해석)

왼쪽 항)

pi((트리에 나타날 확률 pi))라는 확률*그 확률을 가진 ai노드의 레벨을 찾어야 함.

ai노드가 깊이 있고 내려갈 수록 레벨은 커지고 찾는데 더 오래 걸리는 것임

오른쪽 항)

qi((트리에 없을 확률))라는 확률*그 확률을 가진 ei노드의 레벨에서 -1

원래는 리프까진 안와도 되기에 ei노드에 한해서  -1해줌. 

45. 해보기

46.

다이나믹으로 풀겠다 -> 항상 principle of optimality가 들어가 있어야 함. (=성립해야지만 쓸 수 있음)

즉, 이전 조합이 최적이라면, 그 이전 조합을 그대로 가져와서 다음 조합에 쓸 수 있음. 이렇게 점점 키워나가는 것. bottom up방식. 

이전 조합이 최적이기에 다음 조합에서 이 조합을 그대로 사용함. 

이런 걸 principle of optimality라고 함.

 

47. 52분

그렇다면 루트를 뭐로 할 것인가? 

1~n까지 있다면 루트를 k로 정했다 하자. 

자동적으로 1~k-1은 왼쪽에 가있을것임

그리고 또 자동적으로 k+1~n은 오른쪽에 가있을것임

왼쪽트리와 오른쪽 트리를 나누어서 생각해보자. 

각각 따로 cost 계산해보자

그래서 나온 식이 cost(L), cost(R) 임. 

그다음에 이 두 식을 더하면 됨. 

48. 용어 정리 슬라이드 

이제까지는 1~n이라 표현했는데 

이제부터는 i~j라고 하자. 

Tij

:  Ei a'i+1' Ei+1 ai+2 Ei+2 ~ aj Ej 를 가진 optimal binary tree

C(i,j)

: Tij의 cost

R(i,j)

: Tij의 루트

w(i,j)

: weight= Tij의 노드들의 확률. 몇번 나타날 확률. probabliilty를 다 더한 것. ->식 1을 모든 노드에 한해서 다 더한 값. 

49.

T에 대한 cost는 왼쪽 cost + 오른쪽 cost + root의 cost 

->(root의 cost를 구하는 과정에서, root의 level은 1이기에, 1을 곱하나 마나이기에 그건 빼고 p(k)만 남아서 식이 저래 됨)

여기서 cost'이 나옴. 

프라임이 붙음. 왜 붙냐? 

상황상 왼쪽, 오른쪽을 떼서 보기 때문에 실제 level과 1차이남. 

그래서 프라임에서는 실제 level과 같게 하기 위해 +1을 해줌. 

50.

노트필기 참고

=============================1115(51부터 녹음 됨)

51

식 n-m+1에 따라, 

ex) m=2이면 n-2+1 -> n-1개

똑같은 방법으로 m=3이면 n-2개

"크기가 m라면, 루트가 누구인지 n번 계산해야 함. 

그러므로 곱하기 m을 해줌" 

그래서 나온식이 nm-m제곱

1<=m<=n 씨그마 (nm-m제곱) = O(n세제곱)

53.

0개짜리. 

1개짜리는 4개

2개짜리는 3개

3개짜리는 2개

4개짜리는 1개 (우리가 원하는 답, 1234가 있을때뭐가 더 좋냐)

작은 것부터 맨끝에 답 구하는 bottom up 방식

16을 곱해서 (2,4,3,2,1이런식으로) 지금 보여지고 있음

0,0인 경우 e0를 뜻하고 노드가 하나도 안들어있는 경우

cost 0 이고 weight은 e0의 probablitity를 뜻함. 

0,1인 경우 

e1 ~ e1의 probability는 3

0,2인 경우

e2~e2의 probablility는 1

54

e0~e1까지 

a1이 안에 껴있을 것임. 

w는 2+4+3이므로 9

c는 앞에 식에 따라 (p.50) k가 1일때 

=============================1120

53-60

61