[알고리즘 Deep Dive #4] LIS(가장 긴 증가하는 부분 수열): O(N²)에서 O(N log N)으로

들어가며

LIS(Longest Increasing Subsequence, 가장 긴 증가하는 부분 수열)는 알고리즘에서 매우 유명한 문제다.
특히 동적 프로그래밍(DP)을 공부할 때 거의 반드시 등장하는 대표적인 예제이기도 하다.

문제 자체는 단순하다.

수열이 주어졌을 때 증가하는 부분 수열 중 가장 긴 것의 길이를 구하라.

하지만 이 문제는 입력 크기에 따라 완전히 다른 접근 방법이 필요하다.

방법	시간복잡도
DP	O(N²)
이분탐색 + Greedy	O(N log N)

N이 작다면 O(N²) DP로 충분하지만,
N이 수십만 ~ 백만 수준으로 커지면 이분탐색 기반 풀이가 필요하다.

이 글에서는 다음 내용을 순서대로 정리한다.

1. O(N²) DP 풀이
2. O(N log N) 이분탐색 풀이
3. 왜 이분탐색 풀이가 동작하는지

---

문제 정의

수열 A가 주어졌을 때 가장 긴 증가하는 부분 수열(LIS)의 길이를 구하라.

여기서 부분 수열(subsequence)은 원래 수열에서 일부 원소를 선택한 것이다.
단, 원소의 순서는 유지해야 한다.

예를 들어 다음 수열을 보자.

A = {10, 20, 10, 30, 20, 50}

가능한 증가 부분 수열 중 하나는 다음과 같다.

{10, 20, 30, 50}

따라서 LIS의 길이는

4

이다.

---

O(N²) DP 풀이

LIS를 가장 직관적으로 푸는 방법은 동적 프로그래밍(DP)이다.

이 방식은 입력 크기가 크지 않을 때 사용되는 전형적인 LIS 풀이이다.

대표적인 예제가 바로
백준 11053번: 가장 긴 증가하는 부분 수열 이다.

이 문제의 입력 크기는 비교적 작기 때문에
O(N²) DP로도 충분히 해결할 수 있다.

핵심 아이디어는 다음과 같다.

각 위치에서 끝나는 증가 부분 수열의 길이를 구해보자.

즉 수열의 각 원소를 마지막 원소로 사용하는 LIS를 생각하는 것이다.

---

DP 정의

다음과 같이 정의한다.

dp[i] = arr[i]를 마지막 원소로 하는 LIS의 길이

즉 dp[i]는

i번째 원소에서 끝나는 증가 부분 수열의 최대 길이

를 의미한다.

예를 들어 다음 수열을 보자.

arr = {10, 20, 10, 30}

이때

• dp[0] → {10} → 길이 1
• dp[1] → {10, 20} → 길이 2
• dp[2] → {10} → 길이 1
• dp[3] → {10, 20, 30} → 길이 3

이렇게 각 위치에서 끝나는 LIS 길이를 저장한다.

---

점화식

이제 dp[i]를 어떻게 계산할지 생각해 보자.

arr[i] 앞에 있는 원소들을 확인한다.

j < i

그리고 증가 수열이 되려면 다음 조건이 필요하다.

arr[j] < arr[i]

즉 arr[j] 뒤에 arr[i]를 붙일 수 있어야 한다.

그러면 수열 길이는

dp[j] + 1

이 된다.

이 중 가장 긴 것을 선택하면 된다.

dp[i] = max(dp[j] + 1)   (j < i, arr[j] < arr[i])

---

구현

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))

# 자기 자신만으로 이루어진 수열 길이 = 1
dp = [1] * n

for i in range(1, n):
    for j in range(i):
        if arr[j] < arr[i]:
            dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))

---

동작 예시

arr = {10, 20, 10, 30, 20, 50}

DP 진행 과정

i=0 → dp = [1, 1, 1, 1, 1, 1]

i=1
10 < 20
dp[1] = 2

i=2
10 = 10 → 증가 조건 불만족

dp = [1, 2, 1, 1, 1, 1]

i=3
10 < 30
20 < 30
10 < 30

