Levenshtein 거리와 동적 계획법에 대해 설명드리겠습니다.
Levenshtein 거리는 두 문자열 사이의 편집 거리를 의미합니다. 편집 거리는 두 문자열을 같은 문자열로 만들기 위해 필요한 최소한의 연산 수를 말합니다. 연산은 삭제, 삽입, 교체로 이루어집니다.
DP 테이블을 생성할 때, 각 행과 열에 할당하는 값을 설명드리겠습니다.
DP 테이블은 2차원 배열로 구성되며, 행과 열의 인덱스는 문자열의 인덱스를 나타냅니다. DP 테이블의 각 요소는 두 문자열의 편집 거리를 의미합니다.
DP 테이블을 생성할 때, 각 행과 열에 할당하는 값을 다음과 같이 설명할 수 있습니다.
- DP 테이블의 첫 번째 행은 첫 번째 문자열의 첫 번째 문자를 기준으로 편집 거리를 계산합니다. 첫 번째 문자열의 첫 번째 문자가 두 번째 문자열의 첫 번째 문자와 같으면, 편집 거리는 0입니다. 다르면, 편집 거리는 1입니다.
- DP 테이블의 첫 번째 열은 첫 번째 문자열의 첫 번째 문자를 기준으로 편집 거리를 계산합니다. 첫 번째 문자열의 첫 번째 문자가 두 번째 문자열의 첫 번째 문자와 같으면, 편집 거리는 0입니다. 다르면, 편집 거리는 1입니다.
- DP 테이블의 나머지 요소는 이전에 계산된 편집 거리를 기반으로 계산됩니다. 이전에 계산된 편집 거리는 다음과 같이 계산됩니다.
DP[i][j] = min(DP[i-1][j-1] + (s1[i-1] == s2[j-1] ? 0 : 1), DP[i-1][j] + 1, DP[i][j-1] + 1)
이러한 방법으로 DP 테이블을 생성하면, 두 문자열의 편집 거리를 계산할 수 있습니다.
DP 테이블을 생성하는 방법을 예를 들어 설명드리겠습니다.
예를 들어, 두 문자열 s1 = "kitten"과 s2 = "sitting"의 편집 거리를 계산하겠습니다.
DP 테이블은 다음과 같이 생성됩니다.
| | s2[0] | s2[1] | s2[2] | s2[3] | s2[4] | s2[5] |
| --- | --- | --- | --- | --- | --- | --- |
| s1[0] | 0 | 1 | 2 | 3 | 4 | 5 |
| s1[1] | 1 | 1 | 2 | 3 | 4 | 5 |
| s1[2] | 2 | 2 | 1 | 2 | 3 | 4 |
| s1[3] | 3 | 3 | 2 | 1 | 2 | 3 |
| s1[4] | 4 | 4 | 3 | 2 | 1 | 2 |
| s1[5] | 5 | 5 | 4 | 3 | 2 | 1 |
DP 테이블의 마지막 요소 DP[5][5]은 두 문자열의 편집 거리를 의미합니다. DP[5][5]의 값은 3입니다. 따라서, 두 문자열 "kitten"과 "sitting"의 편집 거리는 3입니다.
2025-04-26 07:54