[Algorithm] 개념2 : 1_Dynamic Programming 동적 프로그래밍

미쳐 복습해 기억안나

 

1. Dynamic Programming 동적 프로그래밍

• 작은 부분문제들부터 모두 해결한 후 부분 문제들의 해를 이용해 큰 문제를 해결하는 방법(부분 문제들 사이에 의존적)
• Bottom-up
• 한 번 구한 값은 절대 바뀌지 않고, 여러번 사용될수 있음
• 최적성원칙 Principle of Optimality : 최종해는 최적의 부분해들로 이루어져 있어서 최종해 안에 최적의 부분해들이 포함됨
• 최적성원칙 Principle of Optimality 를 만족하는 문제에서만 동적 프로그래밍 사용 가능

 

• 최적화 문제 : 주어진 문제에 대하여 가장 최적인 해답을 찾는 문제
• shortest path문제 - all pairs shortest paths 문제(alll to all 알고리즘)
  • 각 정점에서 다른 모든 정점까지의 최단거리
  • W[i][j] : 그래프의 인접행렬식으로 표현해 품. 
  • D^k[i][j] : v1~vk중 몇개를 거쳐서 vi에서 vj로 가는 최단경로 길이
  • 시간복잡도 O(n^3) -> Greedy O(n^2)에 비해 안좋음
  • 표에 십자가 그려서 업데이트하면서 푸는 거!
  • 예전에 배웠던 시작점이 정해져 있는 다익스트리xn번 = O(n^3)
  • 동적 방법 Floyd-Warshall : O(n^3)
  • 문제의 입력에 대해 최적의 해답을 주는 재귀관계식 설정 - 상향적으로 최적의 해답 계산
• Dynamic : 단일 출발점 최단경로 문제는 Greedy보다 안좋음. 그러나 Greedy가 풀지 못하는 0-1 knapsack문제를 풀 수 있음.
• 0-1 knapsack 문제
  • P[i][w] :  무게가 w를 넘지 않도록 i번째까지의 물건을 담은 경우의 최대이익
    • 현재 물건을 담아도 무게가 넘치지 않을 때 max(직전단계의 최대 이익, 현재 물건의 이익+현재 물건 제외하고 직전까지의 최대이익) 를 선택. 
    • 현재 물건을 담으면 무게가 넘칠 경우 직전단계의 최대 이익 선택. 아래는 식으로 정리.
    • P[i][w] = 무게가 안넘치면 max(P[i-1][w]), pi+P[i-1][w-wi]), 무게가 넘치면 P[i-1][w]     ** max(P[i-1][w]), pi+P[i-1][w-wi]) : 직전단계까지의 최대이익과 현재물건을 담았을 때 지금까지의 최대이익 중 큰 값
    • => 원하는 하나의 P[i][w]값만 구하려면 P[i-1][w]와 P[i-1][w-wi]만 구하면 됨
  • 표 그려서 위에서부터 아래로 숫자 채우는 거! 마지막에 화살표 경로로 답 나옴 - 근데 이렇게 모든 항을 구하면 너무 오래 걸림. 
  • 개선 -> 위에서부터 쪼개보며 필요한 항만 파악 후 아래부터 Botton-up으로 계산해서 구함. 이때 계산 시 pi+P[i-1][w-wi]에서 w-wi가 음수가 나오면 P[i-1][w])를 써야함을 유의!!
  • => O(min(2^n, nW))
  • 분할정복으로 풀어도 O(2^n). 아직 더 좋은 알고리즘 모름. 더 좋은 게 없다는 것도 증명 못했음. -> NP문제

 

• 문제의 일반적인 분류
  1. P문제 : Polynomial Time 알고리즘(최악의 시간복잡도가 n^k임)을 찾은 문제
  2. Intractable(다루기 어려움. Polynomial Time 알고리즘이 없음)라고 증명된 문제
  3. NP문제 : Polynomial Time알고리즘도 못찾고 Intractable하다고 증명되지도 않았음. Nondeterministic Polynomial Time 

 

• 이진 탐색 트리
  • 왼쪽 자식 노드들은 나보다 작음. 오른쪽 자식 노드들은 나보다 큼. 중복값 없음.
  • 값이 n개인 이진트리는 n개의 internal node와 n+1개의 external node(찾는 값이 트리에 없는 값일 때 도착하는 곳)로 구성.
  • 이진 탐색 트리를 탐색하는 데 드는 비용 Cost = (각internal node를 탐색할 확률 * internal node의 깊이)의 총합 + (각external node를 탐색할 확률 * external node의 깊이-1)총합     **-1하는 이유는 external 노드는 도착하면 비교없이 종료니까
• 최적 이진 탐색 트리 Optimal Binary Search Tree
  • Cost를 최소로 한 이진 탐색 트리. 가장 탐색하기에 최적인 트리.
  • cost를 구하는 과정을 부분문제로 나누어 상향적으로 계산해간다. cost(TREE) = cost(L) + cost(R). (근데 이걸 고대로 안하고 정리해서 함)
  • 시간복잡도 O(n^3)
  • 역계단식 표 그려서 엄청 계산하는 거!
  • 결과트리는 OBST라 함
  • 전체 계산이 끝나면 전체 트리 뿐만아니라 각 노드를 루트로 하는 서브트리들도 알 수 있음
  • 완성된 트리의 cost구하는 법 : cost = 각 inner노드의 깊이*확률 총합 + 각 external노드의 (깊이-1)*확률 총합