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

=== 백테스팅 과정 예시 ===
백트래킹 과정에서는 현재 셀 (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를 구할 수 있다. 전체 답이 궁금하면 아래 파이썬 코드를 실행시켜 볼 수 있다.