문제 개요
숫자로 이루어진 리스트가 주어졌을 때, 그중에서 가장 길게 증가하는 부분 수열(Longest Increasing Subsequence, LIS)의 길이를 찾는 것이 목표입니다. 예를 들어 입력이 [6, 1, 7, 2, 8, 3, 4, 5]라면, 가장 긴 증가 부분 수열은 [2, 3, 4, 5, 6]이므로 정답은 5가 됩니다.
해결 접근 방식
단순한 동적 계획법(DP)으로도 풀 수 있지만, 여기서는 이진 탐색을 활용해 시간 복잡도 O(n log n)만에 해결하는 더 효율적인 방법을 소개합니다.
핵심 아이디어는 tails라는 보조 배열입니다. tails[k]에는 길이가 k+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를 반환합니다.
구현 예제
class Solution(object):
def solve(self, nums):
tails = [0 for _ 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
ob = Solution()
nums = [7, 2, 8, 3, 9, 4, 5, 6]
print(ob.solve(nums))실행 결과
입력:
[7, 2, 8, 3, 9, 4, 5, 6]
출력:
5
동작 설명 및 복잡도
입력 [7, 2, 8, 3, 9, 4, 5, 6]에서 가장 긴 증가 부분 수열은 [2, 3, 4, 5, 6]이므로 결과는 5입니다. 각 원소를 처리할 때마다 이진 탐색으로 삽입 위치를 찾기 때문에 한 번의 처리에 O(log n)이 소요되며, 전체 시간 복잡도는 O(n log n), 공간 복잡도는 O(n)입니다. 완전 탐색 기반의 O(n²) DP 풀이보다 입력 크기가 클 때 훨씬 유리합니다.