최장 공통 부분 수열 편집하기 (부분)

==알고리즘==
동적 계획법을 이용한 최장 공통 부분 수열 알고리즘은 다음과 같은 방식으로 수행된다.
#두 문자열 X와 Y의 길이를 기반으로 2차원 DP 테이블을 생성한다.
#점화식을 이용하여 테이블을 채운다.
#최종적으로 LCS의 길이를 얻고, 역추적하여 실제 LCS를 구할 수 있다.

=== DP 테이블 생성 예시 ===
GACT CGAA와 TTCA CGCA를 비교해보자
# 먼저 각 문자열을 축으로 한 매트리스를 그리고 0으로 초기화한다.
# 한 글자씩 차례로 비교를 한다. 첫줄의 G-T, G-T, G-C, G-A, G-C, G-G, G-C, G-A를 비교하고 
#* 그 다음 줄의 A-T, A-T, A-C, A-A, A-C, ... , A-A 를 비교한다.
# 비교하다 서로 다른 문자가 나오면 한칸 위, 또는 한칸 왼쪽의 숫자 중 큰 숫자를 적는다.
# 비교하다 서로 같은 문자가 나오면 한칸 위 + 한칸 왼쪽 위, 즉 대각선 위의 숫자에 +1을 한 숫자를 적는다.
#* 첫 번째 줄의 경우 윗 칸은 모두 0이므로, 우선 0으로 진행하다 같은 문자가 나오면 1을 적게 된다.
#* 1이 한번 나오면 같은 줄의 그 뒤는 최소 1로 계속 이어진다. 그리고 같은 문자가 한번 더 나오면 2가 되고, 2가 계속 이어진다.
#* 두 번째 줄부턴 왼쪽와 위쪽을 모두 봐야 한다. 겹치는 문자가 없어도 윗칸이 1이면 이 줄에서도 1을 가져간다.
#** 이미 이 줄에서 1이 나오고 있었는데 위에서 1을 만나더라도 그대로 1이다. 둘 중 큰 숫자를 가져가는 것이지 더해지는 것이 아니다.
# 아래 예시의 경우 G와 G가 같기 때문에 그 대각선 위치의 0에서 1을 더한 값을 적는 것이다. 그리고 같은 줄 오른쪽이나 아래쪽은 2번의 규칙에 따라서 1이 죽 이어지게 된다.
# 두번째 줄에 A와 A가 처음 만났을 때는 대각선 위가 0이므로 여전히 1을 적는다. 그리고 2번의 규칙에 따라 계속 1이 이어지다가, 마지막에 A를 한번 더 만났을 때는 대각선 위의 숫자가 1이므로 2를 적게 된다.
# 이렇게 끝까지 수행을 하고 나면 DP 테이블이 완성된다.

{| class="wikitable"
!
!
!'''T'''
!'''T'''
!'''C'''
!'''A'''
!'''C'''
!'''G'''
!'''C'''
!'''A'''
|-
!
|'''0'''
|'''0'''
|'''0'''
|'''0'''
|'''0'''
|'''0'''
|'''0'''
|'''0'''
|'''0'''
|-
!'''G'''
|'''0'''
|0
|0
|0
|0
|0
|1
|1
|1
|-
!'''A'''
|'''0'''
|0
|0
|0
|1
|1
|1
|1
|2
|-
!'''C'''
|'''0'''
|0
|0
|1
|1
|2
|2
|2
|2
|-
!'''T'''
|'''0'''
|1
|1
|1
|1
|2
|2
|2
|2
|-
!'''C'''
|'''0'''
|1
|1
|2
|2
|2
|2
|3
|3
|-
!'''G'''
|'''0'''
|1
|1
|2
|2
|2
|3
|3
|3
|-
!'''A'''
|'''0'''
|1
|1
|2
|3
|3
|3
|3
|4
|-
!'''A'''
|'''0'''
|1
|1
|2
|3
|3
|3
|3
|4
|}

=== 백테스팅 과정 예시 ===
백트래킹 과정에서는 현재 셀 (i, j)에서 다음의 규칙을 따른다:

# '''문자가 같은 경우'''
#* 만약 X[i-1] == Y[j-1]라면, 이 문자는 LCS의 일부이다.
#* 그러므로 해당 문자를 LCS에 추가하고, '''대각선 왼쪽 위 (i-1, j-1)'''로 이동한다.
#* 이 과정은 “현재 문자를 LCS에 포함시켰으니, 이전 부분 문제로 넘어가자”는 의미이다.
# '''문자가 다른 경우'''
#* 만약 X[i-1]와 Y[j-1]이 다르다면,
#* '''위쪽 셀 (i-1, j)'''와 '''왼쪽 셀 (i, j-1)''' 중 더 큰 값(혹은 같은 값인 경우 둘 다)을 가진 방향으로 이동한다.
#* 여기서 둘 다 같은 경우는 '''모든 경로를 고려'''해야 한다는 의미이다. (모든 가능한 LCS를 구하기 위해 분기함)
# '''종료 조건'''
## i == 0 또는 j == 0이 되면, 더 이상 비교할 문자가 없으므로 역추적을 종료한다.

