다이나믹 프로그래밍 - 6. 편집 거리

문제

두 문자열 A와 B가 주어졌을 때, A에 연산을 최소 횟수로 수행해 B로 만드는 문제를 "최소 편집" 문제라고 한다.

A에 적용할 수 있는 연산은 총 3가지가 있으며 아래와 같다.

삽입: A의 한 위치에 문자 하나를 삽입한다.
삭제: A의 문자 하나를 삭제한다.
교체: A의 문자 하나를 다른 문자로 교체한다.
두 문자열이 주어졌을 때, 최소 편집 횟수를 구하는 프로그램을 작성하시오.

입력
첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 소문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력
첫째 줄에 최소 편집 횟수를 출력한다.

구현코드

import java.io.*;

public class Main {
	
	static String str1;
	static String str2;
	
	// 최소 편집 거리(Edit Distance) 계산을 위한 다이나믹 프로그래밍
	public static int editDist(String str1, String str2){
		int n = str1.length();
		int m = str2.length();
		// 다이나믹 프로그래밍을 위한 2차원 DP 테이블 초기화
        int[][] dp = new int[n + 1][m + 1];
		// DP 테이블 초기 설정
        for (int i = 1; i <= n; i++) {
            dp[i][0] = i;
        }
        for (int j = 1; j <= m; j++) {
            dp[0][j] = j;
        }
		
        // 최소 편집 거리 계산
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                // 문자가 같다면, 왼쪽 위에 해당하는 수를 그대로 대입
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                // 문자가 다르다면, 세 가지 경우 중에서 최솟값 찾기
                else { // 삽입(왼쪽), 삭제(위쪽), 교체(왼쪽 위) 중에서 최소 비용을 찾아 대입
                    dp[i][j] = 1 + Math.min(dp[i][j - 1], Math.min(dp[i - 1][j], dp[i - 1][j - 1]));
                }
            }
        }

        return dp[n][m];
	}
	
	public static void main(String[] args)throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		str1 = br.readLine();
		str2 = br.readLine();
		// 최소 편집 거리 출력
        System.out.println(editDist(str1, str2));
	}
}

코드해석

스트링 편집 거리(string edit distance) 알고리즘이란 두 문자열의 유사도를 측정하기 위해 사용되는 알고리즘으로 Levenshtein distance(LD)라고도 합니다.
스트링 편집 거리 알고리즘은 논문, 보고서 등의 표절 검사, DNA 염기 서열의 유사도 검사 등에 사용되어지고 있다고 한다.

이 문제는 책의 저자인 블로그를 참고하였다.
https://blog.naver.com/ndb796/220870218783