dp[3] = 3

i=4
10 < 20
10 < 20

dp[4] = 2

i=5
모든 원소 < 50

dp[5] = 4

최종 결과

dp = [1, 2, 1, 3, 2, 4]

따라서 LIS 길이는

max(dp) = 4

이다.

---

LIS 수열 출력 문제 (BOJ 14002)

백준 14002 - 가장 긴 증가하는 부분 수열 4 문제에서는
LIS의 길이뿐만 아니라 실제 수열도 출력해야 한다.

이를 위해서는 단순히 dp 배열만 사용하는 것이 아니라
이전 원소의 위치를 저장하는 배열이 하나 더 필요하다.

dp[i]   = i번째 원소를 마지막으로 하는 LIS 길이
prev[i] = 해당 LIS에서 i 이전 원소의 인덱스

DP를 계산하면서 더 긴 수열이 발견될 때 이전 위치를 기록하면
마지막에 역추적(backtracking) 으로 실제 LIS를 복원할 수 있다.

---

구현

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))

dp = [1] * n
prev = [-1] * n

for i in range(n):
    for j in range(i):
        if arr[j] < arr[i] and dp[j] + 1 > dp[i]:
            dp[i] = dp[j] + 1
            prev[i] = j

# LIS 끝 위치 찾기
max_len = max(dp)
idx = dp.index(max_len)

# 역추적
lis = []
while idx != -1:
    lis.append(arr[idx])
    idx = prev[idx]

lis.reverse()

print(max_len)
print(*lis)

---

동작 원리

예를 들어

arr = {10, 20, 10, 30, 20, 50}

DP 계산 결과

dp = [1, 2, 1, 3, 2, 4]

가장 큰 값은

4

이고 해당 위치는

index = 5

이다.

이때 prev 배열을 따라가면

50 ← 30 ← 20 ← 10

이렇게 역순으로 추적된다.

뒤집으면

10 20 30 50

즉 실제 LIS 수열을 얻을 수 있다.

---

한계

이 방법의 시간복잡도는

O(N²)

예를 들어

N = 1,000,000

이라면 연산 수는

10¹²

수준이 된다.

즉 실전 문제에서는 시간 초과가 발생한다.

그래서 LIS에는 이분탐색을 이용한 O(N log N) 풀이가 존재한다.

---

O(N log N) 이분탐색 풀이

입력 크기가 매우 큰 경우에는 DP로 해결할 수 없다.

대표적인 예제가
백준 12015번: 가장 긴 증가하는 부분 수열 2 이다. 이 12015번 문제의 입력 크기는 최대 N = 1,000,000 이다.

따라서 O(N²) DP로는 시간 초과가 발생하며
O(N log N) 이분탐색 기반 LIS 알고리즘이 필요하다.

핵심 아이디어

이 알고리즘의 핵심 아이디어는 다음과 같다.

길이별로 “가능한 가장 작은 끝값”을 유지하는 것이다.

생각을 조금 바꿔 보자.
우리는 실제 LIS 수열을 직접 저장하려는 것이 아니라,

길이 1인 증가 수열
길이 2인 증가 수열
길이 3인 증가 수열
...

각 길이에 대해 “끝값이 가장 작은 수열”만 유지한다.

왜냐하면 끝값이 작을수록 이후 원소가 이어질 가능성이 더 커지기 때문이다.

예를 들어 다음 두 수열을 보자.

[10, 20, 30]
[10, 15, 30]

두 수열의 길이는 같지만

[10, 15, 30]

이 더 유리하다. 왜냐하면 이후에 들어올 숫자가

16, 17, 18 ...

같은 값이라면 연결 가능성이 더 커지기 때문이다.

그래서 우리는 실제 수열이 아니라

“각 길이에서 가능한 가장 작은 끝값”

만을 관리한다.

이 끝값들을 저장하는 배열이 바로 tails이다.

tails[i] =
길이 i+1인 증가 부분 수열의
마지막 원소 중 최솟값

예를 들어

tails = [10, 20, 30]

이라면 의미는 다음과 같다.

길이 1 수열의 최소 끝값 → 10
길이 2 수열의 최소 끝값 → 20
길이 3 수열의 최소 끝값 → 30

