[알고리즘] 동적 프로그래밍 알고리즘(스트링 편집 거리, 최단 경로, 저울 문제)
스트링 편집 거리
두 문자열 X, Y 사이의 편집 거리
n개의 X와 m개의 Y
문자열 X를 Y로 변환하는 데 필요한 전체 편집연산에 대한 최소 비용 (특정 위치에 새 문자를 삽입, 문자 삭제, 다른 문자로 변경하는 연산)
최소 편집 비용 == 편집 거리
최적성의 원리 만족
(X와 Y 사이의 편집 거리는 포함한다 - 부분 문자열 사이의 편집 거리를)
- X의 마지막 글자가 삭제된 경우
x1 x2 ... xn-1 , y1 y2 ... ym 의 최소 편집 비용 + x의 마지막 글자 xn의 삭제 비용 - Y의 마지막 글자가 삽입된 경우
x1 ... xn, y1 ... ym-1 + y의 마지막 글자 ym의 삽입 비용 - X의 마지막 글자와 Y의 마지막 글자가 같거나 같도록 변경된 경우
x1 ... xn-1 , y1 ... ym-1 의 최소 편집 비용 + 마지막 글자 xn <-> ym 변경 비용
점화식
X_i=x_1 x_2 ... x_i 와 Y_i
성능 : O(nm)
모든 정점 간의 최단 경로
가중 방향 그래프에서 두 정점을 연결하는 경로 중 간선의 가중치 합이 가장 작은 경로
- 단일 출발점 최단 경로
하나의 특정 정점에서 다른 모든 정점으로의 최단 경로 -> 데이크스트라 알고리즘 욕심쟁이 방법 - 모든 정점 간의 최단 경로
플로이드 알고리즘
가중치의 합이 음수인 사이클이 존재하지 않는다.
경유할 수 있는 정점의 범위가 1인 경로부터 시작해서 |V|까지인 경로까지 하나씩 범위를 늘려 가면서 모든 정점 간의 최단 경로를 한꺼번에 구한다.
가중치 => 인접 행렬로 표현
인접 행렬 (테이블로 표현) D^(k)=(d^(k)_(ij)) 정점 i에서 정점 j까지의 경로 중 정점 1부터 k까지의 정점만을 경유할 수 있는 최단 경로의 길이
d^(k-1)_(ij) 에서 d^(k)_(ij) 어떻게 계산하지?
최단 경로 자체를 구하려면 k값을 저장하게 된다.
저울 문제
무게 M인 물체를 양팔 저울로 달 수 있는지 확인하는 문제
추의 무게와 물체의 무게 모두 정수여야한다.
최적성의 원리
n개의 추로 무게 M인 물체를 확인하는 문제
S(i, k)=1 or 0
1부터 i번까지의 추를 이용하여, 무게 k인 물체를 달 수 있는가?
1 True, 0 False
점화식
S(i,k)=max[S(i-1, k), S(i-1, k-w_i)]
i-1번째까지 k무게를 다는 경우와 i-1번째 무게를 재서 k에서 무게를 뺀값. 둘 중 큰 값을 고른다.
무게를 달 수 있다 -> 어떤 추를 이용해서?
테이블 S, Wi를 이용하면 사용된 추를 구할 수 있다
S(n-1, M-w_n)=1 -> n번째 추가 빠졌는데 1이면, n번째 추가 들어가면 M이라는 추를 사용할 수 있다.
S(n-1, M)=1 -> M번째 추를 다는데 n번추를 사용하지 않아도됨
성능
추가 n개 있으면 추를 사용하느냐 마냐 경우의 수 -> 2^n
M > 2^n 이면 nM > n2^n > 2^n 이므로
O(nM)인 알고리즘이 직관적인 알고리즘보다 비효율적
추의 무게와 물체의 무게가 정수가 아니면 동적프로그래밍 방법 적용 불가