정렬 거리 편집하기 (부분)

=== 동적 계획법 시뮬레이션 ===
이 시뮬레이션은 동적 계획법 구성이 이해가 어려운 사람들을 위해, 이해를 돕기 위한 풀이이므로, 이해가 되는 사람은 그냥 위의 소스코드를 본느 것이 훨씬 간편하다.

문자열 X=infill, Y=final의 정렬 거리를 계산해보자. 비용은 아래와 같다.

* 일치(match): 보상 (예: -1)
* 불일치(mismatch): 벌점 (예: 1)
* 삽입/삭제(gap): 고정 비용 (예: 2)

우선 매트릭스는 아래와 같이 초기화된다.

* 여기서 0, 2, 4, ... 로 증가하는 것은 우선 아무것도 없는 것과 infill, final을 비교하는 것이다. 글자수만큼 삽입이 일어난다.

{| class="wikitable"
!
!
!i
!n
!f
!i
!l
!l
|-
!
|0
|2
|4
|6
|8
|10
|12
|-
!f
|2
|1
|
|
|
|
|
|-
!i
|4
|
|
|
|
|
|
|-
!n
|6
|
|
|
|
|
|
|-
!a
|8
|
|
|
|
|
|
|-
!l
|10
|
|
|
|
|
|
|}
그 다음 f열부터 계산을 진행한다. 오른쪽으로 나아가며 비교를 하는 것은, "i", "in", "inf", "infi"와 같은 해당 인덱스까지의 문자열이다.

* "f"와 공백을 비교하면 삽입/또는 삭제가 일어나므로 2이다.
* "f"와 "i"를 비교하면, 불일치이기 때문에 1이다.
* "f"와 "in"를 비교한다. 3가지 경우로 비교를 해야 한다.
** '''"f*"와 "in":''' 앞서 이미 "f"와 "i"를 비교했으므로, 그 비용을 이용하고, "f"는 한 글자 밖에 없으니 "n"을 삽입한다.
*** 즉 왼쪽 열을 이용할 수 있으며, 1+2 = 3이 된다.
** '''"in"과 "*f"''': "i"는 삽입하는 것으로 하고, "f"와 "n"을 치환한다.
*** 즉 대각선 열을 이용할 수 있으며, 2+1 = 3이 된다. 
** '''"in"과 "**"''': 그냥 f를 지워버리고 in을 삽입하는 것으로 한다.
*** 즉 위쪽 열을 이용할 수 있으며, 4+2 = 6이 된다.
** 이렇게 3가지 비용을 비교해서 가장 작은 3을 넣는다.

{| class="wikitable"
!
!
!i
!n
!f
!i
!l
!l
|-
!
|0
|2
|4
|6
|8
|10
|12
|-
!f
|2
|1
|3
|
|
|
|
|-
!i
|4
|
|
|
|
|
|
|-
!n
|6
|
|
|
|
|
|
|-
!a
|8
|
|
|
|
|
|
|-
!l
|10
|
|
|
|
|
|
|}

* "f"와 "inf"를 비교한다. 동일하게 3가지 경우로 비교를 해야 한다.
** 위쪽 열을 본다. 이는 f를 삭제하는 경우에 해당한다. "inf"가 공백, 즉 "***"과 비교되기 때문이다.
*** 여기 "f"의 삭제비용까지 하면 8이다.
** 대각선 열을 본다. 이는 이전 비교 결과까진 그대로 두고, 마지막 글자끼리 비교하는 경우에 해당한다.
*** 대각선은 "in"과 공백, 즉 "**"가 비교된 결과이다. 여기 "f"와 "f"의 정렬 비용을 더하는데, 같은 값이니 -1을 하면 3이 된다.
** 왼쪽 열을 본다. 이는 "inf"의 "f"를 삽입하는 경우에 해당한다.
*** 왜냐하면 "in"과 "f"가 이미 비교가 되었으므로, "in"의 "f"는 그냥 삽입/삭제를 하는 것이다. 3+2 = 5가 된다.
** 즉 3가지를 비교하면 3이 가장 작으므로 3을 입력한다.

