만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

최소 편집

면접 대비

시간 제한2초메모리 제한512 MB

요약

두 소문자 문자열 A와 B가 주어질 때, 삽입, 삭제, 교체 연산을 최소로 사용해 A를 B로 바꾸는 편집 거리를 구한다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 문자열, 배열, 누적 합
정답자: 아직 제출이 없습니다

문제

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

$A$ 에 적용할 수 있는 연산은 다음 3가지다.

삽입: $A$ 의 한 위치에 문자 하나를 넣는다.
삭제: $A$ 의 문자 하나를 지운다.
교체: $A$ 의 문자 하나를 다른 문자로 바꾼다.

두 문자열이 주어졌을 때 최소 편집 횟수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 문자열 $A$ , 둘째 줄에 문자열 $B$ 가 주어진다. 두 문자열은 알파벳 소문자로만 이루어지며, 길이는 각각 1000글자를 넘지 않는다.

출력

첫째 줄에 $A$ 를 $B$ 로 만드는 최소 편집 횟수를 출력한다.

예제10

예제 1
입력
```
abc
ab
```
예상 출력
```
1
```
예제 2
입력
```
ca
abc
```
예상 출력
```
3
```
예제 3
입력
```
abc
cba
```
예상 출력
```
2
```
예제 4
입력
```
abcd
bcde
```
예상 출력
```
2
```
예제 5
입력
```
abababababa
aaaaaaaaaaa
```
예상 출력
```
5
```
예제 6
입력
```
for
whileforif
```
예상 출력
```
7
```
예제 7
입력
```
whilewhile
whalewhale
```
예상 출력
```
2
```
예제 8
입력
```
aaabaaa
acacaca
```
예상 출력
```
3
```
예제 9
입력
```
qwerty
dvorak
```
예상 출력
```
5
```
예제 10
입력
```
asdf
asdf
```
예상 출력
```
0
```

Loading...