[개념] Dynamic_Programming(동적계획법)

동적 계획법(Dynamic Programming)의 개념과 다양한 응용 알고리즘을 설명합니다. 중복 계산을 방지하는 메모이제이션 기법, 상향식/하향식 접근법부터 피보나치 수열, 이항계수, 격자경로, 코인 체인징, 연쇄 행렬 곱셈, 플로이드 최단경로, LCS, LIS, OBST, 0-1 배낭 문제 등 다양한 DP 알고리즘의 원리와 구현 방법을 코드와 예제를 통해 상세히 다루고 있습니다.

기존 분할정복식(하향식:TopBottom)은 중복계산이 단점

• 발전 시킨 방식이 TopBottom:Memoization 방식이며 중복계산을 없앰 => DP로 분류
• 다만, 하향식 방식들은 재귀 리턴 오버헤드가 아쉽다.

반면, 동적계획법(상향식:BottomTop)은 중복계산이 없음

• 분할해서 나누어진 부분들 문제들을 먼저 풀면서 점점 상향으로 올라가는 방식
• 추가 메모리 사용(배열에 기록 등등), 보통 for문이 제일 흔한 방법
• 다만, 필요없는 값도 계산한다는 점이 아쉽다.

그럼 언제 분할정복식을 쓰고, 언제 동적계획법을 쓰는게 좋은지 궁금증이 생긴다.

보통 분할정복식은 상관관계 없을 때 좋다고 하고, 동적계획법은 상관관계 있을 때 좋다고 한다.

동적계획법(DP) 이용한 알고리즘들

피보나치의 수

• top-bottom(MEMOIZATION) 방식 : f[n] = fib(n-1) + fib(n-2); 코드가 핵심이다.
• 기존 알고리즘에서 f[n] 배열을 따로 추가해서 배열에 기록을 해서 재사용을 해나가는게 핵심인 것!
• 피보나치의 수란?

이항계수

• 기존엔 팩토리얼로 공식을 이용해서 풀었을 텐데, 여기선 아래 식을 활용하자.

  • 

• 코드를 보는게 이해하기 훨씬 편할테니 바로 코드를 보자.

• BottomTop 방식 코드

  

  • 배열에 채워지는 모습은 아래 그림을 통해 이해하자.
  • j <= min(i,k) 를 사용하는 이유는 아래 그림의 오른쪽 배열형태를 이루기 위해서이다. 직접 하나하나 대입해보면 아래 배열처럼 흘러감을 알 수 있다.

​

• TopBottom 방식 코드
  • 재귀를 사용하여 앞서 본 nCk 공식을 그대로 사용하는게 큰 특징이다.
  • 해당 TopBottom 방식의 큰 틀은 “MEMOIZATION, BASE CONDITION, RECURSION” 로 나뉜다.
    • 첫줄의 if(b[n][k]>0) return b[n][k]; 이 MEMOIZATION 부분이다.
    • 두번째줄의 if(n==k || k==0) {...} 이 BASE CONDITION 부분이다.
    • 세번째줄의 b[n][k] = TopDown_bin[n-1][k]+TopDown_bin[n-1][k-1]; 이 RCURSION 부분이다.

격자경로

• 너무나도 유명한 격자경로를 정리해보겠다(기본형태)

  

  • 참고) 식에 P(j,1)은 오타이고 P(i,1)로 봐야한다.
  • 보통 격자경로는 이런 그림의 형태를 가지며, S->T로 가는 최단경로의 개수를 구하는게 목표이다.
  • 또한, S에서 출발해서 오른쪽과 아래로만 이동을 할 수 있다.
  • 1)여기서 수학적 특징으로 nCk 조합을 이용해서 한번에 구할수도 있다.
    • 우리는 총 (가로N+세로M) 번의 이동이 필요하며, 그 중 가로N번을 오른쪽으로, 세로M번을 아래로 이동해야 한다.
    • 총 이동횟수 가로N+세로M = 12이다. 이를 n으로 보자.
    • 12번 이동중에 4번 아래로가는 서로다른 최단 경로개수? 12C4
    • 12번 이동중에 8번 오른쪽가는 ..? 12C8
    • 12C4=12C8 이란것은 수학적으로 자명하기 때문에, 12C4로 바로 값을 구할 수 있다.
  • 2)앞서 정리한 이항계수 알고리즘처럼 여기서도 유사하게 DP로 풀수도 있다.

    • P(i,j)=P(i-1,j) + P(i,j-1) 가 핵심 알고리즘이다.

    • 그림을 보고 이해하자면, (i,j)자리에 그 왼쪽인 (i,j-1)자리와 그 위인 (i-1,j) 자리를 더해서 2, 3, 4, 5… 이런식으로 구해가고 있다는걸 이해하면 충분히 이 문제는 이해할 수 있다.

