오딩이

최장 증가 수열 : Longest Increasing Subsequence 📌 최장 증가 수열이란? 어떤 배열이 있을 때, 배열의 순서를 유지하면서 크기가 점진적으로 커지는 가장 긴 부분수열을 추출한 것입니다. 예를들어, [4, 2, 3, 1, 5, 6]이라는 배열이 있을 때 LIS는 [2, 3, 5, 6]이 됩니다. 점차 증가하는 배열은 [4, 5, 6] 또는 [2, 3, 5, 6] , [3, 5, 6] 등 여러 부분집합이 있을 수 있지만, 그 중 부분집합의 최대 배열을 의미하므로 LIS는 [2, 3, 5, 6]이 됩니다. 🔍 가장 먼저 생각해 볼 수 있는 풀이는 완전탐색(Brute-Force)입니다. 수열의 모든 부분 집합을 구하여 그 부분 집합이 증가 수열인지를 판단합니다. 완전탐색으로 풀 경우 부..