최장 증가수열(Longest Increasing Subsequence) 문제는 왼쪽에서 오른쪽으로 나열된 수열이 있으면, 그 배열 순서를 유지하면서 크기가 점진적으로 커지면서 가장 긴 부분 수열을 추출하는 문제이다. 이때 문제마다 점진적으로 커지는 기준이 같은 수도 포함시킬 수 있으니 문제를 잘 읽고 풀어야 한다. 풀이 방법 기본적으로 최장 증가수열 문제를 풀 수 있는 방법은 크게 Brute-force 방식과 DP 방식 두 가지로 나눌 수 있다. 하지만 Brute-force 방식은 부분집합 알고리즘을 이용하여 지수 시간 복잡도를 가지기 때문에 추천할만한 방법은 아니다. 그러면 DP 방식을 통해 최장 증가수열 문제를 푸는 방법에 대해서 알아보자. Dynamic Programming n개의 숫자열 : a₁,..
