[알고리즘] 12. Dynamic Programming (2)

6. 편집거리 (Edit Distance)

문제 정의: 편집 거리는 한 문자열을 다른 문자열로 변경하기 위해 필요한 편집 연산들의 최소 수를 의미한다. 연산의 종류는 [삽입, 삭제, 교체, 유지]가 있다.

Idea: $D(i,j)$는 두 문자열 $S_1,\ S_2$ 에 대한 편집거리를 나타낸다고 하자. 제일 오른쪽 문자부터 비교를 하면서 연산들 중 값이 가장 작아지는 것을 고르면 된다.

$D(i, j)$의 값은 아래 4가지 값들 중 가장 작은 값이다.

• $D(i, j-1) + 1$ - 삽입
• $D(i-1, j) + 1$ - 삭제
• $D(i-1, j-1) + diff(i, j)$ - 같으면 유지(0), 다르면 교체 (1)

https://slideplayer.com/slide/16315448/

 

7. LCS (Longest Common Subsequence)

문제 정의: 부분 서열 (Subsequence)은 주어진 서열에서 일부 문자를 삭제한 후에 남은 문자들을 순서대로 연결하여 만들어지는 서열을 의미한다. LCS는 X와 Y가 주어질 때 X와 Y의 공통 부분 서열 중 가장 긴 것을 의미한다. X의 길이가 m, Y의 길이가 n일때 X와 Y의 LCS의 길이를 구해보자.

Idea: $LCS(i, j)$를 $X_i$, $Y_j$ 의 LCS의 길이라고 하자. 우리가 구해야할 값은 $LCS(m, n)$ 이다. 기본적인 아이디어는 위의 편집거리와 유사하다.

• $LCS(i, j)=0$   : $i=0$ 이거나 $j=0$인 경우
• $LCS(i, j)= LCS(i-1, j-1)+1$   : $X_i$, $Y_j$가 같으면 LCS의 길이가 1 추가된다.
• $LCS(i, j)= max(LCS(i-1, j), LCS(i, j-1))$   : $X_i$, $Y_j$가 다르면 삽입 또는 삭제 연산을 통해 다음 문자를 보면 된다.

 

8. Global Alignment

문제 정의: 두 개의 문자열을 "-"을 포함하도록 확장하여 같은 길이의 문자열로 만드는데 대응되는 문자들의 쌍들의 score 합이 최대가 되는 alignment를 구해보자.

Idea: $\sigma(x,y)$를 문자 x와 문자 y에 대한 유사도라 하자. 유사도는 $x=y$이면 점수가 많고, $x\neq y$일 때 빈칸이 적을수록 점수가 더 많다. $\sigma(-,-)$는 0 이하의 점수이다. 이번에도 편집 거리와 유사한 방식으로 두 Sequence A, B의 유사도를 가장 크게 만드는 Global Alignment를 구해보자. $V(i, j)$는 $A_i, B_j$ 사이의 유사도이고, 최종 정답은 $V(m, n)$이다.

 

[기저 조건]

• $V(0, 0) = 0$
• $V(i, 0) = V(i-1, 0) + \sigma(A_i,-)$
• $V(0, j) = V(0, j-1) + \sigma(-,b_j)$

 

[$V(i, j)$는 아래 세 가지 값들 중 최댓값이다.]

• $V(i-1, j-1)+\sigma (A_i, B_i)$
• $V(i-1, j)+\sigma (A_i, -)$
• $V(i, j-1)+\sigma (-, B_i)$

 

9. 최대 공백 정사각형

문제 정의: 주어진 $n\times n$크기의 흑백 이미지에서 검은 점을 포함하지 않는 가장 큰 빈 정사각형 찾기

Idea: $LES(x, y)$를 (x,y)를 우측하단 꼭짓점으로 하는 최대 정사각형의 크기라고 하자.

• $LES(x,y)=0$   : (x,y)가 비어있지 않은 경우
• $LES(x,y)=1$   : 첫번째 행 또는 열의 (x, y)가 비어있는 경우
• $LES(x,y)=min (LES(x-1,y-1), LES(x,y-1), LES(x-1,y)) + 1$   : 나머지 픽셀 (x,y)가 비어있는 경우 (하나라도 작으면 작은 사이즈의 정사각형을 가지고 계산해야함)

 

10. 동전 거스름돈

문제 정의: N원의 거스름 돈을 돌려줄 때, 최소 개수의 동전을 사용하여 거스름 돈을 돌려주는 방법을 구해보자.

Idea: $C(i, j)$를 크기 $D_i$ 동전으로 $j$원을 거슬러 줄때의 동전 개수라고 가정하자. $C(i,j)$는 아래 두 값 중 더 작은 값이다.

• $C(i, j-D_i) + 1$   : $D_i$원을 거슬러준 경우 동전 하나 추가
• $C(i-1, j)$   : 거슬러 주지 않고 다음 돈으로 스킵

 

11. 기타 주제들

• 금화 모으기
• 프리랜서의 일정 정하기
• 집합에서 k개 선택하기
• 숫자판 놀이
• 완전 정보 게임 - 바둑돌 가져가기