동적 프로그래밍 알고리즘(2)

두 문자열 X와 Y사이의 편집 거리(edit distance)

• 두 문자열 사이의 근접성 또는 유사성을 판단하는 척도
• X=x1x2... xn, Y=y1 y 2... ym
• 문자열 X를 Y로 변환하는 데 필요한 전체 편집 연산에 대한 최소 비용
  • 특정 위치에 새 문자를 삽입하는 연산 -> 삽입 비용 1
  • 특정 위치의 문자를 삭제하는 연산 -> 삭제 비용 1 
  • 특정 위치의 문자를 다른 문자로 변경하는 연산 -> 변경 비용 2
  • X=x1x2x3x4x5 = SNOWY
  • Y= y1 y 2 y3 y4 y 5 = SUNNY 
  • SNOWY -> SUNNY로 변경하는데 드는 편집 거리는 최소비용 4
• 스트링 편집 거리에서의 최적성의 원리
  • X와 Y사이의 편집 거리는 이들의 부분 문자열 사이의 편집 거리를 포함
    • x의 마지막 글자가 Y의 마지막 글자와 같거나 같게 변경된 경우
      • x1x2... xn-1과 y1 y 2... ym-1의 최소 편집 비용 + 마지막 글자의 변경  비용
    • X의 마지막 글자가 삭제되는 경우
      • x1x2... xn-1과 y1 y 2... ym의 최소 편집 비용 + X의 마지막 글자의 삭제 비용
    • Y의 마지막 글자가 삽입되는 경우
      • x1x2... xn과 y1 y 2... ym-1의 최소 편집 비용 + Y의 마지막 글자 삽입 비용
• 스트링 편집 거리 문제의 점화식
  • E {i, j] = min([E [i-1][j]+ del, E [i][j-1]+ins, E [i-1] E [j-1] + c
  • 성능 n x m
• 특징
  • P(i, j) <- E(i, j)로 선택되는 최솟값이 어떤 연산으로 결정되는 지를 표시
    • 적용된 편집 연산을 구할 수 있음

모든 정점 간의 최단 경로

• 두 정점 간의 최단 경로
  • 가중 방향 그래프에서 두 정점을 연결하는 경로 중에서 간선의 가중치 합이 가장 작은 경로
  • 유형
    • 하나의 특정 정점에서 다른 모든 정점으로의 최단 경로
      • 데이크스트라(Dijkstra) 알고리즘 (욕심쟁이 방법)
    • 모든 정점에서 다른 모든 정점으로의 최단 경로
      • 플로이드(Floyd) 알고리즘
  • 가정 -> 가중치의 합이 음수인 사이클은 조재하지 않음
  • 플로이드 알고리즘
    • 동적 프로그래밍 방법 적용
    • 그래프의 간선의 인접 행렬 표현을 활용하여 경유할 수 있는 정점의 범위가 1인 경로부터 시작해서 단계적으로 범위를 늘려 가면서 모든 정점 간의 최단 경로를 구하는 알고리즘
    • 인접 행렬 D^(k) = d^(k)_ij : 정점 i에서 j까지 경로 중 점점 1부터 k까지의 정점만을 경유할 수 있는 최단 거리
    • 점화식
      • D(i, j,0) -> 정점 없이 간선으로 직접 연결된 경로의 길이
      • D(i, j, k) -> 정점 i에서 j까지 경로 중 점점 1 부터 k까지 경유하는 최단 거리
      • D(i,j,k) = d_ij^k = min [d_ij^(k-1), d_ik^(k-1)+d_kj^(k-1)]
        • D^(0)을 구한다. -> D^(1) -> D^(2) ->... -> D^(k)
    •  성능 분석
      • O(|V|^3) : 정점의 개수의 3승
    • 특징
      • 최단 경로 자체를 구할 수 있음
        • P(i, j) <- k if  d_ij^(k-1) > d_ik^(k-1)+d_kj^(k-1)

저울 문제?

• 양팔 저울, n개의 추, 각 추의 무게 w_i (1 <=i <=n)
• 무게 M인 물체를 양팔 저울로 달 수 있는지 확인하는 문제
  • 추의 무게 w_i와 물체의 무게 M은 모두 정수라고 가정
• 저울 문제에서의 최적성의 원리
  • 선택된  k개의 추( s1, s2,..., sk) -> M = w_s1 + w_s2 +... + w_sk
    •  선택된 추에 n번 추가 포함되지 않는다면
      • 1~(n-1) 번까지의 추를 이용하여 무게 M인 물체를 달 수 있는 지의 문제
    • 선택된 추에 n번 추가 포함된다면 (s_k = n이라고 가정)
      • n번 추를 제외시키면 w_s1+w_s2+...+w_s(k-1) = M - w_sk
        • 1~(n-1) 번까지의 추를 이용하여 무게 M-w_sk인 물체를 달 수 있는 지를 확인하는 문제
• 저울 문제의 점화식
  • S(i, k)=1 또는 0 
    • 1번부터 i번까지의 추를 이용하여 무게 k인 물체를 달 수 있는 지의 여부
      • S(i,0) = 1, S(i, 음수) = 0, S(0, k) = 0
  • S(i, k) = max [S(i-1, k), S(i-1, k-w_i)], 1 <=i <=n, 1 <=k <=m
• 성능 분석 : O(nm) 추의 개수 x 물체의 무게
• 특징
  • 무게 k의 증가를 추의 무게의 최대공약수 단위로 증가시키면 더 효율적
• 테이블 S와 W_i를 이용하면 사용된 추를 구할 수 있음
  • S(n-1, M-w_n) = 1 -> n 번추 사용
  • S(n-1, M)=1 -> n 번추 미사용
  • 물체의 무게가 2^n 보다 크면 모든 경우를 따져 보는 직관적인 방법보다 비효율적
    • 직관적 알고리즘 -> n개의 추로 조합 가능한 모든 경우의 수 -> O(2^n)
    • M>2^n 이면 nM > n2^n > 2^n 이므로 O(nM)인 알고리즘이 직관적인 알고리즘보다 비효율적
  • M과 w_i가 정수가 아니면 동적 프로그래밍 방법을 사용할 수 없다.

cf)

1 : 연쇄 행렬 곱셉 문제의 점화식, 2: 스티링 편집 거리 문제의 접화식, 3 : 플로이드 알고리즘의 점화식, 4: 저울 문제의 점화식

프림 알고리즘과 크루스칼 알고리즘은 최소 신장 트리를 구하는 알고리즘이고, 데이크스트라 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이다. 이들 세 알고리즘은 모두 욕심쟁이 방법이 적용된 대표적인 알고리즘이다.