• 이번엔 기본형태의 조금 응용버전인 표시된 곳은 못지나가는 경우에 구하는 것을 보겠다.

  

  • 마크가 되어있는곳의 경우 0으로 두고, 아닌경우 기존방식 그대로 사용 시 해결할 수 있다.

  • 이유를 생각해보면, 표시된 곳은 지나갈 수 없기 때문에 경로가 아예 없는것이다.

  • 따라서 기존방식에선 (i-1,j), (i,j-1) 위치의 값을 더해서 구하기 때문에, 이때 표시된 곳이
    만약 (i-1,j) 였을 경우 0으로 설정해뒀으면 더해도 (i-1,j) 위치의 값은 안더한거나 마찬가지이게 되는 것이다.

• 여기서 또 응용된 버전으로 표시된곳을 오히려 b(1<=b)번 이상 지나가야 하는 경우를 보겠다.

  

  • 이 예제는 b=2인 경우로 3차원 배열에 b=0, b=1, b=2인 경우들 최단경로 개수를 기록해 나간다.
    • (표시없는길 개수)/(표시1번 지난길 개수)/(표시2번 지난길 개수) 로 볼 수 있다.
  • 구해나가는 방법은 우선 표시(mark)가 없다고 가정해서 표시있는 구역에서 기존과 동일하게 구한다.
  • 다음으로 표시가 있는지 확인 후 있다면 선언했던 3차원 배열에서 각 차원들 값을 다음 차원들로 각각 옮겨준다.
    • 물론, b=2라서 3차원이니까 3차원 이상으로 넘어가는건 무시하고 계속 3차원에서 같이 합해준다.
  • 그림을 보면, T까지 다구한것은 아닌데 그 위의 점까지 구한 결과는 44라는것을 확인 할 수 있다.

Coin Changing Using DP – 물건을 구매하고, 거스름돈 교환

• 이 문제는 물건을 살때 지페를 내고 거스름돈으로 동전을 돌려받는 문제인데,
  돌려주는 잔돈(동전)의 개수를 최소화 하는 알고리즘을 의미한다.

  • 이 알고리즘에서 생각해야할 점이 있다.

  • 만약 동전이 1원, 7원, 10원이 존재하며 이때 14원을 거스름돈으로 돌려줘야 하는경우를 생각해보자.

    • 정말 간단히 그리디(탐욕적)방법으로 생각하면 10x1 + 1x4 = 14 로 총 5개 동전을 거슬러준다.
    • 그런데, 이는 최적의 답이 아니다. 실제로는 7x2 = 14 로 총 2개의 동전만 거슬러주면 된다.
    • 따라서 이런 경우가 있다는것을 잘 이해하고 넘어가야한다.

    

  • 이 알고리즘을 DP로 푸는 방식을 나타낸 그림이다.

  • 아래 공식을 이해하기전 위 코드들이 사용된 구조를 이해하자.

    • denom은 액면가(주어진 동전 종류인 1원, 10원, 100원 등등 의미)를 나타낸 배열이다.
    • 위 그림은 C배열을 나타낸것이며 DP 방식을 사용해서 채워나간 배열이다.
    • C배열의 i는 3개인데, denom[1~3]으로 3개의 액면가가 있다고 이해할 수 있다.
    • j는 총 잔돈으로 거슬러 줄 가격을 의미한다.
    • 마지막으로 내부의 요소들은 거슬러 준 동전의 개수를 의미하는 것이다.

  • 아래 공식의 의미를 이제 이해해보자.

  • 먼저, 0, if(j=0) 이것의 의미는?

    • j가 0이면 거슬러줄 돈이 0원이란건데, 그럼 당연히 거슬러줄 때 필요한 동전개수는 0이다.

  • c[i-1][j], if(denom[i]>j) 이것의 의미는?

    • 액면가(denom[i])가 j(거슬러줄 총값)보다 크다는것은 해당 액면가(denom[i])는 현재 거슬러줄 수 없다는 것이기 때문에, 이전의 값인 c[i-1][j] 값을 그대로 사용한다는 의미이다.

  • min(c[i-1][j], 1+c[i][j-denom[i]]), if(denom[i]<=j) 의 의미는?

    • 액면가가 거슬러줄 총값보다 작거나 같다는 것은 해당 액면가를 사용할 수 있다는 것이다.
    • 따라서 이전의 값과 현재 액면가를 사용한 값을 비교해서 최소값(min)을 사용한다.
    • 참고로 1+.. 는 현재 액면가를 쓰는걸 가정해서 동전 1개를 추가한것이고,
    • j-denom[i] 는 현재 액면가를 더하면 정확히 j(거슬러줄 총값)값과 같게 만들어줄 위치로 이동시켜준다.
      • 이부분 이해가 안가면 그림보고 손으로 해보면 바로 이해가 될것이다.
      • 참고로 i=1인 c배열 부분들은 현재 이 조건으로 생성이 된다는걸 이해하면 완벽하다.

  • 따라서 여기서 최종 해답인 동전개수는 c[3][12] 의 위치인 2개 가 최종 답이 된다.

