Xeraph@NCHOVY

문자열 A는 ABCABBA 라고 하고, 문자열 B가 CBABAC라고 하자. 문자열 A, B를 각각 X축, Y축으로 한 글자씩 배열하여 아래와 같 모양으로 벡터 그래프를 만들어낼 수 있다. 종류별로 수평 벡터, 수직 벡터, 대각선 벡터가 있는데, 수평 벡터와 수직 벡터는 그냥 단방향으로 그어놓은 것이고, 대각선 벡터는 문자가 서로 같은 점을 끝점으로 해서 만든다. 즉, 아래 그림에서 (3, 1)이나 (5, 2) 처럼 문자가 같으면 그 위치에 대각선이 그어지는 것이다.
이 그림에 경로가 하나 표시되어 있다. 경로 하나를 따라가면 공통 문자열이나 편집 명령을 얻어낼 수 있다. 공통 문자열은 대각선 벡터의 끝점이 표시하는 문자다. 즉 저 경로에서 대각선 벡터 끝점만 뽑아서 나열하면 CABA가 된다. 편집 명령은 수평/수직 벡터를 따라가면서 만든다. 오른쪽으로 가면 삭제 (D), 아래쪽으로 가면 입력 (I) 으로 해석할 수 있다. 위 경로를 따라가면 1D (첫번째 문자 삭제), 2D (두번째 문자 삭제), 3IB (세번째 문자 뒤에 B를 입력), 6D (6번째 문자 삭제), 7IC (7번째 문자 뒤에 C를 입력)이 나온다.

문자열 A 원본 편집 시작 : ABCABBA
A, B 삭제 : CABBA
B 입력 : CBABBA
B 삭제 : CBABA
C 입력 : CBABAC
문자열 B 완성됨 : CBABAC

여기에서 알 수 있는 것은 같은 경로에서 대각선 벡터 따면 공통 문자열이 나오고 수평/수직 벡터를 따면 편집 명령이 나오니 LCS와 SES 문제는 Dual 관계라는 것이다. (Dual을 뭐라고 번역하더라) LCS(longest common sequence)는 주어진 문자열 2개의 가장 기다란 공통 문자열을 찾아내는 문제이고, SES(shortest edit path)는 문자열 A를 문자열 B로 변환할 때 최소한의 편집 명령 (edit script) 을 찾아내는 문제이다. 그리고 SES 문제는 (0, 0)에서 (N, M)까지 만들어진 벡터 그래프에서 최소한의 대각선 아닌 벡터(즉, 수평 벡터와 수직 벡터)를 포함하는 경로를 찾는 것과 동등하다. 이 벡터 그래프에 가중치를 준다고 하자. 대각선은 0, 수평/수직 벡터는 1로 주는 것이다. 이렇게 하면 LCS/SES 문제는 (0,0)에서 (N, M)에 이르는 가장 짧은 경로를 찾는 문제의 형태로 바뀐다. 오~

그럼 이제 직관적으로 생각할 수 있는 것은 그리디 알고리즘이다.