문제 개요
정렬되지 않은 정수 리스트가 주어졌을 때, 가장 긴 증가 부분 수열(Longest Increasing Subsequence, LIS)의 길이를 구하는 문제입니다. 예를 들어 입력이 [10, 9, 2, 5, 3, 7, 101, 18]이라면, 증가 부분 수열 [2, 3, 7, 101]이 가장 길기 때문에 출력은 4가 됩니다.
해결 전략: 이진 탐색 활용
이 문제는 단순한 동적 계획법(DP)으로도 O(n²)에 풀 수 있지만, 이진 탐색(Binary Search)을 활용하면 O(n log n)의 시간 복잡도로 더 효율적으로 해결할 수 있습니다.
핵심 아이디어는 tails라는 배열을 유지하는 것입니다. tails[i]는 "길이가 i+1인 증가 부분 수열의 마지막 원소 중 가장 작은 값"을 의미합니다. 새로운 숫자가 들어올 때마다 이진 탐색으로 적절한 위치를 찾아 갱신하며, 배열이 확장될 때마다 LIS의 길이가 1씩 늘어납니다.
알고리즘 단계
- nums의 길이와 같은 크기의 tails 배열을 0으로 초기화합니다.
- size를 0으로 초기화합니다.
- nums의 각 원소 x에 대해 다음을 수행합니다.
- i := 0, j := size로 설정합니다.
- i와 j가 같아질 때까지 이진 탐색을 반복합니다.
- mid := i + (j - i) // 2로 계산합니다.
- tails[mid] < x이면 i := mid + 1, 그렇지 않으면 j := mid로 갱신합니다.
- tails[i] := x로 값을 갱신합니다.
- size := max(i + 1, size)로 갱신합니다.
- 최종적으로 size를 반환합니다.
Python 구현 예제
class Solution(object):
def lengthOfLIS(self, nums):
tails = [0 for i in range(len(nums))]
size = 0
for x in nums:
i = 0
j = size
while i != j:
mid = i + (j - i) // 2
if tails[mid] < x:
i = mid + 1
else:
j = mid
tails[i] = x
size = max(i + 1, size)
return size
ob1 = Solution()
print(ob1.lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18]))
입력
[10, 9, 2, 5, 3, 7, 101, 18]
출력
4
동작 과정 살펴보기
예제 입력에 대해 tails 배열이 어떻게 변화하는지 단계별로 살펴보겠습니다.
- 10 처리 → tails = [10] (size = 1)
- 9 처리 → tails = [9] (size = 1, 10을 9로 교체)
- 2 처리 → tails = [2] (size = 1)
- 5 처리 → tails = [2, 5] (size = 2)
- 3 처리 → tails = [2, 3] (size = 2, 5를 3으로 교체)
- 7 처리 → tails = [2, 3, 7] (size = 3)
- 101 처리 → tails = [2, 3, 7, 101] (size = 4)
- 18 처리 → tails = [2, 3, 7, 18] (size = 4, 101을 18로 교체)
최종적으로 size가 4이므로, 가장 긴 증가 부분 수열의 길이는 4입니다. 참고로 tails 배열 자체는 항상 실제 LIS와 일치하지는 않지만, 그 길이는 항상 정확하게 유지됩니다. 이 알고리즘은 각 원소마다 이진 탐색 한 번만 수행하므로 전체 시간 복잡도는 O(n log n)입니다.