• 물론, 이렇게 구했을때 무슨 동전들을 선택한건지도 역추적으로 간단히 구할 수 있다.

  

  • 또다른 예제인 이 그림을 보면 역추적을 통해서 1원 3개, 7원 1개, 15원 1개 라고 구한 모습이다.
  • 정말 간단한 원리이다.
    • 맨 마지막 위치인 c[3][25]에서 위에값이 내려온건지 왼쪽의 값이 온건지 판단하면 된다.
    • 만약, 위의 값과 현재위치 값이 다르다?? 왼쪽의 값을 추적하면 된다.
      • 이때 왼쪽값 추적은 현재 위치가 (i,j)라 하면 j(거스름돈 총값)에서
        현재 액면가(denom[i])를 빼주면 된다. => 즉, j-denom[i] 로 인덱스 추적하면 된다.
      • 결론은 왼쪽값 추적할땐 해당 위치의 액면가(denom[i])인 동전 1개를 사용했다는 의미이다.
    • 그리고 위의 값과 현재위치 값이 같다?? 바로 위의 값으로 추적(이동)하면 된다.

연쇄 행렬곱셈(Matrix-chain Multiplication)

• 추천(응용) 문제 : 파일 합치기_BOJ11066
  • 연쇄 행렬곱셈처럼 로직은 동일하다.
  • 차이점은 BOJ11066 문제의 점화식에 “결합비용” 부분은 행렬이 아니다보니 다른 값을 사용해야 한다.

어떤 행렬곱셈을 먼저 수행하느냐에 따라 곱셈 횟수가 달라짐

4개의 행렬곱셈만 해도 5가지 곱셈 방법이 존재 및 각각 값이 다름

• A1(100x2) * A2(2x50) * A3(50x3) * A4(3x10) 이 4개의 행렬을 곱하는 곱셈 횟수를 구해보겠다.

  • 연쇄행렬에선 차원을 로 나타낼 수 있음
    • 따라서 위 행렬에서 A1의 차원은 100*2 라는 의미
  • 4개의 행렬곱셈은 총 5가지 곱셈 방법이 존재하며 이중에서 2개만 보이겠다.
  • (((A1*A2)*A3)*A4) 의 곱셈 횟수 : 100*2*50 + 100*50*3 + 100*3*10 = 28000
  • (A1*((A2*A3)*A4)) 의 곱셈 횟수 : 100*2*10 + ((2*50*3) + 2*3*10) = 2360
  • 이처럼 2가지만 봐도 곱셈횟수가 많이 차이난다는 것을 알 수 있다.
  • 그렇다면, 이를 DP방식으로 최적의 행렬곱셈 횟수를 구하는 방법은 무엇일까?

• 점화식을 먼저 구해보자

  • 

• DP방법 => 대각선으로 구해나가면서 배열이 채워지게 됨 (점화식 적용)

  

  • 이 그림은 M[4][6] 을 구하는 모습을 나타낸 그림이다.

  • M[i][j]는 Ai~Aj까지 행렬 곱하는 곱셈의 최소 횟수를 의미

  • 점화식을 기억하자
    • if i=j, M[i][j] = 0
    • if i<j, M[i][j] =

  • if i=j, M[i][j] = 0 은 예로 이 차원이 2x3, 2x3 이면 행렬 곱이 불가해서 0이다.

    • if i<j, M[i][j] = 의 의미는??
      • A1*A2*A3 를 구한다고 가정한다면? A1 (A2 A3) , (A1 A2) A3 처럼 2가지 곱셈 방법이 있다.
      • 각각 64와 90의 곱셈수가 나오며 여기서 더 min 값은 64이므로 64가 M[1][3]자리에 채워진다.
      • k 는 위 2가지 곱셈 방법처럼 괄호가 나뉘는 기준점으로 생각해도 좋다.

  • 이것을 이해했다면 최종 A1 ~ A6까지 연쇄 행렬곱의 최소 횟수는 M[1][6]이라는 것을 이해할 수 있다.

    • 따라서 이를 구하기위해 대각선으로 구해나가면서 M[1][6] 까지 배열을 채워나가는 것이다.

  • 아래는 위 점화식을 코드로 나타낸 것이다.

    • 대각선으로 접근하는 코드인 2중 for문을 잘 이해해두자.
    • 최소치의 k값이란 M[i][j] 를 구할때 min값의 k 값을 의미한다.

    