{| class="wikitable"
!
!
!i
!n
!f
!i
!l
!l
|-
!
|0
|2
|4
|6
|8
|10
|12
|-
!f
|2
|1
|3
|"3"
|
|
|
|-
!i
|4
|
|
|
|
|
|
|-
!n
|6
|
|
|
|
|
|
|-
!a
|8
|
|
|
|
|
|
|-
!l
|10
|
|
|
|
|
|
|}

* 이렇게, 각 칸에선 위, 대각선(↖), 왼쪽 열을 이용한 3가지 경우의 수 중 작은 것을 입력한다.
* 행에 해당하는 "X" 중 우리가 현재 선택한 것을 "x"라고 한다면, 
** 위의 값을 이용하는 것은 x의 값을 "삭제"하는 경우에 해당하고,
** 대각선은 앞선 비교를 다 인정하고, "x"를 Y의 마지막 값과 비교하여 "치환(또는 일치)"하는 경우에 해당하고
** 왼쪽은 비교 대상 y를 "삽입"하는 경우에 해당한다.
** 즉 현재의 비용 기준을 고려하면, min(윗 값 + 2, 대각선 + 또는 - 1, 왼쪽 값 + 2)를 입력하는 단순한 반복이다.

{| class="wikitable"
!
!
!i
!n
!f
!i
!l
!l
|-
!
|0
|2
|4
|6
|8
|10
|12
|-
!f
|2
|1
|3
|3
|5
|7
|9
|-
!i
|4
|
|
|
|
|
|
|-
!n
|6
|
|
|
|
|
|
|-
!a
|8
|
|
|
|
|
|
|-
!l
|10
|
|
|
|
|
|
|}
첫번째 열은 다 채웠다고 생각하고 다음 열의 3번째 로 넘어가보자. "fi"를 "infi"와 비교하고 있다.

* 일단 계산부터 하자면, 윗열 5+2, 대각선 열 3-1, 왼쪽 열 4+2를 비교해서 2가 들어가면 된다.
* 하지만 의미를 뒤짚어 보자면,
** 윗칸: "f와" infi"를 비교한 위치다. 즉, "f"와 "infi"를 비교한 걸 쓰고, 지금 "fi"의 "i"는 지워버리겠다는 거다. 
** 대각선: "f"와 "inf"를 비교한 위치다. 즉 각각 앞글자까지의 비교값을 쓰고, "i"와 "i"를 비교하겠다는 거다. 같으므로 -1이 된다.
** 왼쪽칸: "fi"와 "inf"를 비교한 위치다. 즉 이 비교값을 쓰고, 뒤의 "infi"의 "i"를 삽입하겠다는 것이다.

{| class="wikitable"
!
!
!i
!n
!f
!i
!l
!l
|-
!
|0
|2
|4
|6
|8
|10
|12
|-
!f
|2
|1
|3
|3
|5
|7
|9
|-
!i
|4
|3
|2
|4
|"2"
|
|
|-
!n
|6
|
|
|
|
|
|
|-
!a
|8
|
|
|
|
|
|
|-
!l
|10
|
|
|
|
|
|
|}
이렇게 매트리스를 다 채운다면 아래와 같이 된다. 정렬 비용은 매트리스에 이미 들어간 값이 업데이트 되는 경우는 없으므로, 최종 결과만 봐도 값이 나온 과정을 복기할 수 있다.
{| class="wikitable"
!
!
!i
!n
!f
!i
!l
!l
|-
!
|0
|2
|4
|6
|8
|10
|12
|-
!f
|2
|1
|3
|3
|5
|7
|9
|-
!i
|4
|1
|2
|4
|2
|4
|6
|-
!n
|6
|3
|0
|2
|4
|3
|5
|-
!a
|8
|5
|2
|1
|3
|5
|4
|-
!l
|10
|7
|6
|3
|2
|2
|4
|}
정렬 비용은 가장 마지막에 위치한 "4"이다.