[코딩 인터뷰 준비] Edit distance - 편집 거리 알고리즘

편집 거리 문제를 처음 풀어보던 저 역시, 가장 단순한 방법부터 떠올렸던 경험이 있습니다. 삽입, 삭제, 바꾸기 세 가지 연산을 모든 문자 위치마다 시도해 보는 방식이었죠. 개념 자체는 어렵지 않아서 실제로 손코딩으로 그려보았는데, 작은 입력에서도 눈 깜빡할 사이에 경우의 수가 폭발적으로 늘어나는 게 눈에 보였습니다. 시간 복잡도가 입력 길이에 대해 지수적으로 커지는 바람에, n이 20만 넘어가도 응답을 못 받을 정도였어요. 그때 저는 단순 무식한 방법 대신, 이미 계산한 작은 부분 문제를 저장해서 재활용하는 동적 프로그래밍 접근으로 방향을 틀게 되었습니다. 2차원 표를 채워 나가는 과정은 처음엔 어색했지만, 한 번 손으로 그려 본 뒤로는 오히려 LCS 같은 인접 문제와도 연결되어 보이는 통찰을 얻게 되었습니다. 이번 글에서는 제가 실제로 부딪혔던 초기화 실수와 인덱스 off-by-one, 그리고 표를 어떻게 그려야 덜 헷갈리는지 정리해 보았습니다.

너무나 유명한 고전 알고리즘입니다. 컴퓨터 과학과 언어학 등에서 많이 사용하고 있습니다. 한 문자열을 다른 문자열로 변환하는 데 필요한 최소 작동 횟수를 세어 두 문자열(예: 단어)이 서로 얼마나 다른지를 수량화하는 방법입니다. 거리 편집은 자연어 처리에서 응용 프로그램을 찾는데, 여기서 자동 철자 보정은 해당 단어와 거리가 낮은 사전에서 단어를 선택하여 철자가 틀린 단어의 후보 수정을 결정할 수 있습니다. 생물정보학에서는 문자 A, C, G, T의 문자열로 볼 수 있는 DNA 서열의 유사성을 정량화하는 데 사용할 수 있습니다.

이번에 풀어볼 문제는 정확하게는 레벤슈타인 편집 거리(Levenshtein Edit Distance) 문제입니다. 레벤슈타인의 거리 연산은 문자열에서 문자를 제거, 삽입 또는 대체하는 최소 거리를 구하는 것입니다. 일반적으로 레벤슈타인 거리라는 편집 거리와 구분 없이 사용하는 경우가 많습니다.

문제: 두 문자열 word1과 word2가 주어졌을 때 word1이 word2가 되는 최소 변경 횟수를 구하라.

다음 세 가지 옵션이 한 단어에 대해 변경으로 허용됩니다:

1. 문자 삽입
2. 문자 삭제
3. 문자 바꾸기

예제 1) Input: word1 = "horse", word2 = "ros"
Output: 3
설명:
horse: 'h'를 'r'로 바꾸면 rorse
rorse: 'r'을 삭제하면 rose
rose: 'e'를 삭제하면 ros

예제 2) Input: word1 = "intention", word2 = "execution"
Output: 5
설명:
intention에서 't'를 삭제하면 inention
inention에서 'i'를 'e'로 바꾸면 enention
enention에서 'n'을 'x'로 바꾸면 exention
exention에서 'n'을 'c'로 바꾸면 exection
exection에서 'u'를 삽입하면 execution

널리 알려졌지만 결코 쉬운 문제는 아닙니다. 가장 단순한 방법으로 접근하면 재귀적인 방법을 떠올릴 수 있을 것입니다. 재귀 프로그래밍으로 모든 경우(삽입, 삭제, 바꾸기)를 다 해보고 최소 거리를 반환하면 됩니다. 모든 단어마다 3가지 경우를 계산해야 하므로 시간 복잡도가 O(3^N)임을 알 수 있습니다. 당연히 지수 복잡도이기 때문에 만족할 만한 답이 아님을 알 수 있습니다.

LCS(Longest Common Subsequence) 문제를 접해 보았다면 어딘가 유사하다는 점을 눈치 채셨을 것입니다. 이전 포스팅에 정리해 놓았으니 궁금하시다면 한번 살펴보시기 바랍니다. 편집 거리 전에 풀고 나면 어떻게 접근해야 하는지 생각하는 데 도움이 될 것입니다.

LCS는 위키피디아를 보면 편집 거리 종류로 레벤슈타인 거리와 함께 언급되어 있으니 그만큼 비슷한 종류의 문제라는 뜻입니다. 약간의 디테일만 조금 다릅니다.

다시 문제를 살펴보겠습니다. 재귀 프로그램을 발전시켜야 하는 문제가 있습니다. 재귀 프로그래밍을 최적화시키는 방법은 크게 두 가지입니다. 메모이제이션과 동적 프로그래밍.

LCS 문제와 유사하게 2D 배열로 이전에 중복해서 계산했던 부분을 저장하고 필요할 때마다 꺼내 쓰는 방법을 쓰면 비교적 쉽게 답을 찾을 수 있습니다. 총 4가지 경우를 저장하고 꺼내 써야 합니다.

1. 문자를 바꾸는 경우: dp[i][j] = dp[i - 1][j - 1] + 1
2. 문자를 삽입하는 경우: dp[i][j] = dp[i][j - 1] + 1
3. 문자를 삭제하는 경우: dp[i][j] = dp[i - 1][j] + 1
4. 두 문자가 같은 경우: dp[i][j] = dp[i - 1][j - 1]

위의 로직이 가장 핵심적인 부분입니다. 아직 감이 안 왔다면 표를 그려 보면 도움이 됩니다. 예로 Horse와 ros 거리를 표로 만들어 보겠습니다.

2D 배열을 완성시키면 이런 식의 데이터가 저장될 것입니다. 따라서 horse와 ros의 편집 거리는 맨 오른쪽 밑 가장자리 값인 3임을 알 수 있습니다.

이제 코드를 작성해 보겠습니다.

public int minDistance(String word1, String word2) {
        int n = word1.length();
        int m = word2.length();
        int[][] dp = new int[n + 1][m + 1];
        for(int i = 0; i < dp.length; i++){
            for(int j = 0; j < dp[i].length; j++){
                if(i == 0) dp[i][j] = j;
                else if(j == 0) dp[i][j] = i;
                else {
                    char c1 = word1.charAt(i - 1);
                    char c2 = word2.charAt(j - 1);
                    if(c1 == c2){
                        dp[i][j] = dp[i - 1][j - 1];
                    } else {
                        dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
                    }
                }
            }
        }
        return dp[n][m];
    }

주의할 점은 가로의 0번째 행과 0번째 열은 아무것도 아닌 문자(null)과 비교하는 베이스 케이스를 채워 놓는다는 부분입니다. 예를 들면 null vs h = 1, null vs ho = 2 ... null vs horse = 5 이런 식입니다.

이상 편집 거리 알고리즘에 대해서 알아보았습니다. LCS와 비슷한 원리라는 점을 알아 둔다면 나중에 면접 문제에서 나왔을 때 당황하지 않고 올바르게 해답에 접근할 수 있을 것입니다. 그리고 실무에서도 단어 유사도 등을 측정하는 데 많이 쓰이므로 알아 두면 꽤 쓸모가 있는 알고리즘입니다.