• 또한, k를 P[i][j]에 기억해서 최적 순서를 구할 수 있음 => 즉, 괄호를 씌울수 있음

  

  • 최적 곱셈수로 곱하는 순서를 괄호를 씌워서 나타내는 방법을 알려주는 그림이다.

  • M[i][j]를 최종 구할때 사용한 k값을 P[i][j]에 기억해서 순서를 알 수 있다.

    • 해당 P배열 안의 숫자는 어디서 잘랐는지 위치를 알려줌.
    • 즉, A1~A6에서 P[1][6]=1은 A1에서 잘랐다는것이고, ** **A2~A6인 P[2][6]=5는 A5에서 잘랐다는것을 의미한다.

  • 최적 분해를 구하는 예시를 직접 해본다면?

    • 먼저 P[1][6] 부터 시작하면 => (A1 (A2 A3 A4 A5 A6))
    • 이후는 당연히 P[2][6] 차례 => (A1 ((A2 A3 A4 A5) A6))
    • 다음은 P[2][5] 차례 => (A1 (((A2 A3 A4) A5) A6))
    • 다음은 P[2][4] 차례 => (A1 ((((A2 A3) A4) A5) A6))

  • 아래는 위에서 언급한 괄호 씌워주는 코드 (재귀로 가독성 좋게 구현)

    

최단거리(Floyd)

식도 중요하겠지만 아래 3개인 Floyd, LCS, OBST 는 그림 위주로 보면 동작을 이해하기가 편했다.

그림으로 보자.

• 이처럼 W행렬은 오른쪽의 가중치 방향 그래프를 인접행렬로 나타낸 모습이다.

  • 이음선(연결선)이 없으면 경로가 없는것이라 무한대로 표시하였다.

  • 이음선이 있으면 경로가 있는것이기 때문에 그때의 가중치를 표시하였다.
  • i=j 처럼 v1->v1이면 자기자신으로 가는경우라서 필요가 없기때문에 가중치를 0으로 표시하였다.

• D행렬이 각 정점들 사이의 최단거리들을 표시해둔 행렬이 될것이고,

  • 맨 초기인 D^(0)는 W행렬(인접행렬)과 동일하다.
  • 최종 결과인 D^(n)는 최종 구할 D행렬이 된다.
  • 이부분이 이해가 가지 않는다면, 아래를 먼저 계속 볼 것.

• 이부분도 대충보고 아래 그림을 통해 이해를 하자.
  • 위 그림은 코드 작성할때 사용하게될 식을 보여주려고 나타냈을 뿐

• 이 그림만 이해한다면?? Floyd 알고리즘을 이해한것과 마찬가지이다.
  • 앞서 얘기했듯이 D^(0)는 맨 초기상태인 W(인접행렬)과 동일하다.
  • 이때 v1정점을 경유하는 경우와 기존 경로의 경우의 거리 중 min값을 적용하는 모습이다.
  • 예로 빨간 동그라미 14의 경우?
    • v2->v5가 무한대였는데 v2->v1->v5 경로는 9+5=14로 무한대보다 min값이다.
• 참고로 P행렬은 어느 노드(정점)을 경유했는지를 기록하기 위한 행렬이다.
  • 위 예에선 v1노드를 경유하는 상태라서 1들이 기록이 된 것이다.

• 이번엔 다음 단계인 v2노드를 경유하는 경우를 적용해보는 그림이다.

  • 여기서 중요한점은 이렇게 그림으로 구할땐 편하게 구하는 법이있다.
  • 우선 빨간 네모 부분은 v2노드이므로 경유하는게 아니므로 당연히 값이 변동되지 않는다.
  • 다음으로 동그라미친 3을 잘 보면 가로, 세로방향의 빨간 네모안의 숫자와 줄이 그어져있다.
    이는 14+무한대와 현재 기록되어있는 3을 비교하는 모습이다.

  • 이런식으로 비교할 자리의 숫자와 가로, 세로 방향의 빨간 네모안의 숫자의 합과 비교하는 것이다.

  • 예를 들어 D[1][3] 의 자리의 경우??
    • 기존 기록된게 무한대이고, 빨간 네모의 가로 세로 숫자 합은 1+3=4이다.
    • 이를 비교하면 무한대>4 이므로 min 값은 4로 결정 되는것이다.

