백준 / 실버 2 / 11053 / 가장 긴 증가하는 부분 수열
백준 / 골드 2 / 12015 / 가장 긴 증가하는 부분 수열 2

빡센 이진탐색 문제 푸니까 힐링이 필요할 것 같아서 귀여운 사모예드 사진을 올렸습니다.

생각해봅시다!

• 위의 두 문제는 수열이 주어졌을 때, 최장 증가 부분 수열의 길이를 구하는 문제입니다.
• 부분 수열은 수열에서 순서를 유지한 채로 일부 원소를 선택해 만든 수열입니다.
• 이때 부분 수열의 수가 오름차순으로 정렬되어 있으면, 이를 증가하는 부분 수열이라고 합니다.
• 증가하는 부분 수열 중 가장 긴 수열을 최장 증가 부분 수열이라고 합니다. LIS (Longest Increasing Subsequence)라고도 하는데, 앞으로 편의상 LIS로 축약해 쓰겠습니다.

• e.g., 수열이 {10, 20, 10, 30, 20, 50}일 때
  • LIS는 {10, 20, 10, 30, 20, 50} -> {10, 20, 30, 50}, 길이는 4
• cf. LIS에는 동일한 수를 여러 번 포함할 수 없음
  • e.g., {2, 2, 3}은 LIS가 아닙니다.

O(N^2)로 푸는 방법

풀이 과정

• 수열의 값을 담은 배열을 A로 둘 때, 새로운 배열 memo를 정의합니다.
  • memo[i]에는 A[i]로 끝나는 LIS의 길이를 기록합니다.

e.g., A = [10, 20, 10, 30, 20, 50]일 때

i	0	1	2	3	4	5
A	10	20	10	30	20	50
memo

A[0] = 10

• A[0] (10)으로 끝나는 수열은 자기 자신인 {10}뿐입니다.
• 길이가 1이므로 memo[0] = 1.
• 실제 수열은 이해의 편의를 위해 작성했으며, 실제 알고리즘에선 저장되지 않습니다.

i	0	1	2	3	4	5
A	10	20	10	30	20	50
memo	1
실제 수열	{10}

A[1] = 20

• A[1] = 20보다 작은 값으로 끝나는 수열이 있다면, 뒤에 20을 덧붙일 수 있습니다.
• A[1] = 20은 A[0] = 10보다 크므로, memo[0]에 저장해 둔 1의 LIS에 20을 덧붙일 수 있습니다.
• 아, 그런데 길이도 계산해야 되죠? 20을 덧붙였으니 길이가 1 증가했겠네요. memo[1] = memo[0] + 1로 계산하면, memo[1] = 2.

i	0	1	2	3	4	5
A	10	20	10	30	20	50
memo	1	2
실제 수열	{10}	{10, 20}

A[2] = 10

• A[2] = 10은 A[0] = 10이나 A[1] = 20보다 크지 않으니까 앞서 구한 수열에 이어붙일 수 없습니다.
• 자기 자신인 {10} -> memo[2] = 1

i	0	1	2	3	4	5
A	10	20	10	30	20	50
memo	1	2	1
실제 수열	{10}	{10, 20}	{10}

A[3] = 30

• A[3] = 30은 A[0] = 10, A[1] = 20, A[2] = 10보다 큽니다.
• 가장 긴 수열을 만들기 위해선, memo[1]에 저장해 둔 길이 2의 LIS에 이어붙여야 합니다.
• memo[3] = memo[1] + 1로 계산하면, memo[3] = 3

i	0	1	2	3	4	5
A	10	20	10	30	20	50
memo	1	2	1	3
실제 수열	{10}	{10, 20}	{10}	{10, 20, 30}

A[4] = 20

• A[4] = 20은 A[0] = 10, A[2] = 10보다 큽니다.
• memo[0]와 memo[2] 에 저장해 둔 수열은 모두 길이가 1이므로, 어느쪽에 붙이든 문제없습니다.
• memo[4] = memo[2] + 1로 계산하면, memo[4] = 2

