📌 최장 증가 부분 수열 알고리즘(LIS)
가장 긴 증가하는 부분 수열 시리즈를 풀었음에도 기억이 나지 않아 이번 기회에 다시 정리해 보는 알고리즘.
📕 O(N^2) 동적 계획법(DP) 접근법의 한계
- dp[i]를 "수열의 i번째 원소로 끝나는 가장 긴 증가하는 부분 수열의 길이"라고 정의.
- 모든 i(1 ≤ i ≤ N)에 대하여, j를 1부터 i-1까지 순회하면서, 만약 arr[j] < arr[i]라면 dp[i] = max(dp[i], dp[j] + 1)로 갱신.
- 최종적으로 dp 배열 전체에서 최댓값이 가장 긴 증가하는 부분 수열의 길이.
단점: 시간 복잡도가 O(N^2)이므로, N이 수만 ~ 수십만 이상으로 커지면 시간이 매우 오래 걸림.
📕 O(N*log N) 접근 (이분 탐색 활용)
O(N*log N) 알고리즘은 증가하는 부분 수열을 직접 구하는 대신,길이만 같은 가상의 부분 수열(혹은 배열)을 하나 유지하며, 새 원소가 들어올 때마다 이분 탐색을 통해 적절한 위치를 찾아 수열을 갱신하는 방식
알고리즘의 개념
- 원소를 하나씩 순회
- 만약 현재 원소가 LIS 배열의 가장 마지막 원소보다 크면 바로 뒤에 붙임 ->증가하는 부분 수열이 하나 더 길어졌다는 의미
- 그렇지 않다면, LIS 배열에서 현재 원소가 들어갈 수 있는 위치(이분 탐색)를 찾아 해당 원소로 치환
- 이렇게 모든 원소를 처리한 뒤, LIS 배열의 길이가 가장 긴 증가하는 부분 수열의 길이
🔖예시
10,20,10,30,20,50를 순회하며 최장 증가 부분 수열을 찾는다고 가정
- 초기: LIS 배열 =
- 10 처리: 비어 있으므로 뒤에 붙임
→ 10
- 20 처리: 마지막 원소(10)보다 20이 크므로 뒤에 붙임
→ 10,20
- 10 처리: 마지막 원소(20)보다 작으므로, 10이 들어갈 위치를 이분 탐색으로 찾음
→ 치환 대상(20) 자리를 10으로 교체
→ 10,10 이지만, 실제로는 첫 번째 원소(10)가 그대로 있고, 두 번째 원소(20)를 10으로 교체
→ 결과: 10,10(길이 2)
- 30 처리: 마지막 원소(10)보다 30이 크므로 뒤에 붙임
→ 10,10,30
- 20 처리: 마지막 원소(30)보다 작으므로, 20이 들어갈 위치 탐색
→ 세 번째 원소(30)를 20으로 교체
→ 10,10,20
- 50 처리: 마지막 원소(20)보다 50이 크므로 뒤에 붙임
→ 10,10,20,50
마지막에 10,10,20,50가 남았는데, 길이는 4로, 실제 LIS 10,20,30,50의 길이도 4.
🔭 더 나아가기
가장 긴 증가하는 부분 수열의 길이뿐 아니라 어떤 원소들로 구성되었는지 알고 싶다면, “부모” 정보를 추적
- 각 원소가 LIS 배열에서 어느 “인덱스”에 들어갔는지를 기록.
- 이를 위해 pos[i]를 설정. (i번째 원소가 LIS 배열의 어느 위치에 들어가는지)
- 또, 각 원소가 연결되기 전 “어떤 원소”를 이어받았는지 추적.
- 이를 위해 parent[i]를 설정. (i번째 원소 바로 전에 부분 수열에 들어온 원소의 인덱스)
- 모든 원소를 순회한 뒤, LIS 배열의 마지막 위치를 찾아 해당 인덱스를 시작으로 parent를 거슬러 올라가게 함.
- 거슬러 올라가면서 원소들을 저장한 뒤, 마지막에 뒤집으면 실제 “가장 긴 증가하는 부분 수열”이 됨.
구현 시, “LIS 배열” 자체에는 원소 값만 넣는 것이 아니라 해당 원소의 인덱스를 저장하거나, 별도의 관리가 필요.
✒️ 예시문제
수열
가장 긴 증가하는 부분 수열
가장 긴 증가하는 부분 수열 2
가장 긴 증가하는 부분 수열 3
가장 긴 증가하는 부분 수열 4
최대 공통 증가 수열
증가하는 부분 수열
우물 안에서 무언가 만드는 사람