• v3, v4노드까지 경유했다고 가정하고 최종 v5를 경유하는 마지막 모습이다.

  • 이처럼 Floyd 알고리즘은 총 n번(=v노드 개수)을 전체적으로 반복한다.
  • 물론 내부적으로 행렬의 숫자들을 비교하는건 n^2이다.
  • 따라서 n*n^2=n^3으로 복잡도를 알 수 있다.

• 아래는 참고 코드

  

  • 1번째 알고리즘 : 최단경로의 길이만 구하는 알고리즘

  
  

  

  • 2번째 알고리즘 : 최단경로 길이 + 최단경로까지 구하는 알고리즘

  
  

• 아래는 최단경로(앞에서 구한 P활용) 구하는 코드

LCS(Find a Longest Common Subsequence)

이것에 대한 의미를 먼저 이해해보자.

subsequence란 ABCDE..에서 BCD 이런식으로 가져온것
common subsequnce는 여러 subsequnce에서 또 공통된 거를 의미
longest … 란 이 공통된것 중에서 젤 긴것을 구하는 것.

즉, A문자열과 B문자열 이렇게 주어졌을때 이것들의 LCS를 구한다는 의미이다.

• c(n,m)은 가장 긴 공통 값을 의미
• i=0 or j=0이면? 문자가 없는거니까 당연히 0
• a[i]==b[j]라면? 그 전인 c[i-1,j-1]가 남고, a[i]==[bj]니까 +1
  • 이는 당연히 A문자열과 B문자열에서 각각 V, V가 나왔다고 한다면 문자가 같으니까 +1을 하는것.
• a[i]!=b[j]라면? c배열의 왼쪽과 위의 값 중에서 제일 긴(max) 값으로 적용
  • 같은 문자가 나오지 않았으니 이전의 값들 중 긴(max) 값으로 사용한다는 것을 의미.
• 예로 표에 줄그은부분 해석하자면?
  • A:GVCE, B:GDV => 동일 : GV로 2개
• 위 식대로 진행한다면 오른쪽 배열처럼 나타낼 수 있는것.

• 마지막으로 이렇게 서로 다른 LCS를 어떻게 카운트하며 경로를 찾느냐가 문제이다.
  • 그래프 경로 구하던 BFS, DFS 같은 알고리즘으로 간단히 구할 수 있다.
    • 모서리 부분은 꼭 왼쪽 위에서 와야하지 바로 위나 바로 왼쪽에선 못온다.
      이성질을 조건으로 사용하여 BFS나 DFS로직을 구현하면 위 그림처럼 경로를 찾을 수 있다.
  • 이렇게 전부 찾게 되면 총 2개의 LCS를 구했다는걸 카운트 할 수 있다.

실제로 사용(응용)하는 문제

• 문제를 해석해보면, 키가 증가하면서 IQ가 감소하는 것을 찾아야 한다.

• 총 2개의 정답이 나온다.
• 비교하는 두 배열을 하나는 키 오름차순, 또다른 하나는 IQ 내림차순 정렬을 진행하는게 우선이다.
• 이후에는 공통된 이름 부분을 구하면 되므로 LCS 해결 방식으로 풀 수 있다.
• 주의할 점은 키 값이 동일하고 IQ가 동일한 경우들도 있는데 잘 처리해야한다.
  • 그림의 왼쪽 세로 배열처럼 동일 키의 경우 IQ가 상승(감소가 아닌)으로 정렬을 해야만 정확한 값을 얻을 수 있다.
    -> 이렇게 해야 키 오름차순, IQ 내림차순을 지킬 수 있음.

LIS(Longest Increasing Subsequence)

최장증가수열(LIS) : 각 원소가 이전 원소보다 큰 최장 증가 부분 수열을 의미

예를들어

• input: -60 -41 -100 8 -8 -52 -62 -61 -76 -52 -52 14 -11 -2 -54 46 가 있다면
• output: -60 -41 -61 -52 -11 -2 46 가 정답이다.

// length[]의 각 요소값은 최장 증가 부분 수열의 개수
for (int k = 0; k < n; k++) {
    length[k] = 1;
    for (int i = 0; i < k; i++) {
        if(arr[i] < arr[k]) {
            length[k] = max(length[k], length[i] + 1); // 점화식
        }
    }
}

참고할 응용 문제는 전깃줄BOJ2565 가 있다.

• A, B 건물에 있는 전깃줄이 교차하지 않게 하는 문제이다.
• 최소 몇개의 전깃줄을 제거해야 하는가? LIS 응용문제

OBST(Optimal Binary Search Tree)

이진검색트리는 순서가능집합 에 속한 item으로 구성된 이진 트리이고, 다음 조건을 만족한다.

