"사전 기반으로 단어 수정해주는 프로그램 만들기" 라는 제안이 있었는데, 진짜 사전 가지고 만들려면 버겁고 귀찮은 부분이 많을것 같아서 대신 fuzzy search 부분만 문제로 낼게


편집거리(edit distance)는 두 문자열이 얼마나 비슷한지를 정량화 하는 개념임.

가장 대표적인걸로 Levenshtein distance가 있음

https://en.wikipedia.org/wiki/Levenshtein_distance


 Levenshtein distance는 두 문자열 a, b 가 있을 때, a에 한개의 문자를 추가, 한개의 문자를 삭제, 한개의 문자를 다른 문자로 변경하는 3가지 연산을 여러번 가해서 문자열 b로 만드는데 필요한 최소의 연산갯수로 정의됨.

이걸 효율적으로 구하는 알고리즘은 위키피디아 링크에 나와있음.


입출력 예시

입력:

kitten

sitting


출력:

3


저번 SAT 문제는 너무 어렵게 낸것 같아서 미안하다,,

이번건 풀만 할거라고... 생각해