i	0	1	2	3	4	5
A	10	20	10	30	20	50
memo	1	2	1	3	2
실제 수열	{10}	{10, 20}	{10}	{10, 20, 30}	{10, 20}

A[5] = 50

• A[5] = 50은 A[0] ~ A[4] 모든 수보다 큽니다.
• 가장 긴 LIS를 만들기 위해선, memo[3]에 저장해 둔 길이 3의 수열에 이어붙여야 합니다.
• memo[5] = memo[3] + 1로 계산하면, memo[5] = 4

i	0	1	2	3	4	5
A	10	20	10	30	20	50
memo	1	2	1	3	2	4
실제 수열	{10}	{10, 20}	{10}	{10, 20, 30}	{10, 20}	{10, 20, 30, 50}

최종

• 최종적으로는 지금까지 구한 수열 길이들이 담긴 memo 리스트의 최댓값인 4가 정답이 됩니다.

풀이

정리하자면

• (1) A[i]로 끝나는 LIS의 길이를 구하기 위해
• (2) j = 0 ~ (i - 1)을 순회하면서 A[j] < A[i]을 만족하는 j에 대해, memo[j]의 최댓값을 찾는다.
• (3) memo[j]의 최댓값에 1을 더해 memo[i]에 저장한다.
  • 단 A[j] < A[i]인 j가 없으면, A[i] 하나만으로 LIS를 구성해야 하므로 1을 저장한다.

N = int(input())
A = list(map(int, input().split())) # 수열 A

# memo[i]: A[i]가 마지막 값인 LIS의 길이
memo = []

for i in range(N):
    # prev: A[i]보다 작은 값으로 끝나는 LIS 중
    # 가장 긴 LIS의 길이
    prev = 0
    for j in range(i):
        if A[j] < A[i]:
            prev = max(memo[j], prev)
    memo.append(prev + 1)

# memo list의 최댓값이 정답
print(max(memo))

시간 복잡도

• 총 $N$개의 값에 대해 $(O(N))$
  • 해당 값으로 끝나는 LIS 길이를 구할 때, A[0] ~ A[i-1]을 확인해야 하므로 $O(N)$ 소요
• 최종 $O(N^2)$.
• 11053번 문제는 $N \leq 1,000$이므로 $O(N^2)$의 시간 복잡도로 풀 수 있습니다

O(N log N)으로 푸는 방법

• 그런데 12015번 문제는 $N \leq 1,000,000$이므로 $O(N^2)$으론 시간 초과가 뜹니다!
• 앞선 문제에서는 memo[i]를 계산할 때 A[0] ~ A[i - 1]을 다 탐색합니다.
• 순차적으로 탐색하는 만큼 $O(N)$... 더 빠르게 탐색할 방법은 없을까요

풀이 과정

• tails라는 새로운 리스트를 정의하겠습니다
  • tails[k]에는 지금까지 만든 길이 k인 증가 부분수열의 끝값의 최솟값을 저장합니다.
  • 끝값을 저장하는 이유는, 그 뒤에 숫자를 붙일 수 있는지 확인하기 위해서입니다.
• 수열 A의 원소를 순서대로 확인하며, tails 리스트를 갱신하게 됩니다.
  • 갱신 과정에서 이진탐색을 쓰게 되는데... 이건 뒤에서 설명하죠.

• 예제: A = [10, 20, 5, 30, 10, 50]으로 두겠습니다.
  • 편의상 tails[0] = 0으로 두겠습니다.

A[0] = 10

• 길이 1의 수열 {10}을 만들 수 있습니다.
• 길이 1짜리 수열의 끝값을 10으로 저장합니다.
  • 실제로는 tails.append(10)을 해 주면 됩니다.

k	1
tails	10
실제 수열	{10}

• 실제 수열은 이해를 돕기 위해 적은 걸로, 실제 프로그램에선 저장되지 않습니다.

A[1] = 20

• 20은 tails[1] = 10보다 크므로, 기존 길이 1의 수열 {10}에 20을 붙여 {10, 20}으로 만들 수 있습니다.
• 길이 2짜리 수열의 끝값을 20으로 저장합니다.
  • 실제로는 tails.append(20)을 해 주면 됩니다.