• 각 마디는 하나의 키만 가짐
• 주어진 마디의 왼쪽 서브트리는 그 마디의 키보다 작거나 같다.
• 주어진 마디의 오른쪽 서브트리는 그 마디의 키보다 크거나 같다.

최적 이진 검색 트리를 구하는것이 목적이다.

• 이진 검색 트리가 여러가지 모양으로 나올 수 있는데, 이때 각 값들의 검색이 최적인 경우의 트리를 구하는 것이다.
• 따라서 각 키들의 검색 확률(즉, 검색 빈도수 느낌)을 받아서 이를 이용해 DP로 구한다.

점화식을 알아보기전에 “최적 이진 검색 트리”의 핵심을 알아보자.

• 아래 그림의 이진검색트리 5개의 그림을 보자.
• 키는 총 3개인 트리이며, 각 키의 검색확률이 주어진다.
• 이때, K3-K2-K1 같은 순서의 트리가 없는 이유는 “이진검색트리 조건에 불만족” 하기 때문이다.
  • 아래그림의 빨간색으로 그려진 트리가 그 예시이다.
• 평균검색시간을 구한 방법을 1번 트리로 예시를 들어보겠다.
  • 1번 트리는 K3가 루트이므로 K3는 한번의 비교만에 찾을 수 있다.
    반면에 K2는 2번의 비교, K1은 3번의 비교를 통해 찾을 수 있다.
  • 방금 구한 연산횟수를 적용해보면 1*(p3)+2*(p2)+3*(p1) 이 됨을 알 수 있다.

• A[1][2]를 구한다는것은 K1,K2 만 사용했을때 OBST를 구하는 것이다.
  • 그림을 보면 1번과 2번 트리를 고려해야하며 최적트리 확률값은 1.1임을 알 수 있다.(검색시간 계산하는 과정 설명은 앞서 설명했기에 생략)
• A[2][3] 을 구한다는것은 K2,K3 만 사용했을때 OBST를 구하는 것이다. (자세한 설명 생략)
• A[1][3] 을 구한다는것은 K1,K2,K3 전체를 사용했을때 OBST를 구하는 것이다. => 우리의 목적!
  • 이부분을 이해하는것이 가장 중요하다.
  • K1,K2,K3 가 있을때 가능한 이진검색트리의 모습은 5,6,7번 트리 모양이다.
  • 해당 모양을 보면 앞에서 구한 A[1][2], A[2][3] 들을 사용한다는 것을 알 수 있다. (DP)
    그렇다보니 바로 K1,K2,K3 전체를 사용했을때 OBST를 마지막에 구하고 있는 것이다.
  • 5번 트리의 평균검색시간을 구한 식을 이해해보자.
    • 앞서구한 A[2][3]를 바로 사용한다. 단, 기존에는 레벨(높이)이 루트로 한단계 더 낮았었는데 현재는 K1 아래에 있어서 레벨이 높아졌음을 고려해야한다.
      따라서 p2와 p3을 더한것이다. (연산횟수를 확률에 곱했던걸 기억하자. 여기서는 연산횟수가 한단계 커지는 거니까 p2, p3을 한번씩 또 더한것이다.)
    • 마지막 남은 K1은 바로 연산횟수와 확률을 곱한 1*(p1)으로 구해서 더해주면 끝이다.
  • 나머지 트리도 전부 똑같은 방식이다.

• 점화식(공식)은 무엇일까?
  
  • 왼쪽 서브트리는 A[1][K-1] 이고, 오른쪽 서브트리는 A[k+1][n] 이다.
  • 그리고 서브트리를 보면 한단계식 레벨이 높아졌기 때문에 연산횟수가 1씩 늘어났다.
    • 왼쪽서브트리는 p1~pk-1 을 더해주고, 오른쪽서브트리는 pk+1~pn 을 더해서 적용한다.
  • 마지막 루트에있는 키는 1*pk 이며 해당값까지 더해주면 된다.
• 특징을 잘 보면 p1~pn까지 전부 더해줬기에 시그마 수학기호를 사용해서 표현했다.
  • 확률의 전체합은 1이기 때문에 +1 로 생각해도 좋다.

아래의 OBST 구하는 예제를 따라해보면 2차원 배열로 구해지는 과정이 이해될것이다.

• 현재 A[i][i]때 값을 미리 넣은 상태이고 R은 루트를 표시한 것
• p1~p4 는 기존에 미리 주어지는 키 찾는 확률이다.

• A[1][2]는 K1이나 K2 둘다 확률이 같아서 루트를 뭐로 두든 상관없다.
  • K1이 루트라면 A[2][2]+p2+1*p1 이 되니까 9/8 이 나온다.
