백준 9252번 링크 LCS Longest common subsequence를 찾는 전형적인 DP 문제다. 점화식은 다음과 같다. $$ DPi = \begin{cases} DPi - 1 + 1 &\text{if } str[i] == str[j] \\ max(DPi - 1, DPi) &\text{o.w. }\end{cases} $$ 해당 문제에서는 결과값으로 LCS의 길이 뿐만 아니라 문자열도 요구한다. 두가지 방법이 있다. 2차원 배열을 만들어 해당 칸으로 온 방향을 기록해둔다. 단순하게 역추적한다. 2번 방법을 적용하여 풀었다. 코드

백준 7579번 링크 Knapsack problem Optimization version NP hard 문제이다. Optimization version의 정의는 다음과 같다. Input: Positive integers $$W, w{1}, ... , w{n}$$ and $$v{1}, ... , v{n}$$ Output: A subset S $$\subset$$ {1, ... , n} that maximizes $$\Sigma{i\in S}v{i}$$ subject to $$\Sigma{i\in S}w{i} \le W$$ 쉽게 말하면 n개의 배낭이 있고, 각 배낭은 가격과 가치가 있다. 한정된 돈으로 최대한의 가치를 얻는 방법을 묻는 문제다. weight와 value라고 표현하는 게 개인적으로 편한 것 같다. Deicision version 이 문제가 NP hard인 것을