k	1	2
tails	10	20
실제 수열	{10}	{10, 20}

A[2] = 5

• A[2] = 5은 tails[1] = 10보다 작으므로, 기존 수열 중 아무데에도 이어붙일 수 없습니다.
• 하지만 {5} 단독으로 길이 1의 수열를 만들 수 있습니다.
• 길이 1짜리 수열의 끝값을 10에서 5로 갱신합니다.
  • 실제로는 이진탐색으로 tails = [0, 10, 20] 중 5가 들어갈 자리인 i=1을 찾고, 해당 자리의 값을 5로 바꿉니다.

k	1	2
tails	5	20
실제 수열	{5}	{10, 20}

A[3] = 30

• A[3] = 30은 tails[2] = 20보다 크므로, 기존 길이 2의 수열에 이어붙일 수 있습니다.
• 길이 3짜리 수열의 끝값으로 30을 저장합니다.
  • 실제로는 tails.append(30)을 해 주면 됩니다.

k	1	2	3
tails	5	20	30
실제 수열	{5}	{10, 20}	{10, 20, 30}

A[4] = 10

• A[4] = 20은 tails[1] = 5보다 크고 tails[2] = 20보다 작으므로, 기존 길이 1의 수열에 이어붙일 수 있습니다.
• 길이 2짜리 수열의 끝값을 20에서 10으로, 갱신합니다.
  • 실제로는 이진탐색으로 tails = [0, 5, 20, 30] 중 10가 들어갈 자리인 i=2를 찾고, tails[2]를 10으로 바꿉니다.

k	1	2	3
tails	5	10	30
실제 수열	{5}	{5, 10}	{10, 20, 30}

A[5] = 50

• A[5] = 50은 tails[3] = 30보다 크므로, 기존 길이 3의 수열에 덧붙일 수 있습니다.
• 길이 4짜리 수열의 끝값으로 50을 저장합니다.
  • 실제로는 tails.append(50)을 해 주면 됩니다.

k	1	2	3	4
tails	5	20	30	50
실제 수열	{5}	{5, 10}	{10, 20, 30}	{10, 20, 30, 50}

최종

• 위와 같은 방식으로 구하면, 가장 긴 부분수열의 길이는 $4$가 됩니다.
  • 실제론 tails = [0, 5, 10, 20, 50]인데, len(tails) - 1인 4가 정답입니다.

풀이

정리하자면

• (1) i = 0 ~ (N - 1)을 순회하면서

• (2) tails[-1] < A[i]일 땐 (기존에 제일 긴 수열에 이어붙일 수 있을 때)

  • tails에 A[i]를 추가한다.

• (3) tails[-1] >= A[i]일 땐

  • 이분탐색으로 tails에 A[i]가 들어갈 수 잇는 인덱스 loc을 구하고
  • 해당 loc의 값을 A[i]로 갱신한다.

• (4) 부분수열의 최장길이는 len(tails) - 1로 계산한다.

• 본 풀이에선 파이썬의 이진탐색 라이브러리 bisect를 사용하겠습니다.

  • bisect.bisect_left(리스트, 값)는 정렬된 리스트에서 입력한 값을 가진 가장 왼쪽 원소의 인덱스를 반환합니다.
  • 만약 해당 값을 가진 원소가 없는 경우, 들어갈 수 있는 인덱스를 반환합니다.

import bisect

N = int(input())
A = list(map(int, input().split())) # 수열 A

# tails[i]: 길이가 i인 수열의 끝값
tails = [0]

for i in range(N):
    if tails[-1] < A[i]:
        tails.append(A[i])
    else:
        loc = bisect.bisect_left(tails, A[i])
        tails[loc] = A[i]

# 지금까지 만든 부분수열 중 최대 길이
print(len(tails) - 1)

시간 복잡도

• 총 $N$개의 값에 대해 $(O(N))$
  • tails 리스트에 대해 최대 $O(\log N)$번 이진 탐색을 수행
• 최종 $O(N\log N)$.
• 12015번 문제처럼 $N \leq 1,000,000$여도 풀 수 있습니다