中庸 中庸

Shortest Path 를 구하는 대표적인 Alogorithm 으로는 Dijkstra Algorithm 이 있었습니다. Dijkstra 알고리즘의 key lemma 는 다음과 같았습니다. Dijkstra Algorithm 에서 (아직 방문 안 한 vertex 들 중) vertex s 에서부터의 shrotest path 길이가 가장 짧은 vertex 를 v라 하면 그 길이는 실제 s에서 v로의 shortest path 길이와 같다. 위 key lemma 는 weight 가 negative 인 edge 가 존재할 경우 성립하지 않습니다. 그 이유는 다음과 같습니다. 그렇다면 negative edge 가 있는 경우에도 동작하는 Shortest path 를 구하는 Algorithm은 무엇이 있을까요? The ..

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