中庸 中庸

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..