中庸 中庸

문서 편집기나, 키보드에는 다음과 같이 오타가 났을 때 수정된 단어를 추천해주는 기능이 있습니다. 이렇게 오타를 정정해주기 위해선 어떤 단어와 "비슷한 (가까운) 단어" 를 정의할 수 있어야 합니다. 그렇다면 어떤 단어와 "비슷한" 단어는 어떻게 정의할 수 있을까요? 이와 관련된 문제가 바로 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

다이나믹 프로그래밍 (Dynamic Programming) 이란 재귀 (recursion)와 메모이제이션 (memoization) 을 사용하여 문제를 해결하는 기법입니다. memoization 은 recursive function 의 중간 결과를 저장하는 기법인데 말로 하면 와닿지 않으니 피보나치 수를 구하는 문제를 해결하며 다이나믹 프로그래밍과 메모이제이션에 대해 이해해보도록 하겠습니다. Fibonacci Number. 0을 포함한 자연수 n에 대해서 n-th Fibonacci Number Fn 은 다음과 같이 정의합니다. F0 = 0, F1 = 1 Fn = Fn-1 + Fn-2 (for n > 1) 얘를 들면 F5는 다음과 같습니다. 이제 재귀(Recursion)을 이용하여 Fibonnaci Numb..