• 원래 K1, K2 확률이 달랐으면 K1-K2 트리랑 K2-K1 트리 2개를 고려했어야 한다.
  그러나 2개때는 무조건 확률이 큰 값이 루트인게 젤 최적 검색이 될테니까 사실 2개를 고려할 필요도 없긴 하다.
• 다만, 3개때부턴 3가지 경우 다 비교를 해줘서 제일 최소값을 구해야 한다.

• 3개일 때 모습
• 잘보면 배열이 대각선으로 채워짐을 알 수 있다.
  이는 앞서 배운 연쇄행렬곱셈 이랑 유사하니까 해당 파트를 참고하면 코드 구현까지도 문제 없을 것이다.

• 최종 모습

0-1 Knapsack(DP)

0-1 Knapsack란 배낭을 빈틈없이 채우는데 품목(item)은 쪼갤 수 없는 알고리즘이다.
여러 품목(item)들 중에서 정해진 무게(W)만큼 채워서 최대한 많은 이득을 취할 수 있는 문제를 다룬다.

무게 큰거부터 차례로 넣어가고, 남은건 쪼개서 담으면 되기때문에 탐욕(그리디)방법으로 풀 수 있다.
하지만 물건을 쪼갤수 없는 상태면?? 0-1 Knapsack의 문제가 되는것이다.
Fractional Knapsack과 0-1 Knapsack을 구별할 것

• Greedy는 Fractional Knapsack 가능, 0-1 Knapsack 불가
• 따라서 0-1 Knapsack은 DP로 구현

• P[n][W] = 최종 우리가 구할 값(n:전체 품목, W:주어진 전체 무게)
• : i번째 물건의 무게가 가방 여유 w무게 보다 큰 경우(즉, 물건 못 넣음)

• : i번째 물건의 무게가 가방 여유 w무게 보다 같거나 작은 경우(즉, 물건 넣을 수도 있음)

• 위 공식으로 P배열을 채워나간다.
  • 중요한점은 너무 쓸데없는 값들도 배열에 연산해서 저장을한다는 점이다.
  • 따라서 아래 그림을 보면 훨씬 연산량을 단축 시키는 방법이 있다.

• 모든 배열 값을 구할필요가 없으니까 필요한것만 구하자는 의미
• 단, 위 방법처럼 top-bottom(재귀) 으로 넘어가면 “연산량”을 줄일 수 있지 근본적인 “메모리 문제”가 있을 경우 이를 해결한다는게 아님. 착각X
  • 따라서 냅색 문제가 메모리 초과일 것 같을때 해당 문제 조건만 보지말고 다른 방향의 풀이 생각!
  • 참고(심화) 문제 -> 앱_7579

프리랜서의 일정 정하기

OPT[j] = max ( OPT[j-1], w[j] + OPT[p(j)] )

• OPT[j-1] : 일정 j 선택X
• OPT[p(j)]+w(j) : OPT[p(j)]는 p(j)<j인 일정들 중 젤 큰 index의 최적해(OPT) 값
  • p(j) : 일정 j와 겹치지 않고, j와 가장가까운(큰) 일정을 의미
  • w(j) : 일정 j의 비용
• BOJ는 없고 SWEA 에 4052 문제로 존재
  • 참고로 문제에 그림 조금 잘못 그려져 있음.
• 참고 : 프리랜서 일정 정하기

완전정보 게임(=NIM게임)

• “바둑돌 가져가기, coin move game” 는 확실히 이해하는것을 권장

• 참고 : 바둑돌 가져가기, coin move game, coin game, card game

제한된 비트 스트링의 개수

사용하게될 공식 자체는 S(k) = S(k-1) + S(k-2) 로써 매우 간단하지만, 아래 원리는 이해하고 넘어가자.

최대 공백 정사각형(Largest Empty Square)

• LES[x][y] = min( LES[x-1][y-1], LES[x][y-1], LES[x-1][y] ) + 1
LES[x][y] = 1 if 첫번째 행or열이 비었을때
LES[x][y] = 0 if 비어있지 않다면

• LES[x][y] 는 공백 정사각형 크기이며, [x,y]는 해당 정사각형의 우측하단 좌표를 의미

• 참고 : 최대 공백 정사각형

위상정렬 + DP

관련 문제로 BOJ2056 작업 해당 문제를 풀어보면, 아래의 그림의 개념을 조금 이해가 될 것이다.

• 참고하기 좋은 풀이 : 작업 풀이

TSP(외판원 순회)

백준2098_외판원 순회 -> 모든 마을을 단 한번씩만 방문하고 0번 마을로 돌아왔을 때의 최저 비용 구하라!