이런 경로를 따르기 때문에 백트레킹은 여러 경로로 분기가 되고, 여러 LCS를 구하는 과정이 된다.

* '''(괄호)'''는 일치한다는 의미이다. 이 땐 대각선 위로 진행한다.
* <s>'''취소선'''</s>은 일치하지 않는다는 의미이다. 이 땐 왼쪽 또는 위로 진행한다.
* <u>'''밑줄'''</u>은 그냥 선택되지 않은 경로이다. 이쪽으로 갈 수 있었지만 안 간 것을 표시하였다.

'''경로 1'''
{| class="wikitable"
!
!
!'''T'''
!'''T'''
!'''C'''
!'''A'''
!'''C'''
!'''G'''
!'''C'''
!'''A'''
|-
!
|'''0'''
|'''0'''
|'''0'''
|'''0'''
|'''0'''
|'''0'''
|'''0'''
|'''0'''
|'''0'''
|-
!'''G'''
|'''0'''
|0
|0
|0
|0
|0
|1
|1
|1
|-
!'''A'''
|'''0'''
|0
|0
|0
|1
|1
|1
|1
|2
|-
!'''C'''
|'''0'''
|0
|0
|'''(1)'''
|<u>'''1'''</u>
|2
|2
|2
|2
|-
!'''T'''
|'''0'''
|1
|<u>'''1'''</u>
|'''1'''
|'''1'''
|2
|2
|2
|2
|-
!'''C'''
|'''0'''
|1
|1
|2
|2
|'''(2)'''
|2
|3
|3
|-
!'''G'''
|'''0'''
|1
|1
|2
|2
|2
|'''(3)'''
|<u>'''3'''</u>
|3
|-
!'''A'''
|'''0'''
|1
|1
|2
|3
|'''<u>3</u>'''
|<s>'''3'''</s>
|<s>'''3'''</s>
|4
|-
!'''A'''
|'''0'''
|1
|1
|2
|3
|3
|3
|3
|'''(4)'''
|}

* A-A는 일치하므로 대각선 위로 이동한다.
* C-A는 일치하지 않으므로 왼쪽 또는 위쪽으로 갈 수 있는데, 여기선 왼쪽을 선택한다.
* A-G는 일치하지 않으므로 왼쪽 또는 위쪽으로 갈 수 있는데, 여기선 위쪽을 선택한다.
* G-G는 일치하므로 대각선 위로 이동한다.
* C-C도 일치하므로 대각선 위로 이동한다.
* A-T는 일치하지 않으므로 왼쪽 또는 위쪽으로 갈 수 있는데, 여기선 왼쪽을 선택한다.
* C-T는 일치하지 않으므로 왼쪽 또는 위쪽으로 갈 수 있는데, 여기선 위쪽을 선택한다.
* C-C는 일치하므로 대각선 위로 이동한다.
* 0이므로 종료한다.

CCGA는 하나의 LCS라는 결론이 났다.

'''경로 2'''
{| class="wikitable"
!
!
!'''T'''
!'''T'''
!'''C'''
!'''A'''
!'''C'''
!'''G'''
!'''C'''
!'''A'''
|-
!
|0
|0
|0
|0
|0
|0
|0
|0
|0
|-
!'''G'''
|0
|0
|0
|0
|0
|0
|1
|1
|1
|-
!'''A'''
|0
|0
|0
|0
|'''(1)'''
|1
|1
|1
|2
|-
!'''C'''
|0
|0
|0
|1
|1
|'''(2)'''
|'''<u>2</u>'''
|2
|2
|-
!'''T'''
|0
|1
|1
|1
|1
|<s>'''2'''</s>
|<s>'''2'''</s>
|2
|2
|-
!'''C'''
|0
|1
|1
|2
|2
|2
|2
|'''(3)'''
|3
|-
!'''G'''
|0
|1
|1
|2
|2
|2
|<u>'''3'''</u>
|<s>'''3'''</s>
|3
|-
!'''A'''
|0
|1
|1
|2
|3
|3
|'''<u>3</u>'''
|<s>'''3'''</s>
|4
|-
!'''A'''
|0
|1
|1
|2
|3
|3
|3
|3
|'''(4)'''
|}
ACCA도 하나의 LCS라는 결론이 난다.

이렇게 양쪽 방향으로 갈 수 있는 경우를 다 분기해서 가다 보면 모든 경로를 추적하여 모든 LCS를 구할 수 있다. 전체 답이 궁금하면 아래 파이썬 코드를 실행시켜 볼 수 있다.