728x90
편집 거리
책 이것이 코딩 테스트다의 편집 거리
해설
✔ 두 문자가 같은 경우 : dp[i][j] = dp[i - 1][j - 1]
✔ 두 문자가 다른 경우 : dp[i][j] = 1 + MIN(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1])
두 문자가 같은 경우 점화식이 위 처럼 되는 이유는 다음과 같다.
두 번째 그림에서 3번을 예시로 설명하겠다.
S 를 가지고 SA 를 만들기 위한 최소 편집 거리에 교체 연산을 추가로 실시
즉, SAU -> SAT 로 만들기 위한 것이라고 생각하면 된다.
* DP[2][3] = DP[1][2] + 교체 연산
근데 만약에 U 랑 T 문자가 같다고하면 교체 연산을 추가로 할 필요가 없기 때문에 왼쪽 위의 값을 그대로 대입해주면 된다.
구현
public class Main {
static String A;
static String B;
public static void main(String[] args) {
input();
System.out.println(solution());
}
static void input() {
Scanner sc = new Scanner(System.in);
A = sc.nextLine();
B = sc.nextLine();
}
static int solution() {
int n = A.length();
int m = B.length();
// 다이나믹 프로그래밍을 위한 2차원 DP 테이블 초기화
int[][] dp = new int[n + 1][m + 1];
/*
DP 테이블 초기 설정
빈 문자열을 가지고 해당 문자를 만들 수 있는 최소 편집 거리로 초기화
Ex. dp[2][0] 에 저장된 값은
빈 문자열을 가지고 su 를 만들 수 있는 최소 편집거리를 의미
*/
for (int i = 1; i <= n; i++) {
dp[i][0] = i;
}
for (int k = 1; k <= m; k++) {
dp[0][k] = k;
}
// 최소 편집 거리 계산
for (int i = 1; i <= n; i++) {
for (int k = 1; k <= m; k++) {
// 문자가 같다면, 왼쪽 위에 해당하는 수를 그대로 대입
if (A.charAt(i - 1) == B.charAt(k - 1)) {
dp[i][k] = dp[i - 1][k - 1];
}
// 문자가 다르다면, 세 가지 경우 중에서 최솟값 찾기
else { // 삽입(왼쪽), 삭제(위쪽), 교체(왼쪽 위) 중에서 최소 비용을 찾아 대입
dp[i][k] = 1 + Math.min(dp[i][k - 1], Math.min(dp[i - 1][k], dp[i - 1][k - 1]));
}
}
}
return dp[n][m];
}
}
References
728x90
'Algorithms > 문제 풀이' 카테고리의 다른 글
2020 카카오 신입 공채 : 문자열 압축 (0) | 2022.01.18 |
---|---|
[BOJ 18353] 병사 배치하기 (0) | 2022.01.11 |
이것이 코딩테스트다 : 금광 (0) | 2022.01.07 |
[BOJ 14502] 연구소 (0) | 2022.01.06 |
[BOJ 15686] 치킨 배달 (0) | 2022.01.03 |