[알고리즘] 동적 프로그래밍

동적 프로그래밍 해결법

• 단순 하위문제들(simple subproblems): 전체적인 최적화 문제를 하위문제들로 반복적으로 쪼개는 어떠한 방법이 존재해야 한다. 더욱이 i, j, k 등과 같이 단지 약간의 색인들로서 하위문제들을 정의하는 단순한 방법이 존재해야 한다.
• 하위문제 최적화(subproblem optimization): 전체적인 문제에 대한 최적화 해법은 하위문제들을 위한 최적 해결법들의 합성이어야만 한다.
• 하위문제 중복(subproblem overlap): 관련되지 않은 하위문제들에 대한 최적화 해법들은 공통적으로 다른 하위문제들을 포함할 수 있다.

LCS 문제

긴 공통의 서브시퀀스(Longest Common Subsequence, LCS) 문제는 두 개의 문자열에 대해 두 문자열의 부분문자열 중 가장 긴 문자열을 찾는 문제이다.

패턴 매칭 알고리즘

부르트 포스(Brute-Force) 알고리즘 보이어-무어 알고리즘(Boyer-Moore) 알고리즘 크누스-모리스-프랫 알고리즘 헤프만-코딩 알고리즘 그리디 메소드

...작성중...