해당 문제는 조금 특별하다. dp의 매개변수로 비트마스킹을 사용하는 경우이다.

아래와 같은 상태를 정의하자

now_pos = 0; //시작 마을
visited_array = [1, 0, 0, 0, 0, 0];
total_cost = 0;

이때, 두가지 이점이 존재한다

1. 여러 경로에 의한 결과를 중첩해서 표현할 수 있게 됩니다.
2. 종료 시점을 명확하게 알 수 있습니다.

// [0→2→3→4] 의 경로로 이동한 상태와 [0→3→2→4]의 경로로 이동한 상태 "중첩 표현"
now_pos = 4;
visited_array = [1, 0, 1, 1, 1, 0];
total_cost = min(cost[0][2] + cost[2][3] + cost[3][4], cost[0][3] + cost[3][2] + cost[2][4]);

// 종료 시점 : now_pos 로부터 0번으로 돌아오는 비용(cost[i][0])만 추가로 더해주자
int result = Integer.INT_MAX;
for(int i = 1; i < N; i++){
	//now_pos = i, visited_array = [1, 1, 1, 1, 1, 1], 인 모든 state에 대해
	result = Math.min(result, MyClass[(some state)].total_cost + cost[i][0]);
}

MyClass[(some state)].total_cost 를 dp[i][j] 로 표현하자. 그리고 비트마스킹 적용하자.

• 사용 비트마스킹 예시 : [1, 0, 1, 1, 0, 0] → 001101(2) = 13
• i 는 2^N 가지, j 는 N가지 -> 비트마스킹 참고하면 범위가 이해하기 쉽다.

int dp[i][j];
//i-> 내가 지금까지 방문한 마을을 수로 표현 (001101(2) -> 13 -> 1,3,4번 마을 방문)
//j-> 현재 내가 있는 마을
//dp[i][j]-> 이런 상태가 완성되었을 때의 최솟값 (a.k.a total_cost) 

int dp[][] = new int[(1 << N)][N];
/* fill dp to Integer.INT_MAX; */
dp[1][0] = 0; //[1]:0번 마을을 방문했고, [0]:현재 0번 마을에 있음

최종 코드

for(int i = 1; i < (1 << N); i++){ //현재 내가 방문한 마을의 비트 값, visited_array
	for(int j = 0; j < N; j++){ //현재 내가 서 있는 마을, now_pos
		if(dp[i][j] == Integer.INT_MAX) continue; //불가능한 상태를 보려고 함
		for(int k = 0; k < N; k++){ //내가 다음으로 방문하려는 마을, next_pos
			if((i & (1 << k)) > 0) continue;
			//i는 방문했던 마을의 비트 값이었음. 그런데 지금 가려는
			//k번 마을이 이미 이 비트에 있으면 갈 수 없으므로 continue 처리
			dp[i | (1 << k)][k] = Math.min(dp[i | (1 << k)][k], dp[i][j] + cost[j][k]);
			//k번 마을의 비트를 채우면서 k번으로 이동해야 하므로 [i | (1 << k)][k]
			//현재 나의 최소값 (dp[i][j]) + 이동 비용(cost[j][k])을 다음 상태로 전달
		}
	}
}
int result = Integer.INT_MAX;
for(int i = 1; i < N; i++){
	result = Math.min(result, dp[(1 << N) - 1][i] + cost[i][0]);
} //N개의 비트를 모두 채운 상태 = (1 << N) - 1 로 표현 가능. 
//모두 방문한 경우의 dp값을 사용해야 하므로 (1 << N) - 1 을 사용한 것. 
//또한, 마지막에 다시 원래 마을로 돌아오는 비용을 더해줘야 하므로 cost[i][0] 을 사용한 것.

DP가 불가능한 경우는?

DP가 불가능한 경우는 무엇일지가 궁금했는데 DP에는 최적의 원칙(the principle of optimality) 이란게 있다.
최적의 원칙이 적용이 되어야 DP가 가능하다는 것이다.

예를들어 경로의 문제를 생각해보면

• vi->vj로 문제?, vk를 경유한다면 vi->vk로 가는 최단경로를 사용해서 vi->vk->vj
  vi->vk로 가는 문제였다면? vi->vk에 경유지는 없고 바로 최단경로로 끝.
• 근데, v->vk와 vi->vk->vj에서의 vi->vk가 서로 경로가 다르면 안된다는것.
  그렇게되면 최적의 원칙이 적용된다고 할 수 없다는 것.
• 최적의 원칙이 적용이 안되는 예들 중에 하나는 최장경로의 문제가 있다.