각 길이에 대해 “끝값이 가장 작은 수열”만 유지한다.

---

Patience Sorting으로 보는 LIS

LIS의 O(N log N) 알고리즘은 Patience Sorting(카드 더미 정렬) 모델로 직관적으로 이해할 수 있다.

각 숫자를 카드라고 생각하고 다음 규칙으로 더미를 만든다.

1. 카드를 왼쪽부터 하나씩 본다.
2. 현재 카드 x 이상인 가장 왼쪽 더미 위에 놓는다.
3. 그런 더미가 없으면 새 더미를 만든다.

예를 들어 다음 수열을 보자.

3, 7, 5, 6, 4, 2, 10, 9, 8

Patience Sorting 규칙에 따라 카드를 쌓으면 다음과 같은 더미들이 만들어진다.

[3, 2]
[7, 5, 4]
[6]
[10, 9, 8]

여기서 중요한 사실은

더미의 개수 = LIS 길이

이다.

또한 각 더미의 맨 위 카드(top) 값들은 항상 정렬된 상태가 된다.

2, 4, 6, 8

이 값들이 바로 LIS 알고리즘에서 사용하는

tails 배열

과 같은 역할을 한다.

즉 이분탐색 LIS 알고리즘은

Patience Sorting을 배열로 최적화한 것

이라고 볼 수 있다.

---

출처

• Wikipedia – Patience Sorting
  https://en.wikipedia.org/wiki/Patience_sorting

---

규칙

새로운 원소 x를 처리할 때 다음 규칙을 따른다.

1️⃣ x가 tails 마지막 값보다 큰 경우

x > tails[-1]

tails.append(x)

---

2️⃣ 그렇지 않은 경우

tails에서 lower bound를 찾는다.

tails[pos] ≥ x

그리고 교체한다.

tails[pos] = x

---

동작 예시

arr = [10, 20, 30, 15, 25, 50]

| 원소 | 동작 | tails | 비고 | |—|—|—|—| | 10 | 추가 | [10] | | | 20 | 추가 | [10, 20] | | | 30 | 추가 | [10, 20, 30] | | | 15 | lower bound = 1, 20 → 15 교체 | [10, 15, 30] | 더 작은 값으로 갱신 | | 25 | lower bound = 2, 30 → 25 교체 | [10, 15, 25] | 더 작은 값으로 갱신 | | 50 | 추가 | [10, 15, 25, 50] | |

len(tails) = 4

15가 들어왔을 때 20을 15로 교체했기 때문에,
이후에 25가 들어왔을 때 연결될 수 있었다.
만약 교체하지 않았다면 tails = [10, 20, 30, ...] 상태에서
25는 30을 교체하지 못하고 [10, 20, 25]가 되어 같은 결과지만,
더 극단적인 예시로 16이 들어온다면:

교체 O → tails = [10, 15, 25] → 16 연결 가능 ✅
교체 X → tails = [10, 20, 25] → 16 연결 불가 ❌

---

구현

import sys
from bisect import bisect_left
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))

tails = []

for x in arr:
    pos = bisect_left(tails, x) # lower bound 위치 찾기

    if pos == len(tails):
        tails.append(x)  # x가 tails의 맨 뒤 원소보다 크면 추가
    else:
        tails[pos] = x  # 아니면 교체

print(len(tails))

bisect_left(tails, x) : 정렬된 배열 tails에서 x 이상인 값 중 가장 왼쪽 인덱스를 반환한다. Python 표준 라이브러리로, 내부적으로 이분탐색을 수행한다.

lower bound를 직접 구현하면 이렇다.

def lower_bound(arr, x):
    lo, hi = 0, len(arr)

    while lo < hi:
        mid = (lo + hi) // 2

        if arr[mid] < x:
            lo = mid + 1
        else:
            hi = mid

    return lo

---

왜 교체해도 길이가 맞을까?

교체의 목적

tails의 각 자리는 “해당 길이로 끝날 수 있는 최솟값” 을 유지한다.

tails[i] = 길이 i+1인 증가 수열의 끝값 중 최솟값

