[알고리즘의단계적사고] 과제3 풀이

1. 다음의 두 스트링에 대해 작은 것부터 해결하기(동적 계획) 알고리즘 알고리즘을 수행하여 편집 거리를 계산하라. 반드시 표를 그려서 결과를 보여야 한다. (10점)

편집 거리(Edit Distance)는 두 문자열 간의 변환을 최소화하는 데 필요한 편집 작업의 최소 개수를 측정하는 방법이다. 이 편집 작업에는 삽입, 삭제, 대체가 포함된다. 본 과제에서는 두 문자열 간의 편집 거리를 계산하기 위해 동적 계획법을 사용할 것이다. 문자열 A와 B를 설정한다. 예를 들어, A = `kitten`이고, B = `sitting`일 때, 두 문자열 간의 편집 거리를 계산하는 과정을 진행한다. 우선 문자열 A의 길이는 6이고, 문자열 B의 길이는 7이다. 동적 계획법을 사용하기 위해 2차원 배열을 생성한다. 이 배열의 크기는 (A의 길이 + x (B의 길이 + 로 설정한다. 배열의 각 요소는 substring의 편집 거리를 나타낼 것이며, 배열의 첫 번째 행과 첫 번째 열은 초기화할 필요가 있다. 배열의 첫 번째 행은 문자열 A를 비우고 문자열 B를 만드는 데 필요한 편집 작업의 수를 나타낸다. 즉, B의 각 문자 하나를 넣기 위해 해당 인덱스에 1을 더해가는 형태로 초기화된다. 마찬가지로 첫 번째 열은 문…