알고리즘 - 가장 긴 증가하는 부분 수열 문제 (Longest Increasing Subsequence Problem)
가장 긴 증가하는 부분 수열 문제 (Longest Increasing Subsequence, LIS) 는 다이나믹 프로그래밍의 전형적인 문제 중 하나로써, 다이나믹 프로그래밍의 예시로 자주 나오는 문제이다. 비교적 쉬운 O(N^2) 알고리즘과 좀 더 어렵지만 효율적인 O(N log N) 알고리즘이 있다. 부분 수열 어떠한 수열에서 일부 숫자들을 지워서 만들어지는 수열을 부분 수열이라고 한다. 자기 자신도 자기 자신에 대한 부분 수열이라고 볼 수 있다. 예를 들어 [1, 2, 3, 5, 2, 8] 에 대한 부분 수열은 [1], [1, 3, 5] 등이 있다. 증가하는 부분 수열 부분 수열 중 오름차순으로 정렬되어 있는 부분 수열을 증가하는 부분 수열이라고 한다. 예를 들어 [1, 2, 3, 5, 2, 8] ..