끝값이 작을수록 이후 원소가 이어질 가능성이 높아진다.

tails = [2, 5, 7]  →  길이3 수열의 끝값 = 7
4가 등장하면
tails = [2, 4, 7]  →  길이2 수열의 끝값이 5에서 4로 갱신

이후 5, 6이 들어오면:
교체 O → [2, 4, 5] → [2, 4, 5, 6]  len = 4 ✅
교체 X → [2, 5, 7] → [2, 5, 6]     len = 3 ❌

---

왜 길이는 절대 틀리지 않는가

길이가 늘어나는 경우는 딱 하나다.

x > tails[-1]   →   tails.append(x)

x가 기존 가장 긴 수열 뒤에 실제로 붙을 수 있을 때만 길이가 늘어난다.
반대로 교체는 기존 길이를 개선할 뿐, 새로운 길이를 만들지 않는다.

동작	의미
append	더 긴 증가 수열 발견 → LIS 길이 +1
replace	같은 길이 수열을 더 좋은 끝값으로 개선

따라서 len(tails)는 항상 지금까지 발견된 LIS 길이와 정확히 같다.

---

tails는 실제 LIS가 아니다

교체는 tails를 가능한 여러 LIS 중 가장 느리게 증가하는 수열로 유지한다.

arr = [10, 20, 30, 15]

[10] → [10, 20] → [10, 20, 30] → [10, 15, 30]

{10, 15, 30}은 원래 배열에서 인덱스 순서를 유지하며 뽑을 수 없다.
(15는 인덱스 3, 30은 인덱스 2 → 순서 위반)

실제 LIS:  {10, 20, 30}  인덱스 0 → 1 → 2  ✅
tails:     {10, 15, 30}  인덱스 0 → 3 → 2  ❌

결과 배열(tails)은 실제 LIS와 내용은 다르지만 길이는 동일하다. 교체의 목적은 “더 작은 값으로 끝나는 수열을 유지해서, 이후 원소가 이어질 가능성을 높이는 것” 이다.
내용물이 아니라 길이만 구하는 문제에서는 이 방식이 항상 정확하다.

실제 LIS 수열을 출력해야 하는 문제라면 parent 배열로 별도 추적이 필요하다.

---

실제 LIS 수열을 구하는 문제

지금까지 설명한 O(N log N) 알고리즘은
LIS의 길이(length)만 구하는 알고리즘이다.

하지만 어떤 문제는 LIS 자체를 출력해야 한다.

대표적인 예제가
백준 14003번: 가장 긴 증가하는 부분 수열 3 이다.
(무려 플레티넘 문제이다.)

이 문제에서는 단순히 tails 배열만 유지하는 것으로는 부족하다.
tails는 각 길이의 최소 끝값만 저장할 뿐, 실제 수열의 연결 관계는 저장하지 않기 때문이다.

따라서 실제 LIS를 복원하려면 추적 정보를 추가로 저장해야 한다.

보통 다음 두 가지 배열을 사용한다.

배열	역할
pos	각 원소가 LIS에서 몇 번째 위치에 들어갔는지
parent	해당 원소 이전에 오는 LIS 원소의 인덱스

이 정보를 이용하면 마지막 원소부터 역추적(backtracking) 하여 실제 LIS 수열을 복원할 수 있다.

---

LIS 수열 복원 알고리즘

알고리즘은 크게 세 단계로 구성된다.

1️⃣ LIS 길이 계산

기존과 동일하게 tails 배열을 유지한다.

단, 이때 각 원소가 들어간 위치를 기록한다.

pos[i] = arr[i]가 LIS에서 차지하는 위치

---

2️⃣ 이전 원소 추적

각 원소가 LIS에 들어갈 때

parent[i] = 이전 LIS 원소의 인덱스

를 기록한다.

예를 들어

10 20 30 15 25

에서 LIS가

10 → 15 → 25

라면

parent[15] = 10
parent[25] = 15

같은 방식으로 연결 정보가 저장된다.

---

3️⃣ 역추적(backtracking)

LIS의 마지막 원소부터 parent를 따라가면

25 → 15 → 10

