문서 편집기나, 키보드에는 다음과 같이 오타가 났을 때 수정된 단어를 추천해주는 기능이 있습니다. 이렇게 오타를 정정해주기 위해선 어떤 단어와 "비슷한 (가까운) 단어" 를 정의할 수 있어야 합니다. 그렇다면 어떤 단어와 "비슷한" 단어는 어떻게 정의할 수 있을까요? 이와 관련된 문제가 바로 Edit Distance (편집 거리) 문제입니다. Edit Distance : 두 String 이 얼마나 가까운지 나타내는 척도. String S1 과 S2 간의 edit distance 는 S1 을 S2 로 만들 때 아래 3가지 type의 연산을 최소한 몇 번 수행하여 만들 수 있는가로 정의합니다. Insertion (삽입) : S1 에 Symbol 하나를 추가 (위치는 무관) ex. MONDT -> MONEDT..

Dynamic Programming 기법으로 해결할 수 있는 대표적인 문제인 LIS (Longest Increasing Subsequence) 문제입니다. 먼저 Subsequence 의 정의부터 알아보겠습니다. 길이 n인 Sequence (ordered list) S = a1, a2, ... , an 이 주어졌을 때, sequence S' = ai1, ai2, ..., aik 가 1