78. Longest Common Subsequence
최장 공통 부분수열(Longest Common Subsequence, LCS)은 두 수열에 대해 정의되는 수열로, 두 수열 $a, b$가 존재하고 수열 $c$가 $a$의 부분수열이면서 $b$의 부분수열일 때 $c$를 $a$와 $b$의 공통 부분수열이라고 하고, 그런 공통 부분수열 중 가장 긴 것을 $a$와 $b$의 최장 공통 부분수열이라고 한다. 예를 들어 수열 $a$와 $b$가 다음과 같을 때 두 수열의 LCS는 $\{5, 7, 4, 6\}$이다. $$a = \{2, {\color{red}5}, 2, {\color{red}7}, 1, {\color{red}4}, 3, {\color{red}6}\}$$ $$b = \{4, {\color{red}5}, {\color{red}7}, 6, {\color{red..
77. Longest Increasing Subsequence
최장 증가 부분수열(Longest Increasing Subsequence, LIS)은 수열의 부분 수열 중 값이 오름차순으로 나오면서 가장 긴 것을 말한다. 부분 수열은 원래의 수열에서 몇 개의 원소를 제거한 뒤 남는 수열을 의미하며, 연속되지 않는 원소들이 남을 수도 있다. 예를 들어 다음과 같은 수열 $a$가 있을 때 이 수열의 LIS는 $\{2, 4, 6, 7\}$이다. $$a = \{5, {\color{Red}2}, 6, {\color{Red}4}, 8, 3, {\color{Red}6}, {\color{Red}7}\}$$ LIS의 원소들은 단조증가하므로 LIS에는 같은 원소가 두 번 이상 나타날 수 없다. 또한 한 수열에 두 개 이상의 LIS가 존재할 수도 있다. 예를 들어 수열 $a$가 다음과..
