백준15483번 최소 편집
https://www.acmicpc.net/problem/15483
레벤슈타인 거리를 구하는 문제이다.
어떤 문자열의 i번째가 어떤 문자열의 j번째와 다르면
그 문자열의
i - 1번째, j - 1번째 편집 횟수 + 1 (교체)
i - 1번째 j번째 편집 횟수 + 1 (삽입)
i번째 j - 1번쨰 편집 횟수 + 1 (삭제)
이고
같다면
i - 1번째 j - 1번째 편집횟수와 같음을 이용하여
이차원 배열로 DP배열을 구현하는 문제이다.
처음에는 공백으로부터 시작해서 편집을 시작하므로
또는 한글자짜리도 일관성있게 풀기 위하여 공백으로 시작해서 푼다.
공백으로부터의 편집횟수를 미리 적어놓지 않으면 이후부터는 일반성이 좀더 떨어져 첫줄에 if문을 써야한다.
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
int array[1001][1001];//레벤슈타인 거리를 저장하는 배열
int min(int x, int y, int z)
{
if (x < y)
{
if (x < z) return x;
else return z;
}
else//y가 x보다 작음
{
if (y < z) return y;
else return z;
}
}
int main()
{
char string1[1001];
char string2[1001];
scanf("%s", string1);
scanf("%s", string2);
int length1 = strlen(string1);
int length2 = strlen(string2);
int i, j;
for (i = 0; i <= length1; i++)
{
array[i][0] = i;
}
for (i = 0; i <= length2; i++)
{
array[0][i] = i;
}
//처음에 공백이 있다 가정하고 그 문자열을 만들기 위해 필요한 편집수 저장
//각각 0 1 2 3 4...length
for (i = 1; i <= length1; i++)
{
for (j = 1; j <= length2; j++)
{
if (string1[i - 1] == string2[j - 1])
{
array[i][j] = array[i - 1][j - 1];//글자가 같으면 그 글자는 놔두면 되므로 이전 편집수를 그대로 가져오면 됨
}
else
{
array[i][j] = min(array[i - 1][j - 1], array[i - 1][j], array[i][j - 1]) + 1;//각각 교체, 삭제, 삽입의 과정이 하나 더 들어가므로 + 1
}
}
}
printf("%d", array[length1][length2]);
return 0;
}
Author And Source
이 문제에 관하여(백준15483번 최소 편집), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@honeyricecake/백준15483번-최소-편집저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)