처럼 역순으로 나오고, 이를 뒤집으면 실제 LIS가 된다.

---

구현 (Python)

from bisect import bisect_left

n = int(input())
arr = list(map(int, input().split()))

tails = []
tails_idx = []   # tails 각 위치에 있는 원소의 원래 인덱스 (중복된 값이 있을 수도 있으니까.)
parent = [-1] * n  # parent[i] = arr[i]의 이전 원소 인덱스

for i, x in enumerate(arr):
    pos = bisect_left(tails, x)

    if pos == len(tails): 
        tails.append(x) # 현재 원소가 tails의 모든 원소보다 크면, tails의 맨 뒤에 추가
        tails_idx.append(i) # 현재 원소의 인덱스 추가
    else: 
        tails[pos] = x # 현재 원소가 tails의 어떤 원소보다 작거나 같으면, 해당 위치의 원소를 현재 원소로 교체
        tails_idx[pos] = i # 현재 원소의 인덱스로 교체

    # 이전 원소 기록 (pos > 0이면 바로 앞 위치의 원소가 predecessor)
    if pos > 0:
        parent[i] = tails_idx[pos - 1]

# 마지막 원소부터 역추적
path = []
cur = tails_idx[-1]
while cur != -1:
    path.append(arr[cur])
    cur = parent[cur]

path.reverse()

print(len(tails))
print(*path)

시간복잡도는 여전히

O(N log N)

이다.

---

예시 추적

arr = [2, 3, 1, 4]

i=0, x=2: tails=[2],     tails_idx=[0],   parent[0]=-1
i=1, x=3: tails=[2,3],   tails_idx=[0,1], parent[1]=0   (2←3)
i=2, x=1: tails=[1,3],   tails_idx=[2,1], parent[2]=-1  (2→1 교체)
i=3, x=4: tails=[1,3,4], tails_idx=[2,1,3], parent[3]=1 (3←4)

tails의 인덱스 순서를 보면:

tails     = [1, 3, 4]
tails_idx = [2, 1, 3]  ←  인덱스 2→1, 순서 위반 ❌

tails 자체는 실제 배열에서 뽑을 수 없는 수열이다.
하지만 parent를 따라 역추적하면:

역추적: 3 → 1 → 0
경로:   arr[0]=2, arr[1]=3, arr[3]=4
출력:   2 3 4  ✅  (인덱스 0→1→3, 순서 OK)

tails [1, 3, 4]와 실제 경로 [2, 3, 4]가 다르다.
tails는 길이만 정확하고, 실제 경로는 parent 역추적으로만 구할 수 있다.

---

마무리

두 풀이 비교

	O(N²) DP	O(N log N)
시간복잡도	O(N²)	O(N log N)
공간복잡도	O(N)	O(N)
구현 난이도	쉬움	중간
실제 LIS 출력	가능	추가 추적 필요

---

N 크기별 풀이 선택

실전에서는 입력 크기(N) 를 보고 알고리즘을 선택해야 한다.

N ≤ 5,000      → O(N²) DP 가능
N ≤ 1,000,000  → O(N log N) 필요

대표적인 LIS 문제:

문제	특징	풀이
백준 11053	기본 LIS 길이 구하기	O(N²) DP
백준 12015	대형 입력에서 LIS 길이 구하기	O(N log N)
백준 14002	LIS 길이 + 실제 수열 출력	O(N²) DP + 역추적
백준 14003	대형 입력 + LIS 수열 출력	추적 + O(N log N)

정리

LIS 문제의 핵심 아이디어는 다음 두 가지다.

1. tails[i]
   → 길이 i+1 증가 수열의 가능한 최소 끝값 유지

2. lower_bound 교체
   → 더 작은 끝값으로 갱신해 미래 확장 가능성을 확보

이 아이디어는 다음 문제에도 그대로 확장된다.

LDS  (Longest Decreasing Subsequence)
LNDS (Longest Non-Decreasing Subsequence)
Bitonic Sequence

---

Tags: #알고리즘 #LIS #최장증가부분수열 #이분탐색 #BinarySearch #LowerBound #Python #Algorithm #백준 #코딩테스트