최장 증가 부분 수열

어떤 문제를 푸는가

수열에서 순서를 유지하며 골라낸 증가하는 부분 수열 중 가장 긴 것의 길이를
구합니다. 예: [10, 9, 2, 5, 3, 7, 101, 18]의 LIS는 [2, 3, 7, 101]로 길이
4입니다. 부분 수열이므로 연속일 필요는 없고, 순서만 지키면 됩니다.

1단계 — \(O(N^2)\) DP

dp[i]를 "\(i\)번째 원소로 끝나는 가장 긴 증가 수열의 길이"로 둡니다.

$$ dp[i] = 1 + \max_{j < i,\ a[j] < a[i]} dp[j] $$

자기 앞의 모든 작은 원소를 보고, 그중 가장 긴 것에 자신을 이어 붙입니다.
답은 \(\max_i dp[i]\). 직관적이지만 \(O(N^2)\)이라 \(N\)이 수만을 넘으면 느립니다.

2단계 — \(O(N \log N)\) 풀이

핵심 발상: 길이가 \(\ell\)인 증가 수열들 중 마지막 원소가 가장 작은 값 을
tails[ℓ]에 저장합니다. 마지막 값이 작을수록 뒤에 더 많은 원소를 이을 수
있으니 유리합니다. 이 tails 배열은 항상 증가 상태를 유지합니다.

각 원소 \(x\)를 처리할 때:

1. tails에서 \(x\) 이상인 첫 위치 를 이분 탐색으로 찾는다.
2. 그 자리를 \(x\)로 교체한다. (그 자리가 끝이면 길이가 1 늘어남)

처리가 끝나면 tails의 길이가 곧 LIS의 길이입니다.

왜 옳은가

tails는 "각 길이별 최선의 끝값"을 유지합니다. \(x\)로 어떤 자리를 교체하면,
그 길이의 증가 수열을 더 작은 값으로 끝낼 수 있게 되어 미래의 선택지가 넓어
집니다. tails가 증가하므로 이분 탐색이 가능하고, 교체는 다른 자리의 불변식을
깨지 않습니다. 다만 tails 자체는 실제 LIS가 아닙니다 — 길이만 정확합니다.

복잡도

\(N \le 10^5\) 이상이면 \(O(N \log N)\)이 사실상 필수입니다.

엄격히 증가 vs 비감소

"같은 값 허용(비감소)"이면 lower_bound(같은 값 이상) 대신 upper_bound
(같은 값보다 큰 첫 위치)를 써 같은 값을 이어 붙입니다. 문제 조건을 정확히
읽어 둘을 구분하는 것이 핵심입니다. 다음 강의에서 구현과 경로 복원을 봅니다.

O(N log N) 구현 (C++)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; cin >> n;
    vector<int> a(n);
    for (auto& x : a) cin >> x;

    vector<int> tails;                 // tails[k] = 길이 k+1 수열의 최소 끝값
    for (int x : a) {
        auto it = lower_bound(tails.begin(), tails.end(), x);  // x 이상 첫 위치
        if (it == tails.end()) tails.push_back(x);  // 더 긴 수열 발견
        else *it = x;                               // 끝값을 더 작게 갱신
    }
    cout << tails.size() << '\n';      // 길이만 정확
}

lower_bound는 "엄격히 증가" LIS용입니다. 비감소(같은 값 허용)면
upper_bound로 바꿉니다.

파이썬 구현

import sys, bisect
input = sys.stdin.readline

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

tails = []
for x in a:
    i = bisect.bisect_left(tails, x)   # 엄격히 증가
    if i == len(tails):
        tails.append(x)
    else:
        tails[i] = x
print(len(tails))

비감소면 bisect_right를 씁니다.

실제 수열 복원

tails는 길이만 주므로, 실제 LIS 하나를 복원하려면 각 원소가 들어간
위치(길이 인덱스) 와 그 시점의 직전 원소 를 기록합니다.

vector<int> tails, idx;        // idx: tails 각 자리의 원소 인덱스
vector<int> pos(n), par(n, -1);
for (int i = 0; i < n; i++) {
    int p = lower_bound(tails.begin(), tails.end(), a[i]) - tails.begin();
    if (p == (int)tails.size()) { tails.push_back(a[i]); idx.push_back(i); }
    else { tails[p] = a[i]; idx[p] = i; }
    pos[i] = p;
    par[i] = (p > 0) ? idx[p - 1] : -1;   // 직전 길이의 끝 원소
}
// 가장 긴 수열의 끝에서 par를 따라 거꾸로 올라가 뒤집는다
int cur = idx.back();
vector<int> lis;
while (cur != -1) { lis.push_back(a[cur]); cur = par[cur]; }
reverse(lis.begin(), lis.end());

par는 "각 원소가 자리 \(p\)에 놓일 때, 자리 \(p-1\)의 현재 끝 원소"를 가리켜
실제 증가 수열을 이어 줍니다.

흔한 함정

• 엄격 vs 비감소 혼동 — lower_bound/upper_bound를 문제에 맞게.
  여기서 한 글자가 정답을 가릅니다.
• tails를 답으로 출력 — tails는 실제 수열이 아닙니다. 길이만 맞습니다.
• 최장 감소 수열(LDS) — 수열을 뒤집거나 부호를 바꿔 같은 코드로 처리.

응용 패턴

• 2차원 문제(상자 쌓기, 봉투 중첩) — 한 축으로 정렬한 뒤 다른 축에 LIS.
  같은 첫 축 값의 타이브레이크 방향에 주의(엄격성 충돌 방지).
• 두 수열의 LCS가 한쪽이 순열일 때 — 위치로 변환해 LIS로 가속.
• 가장 적은 비감소 수열로 분할 — 딜워스 정리로 LIS/LDS와 연결.

\(O(N^2)\) DP로 직관을 잡고, tails + 이분 탐색으로 \(O(N \log N)\)까지
끌어올리는 흐름이 이 단원의 정수입니다.

출제 신호

• "증가하는 부분 수열의 최대 길이" — 직접 출제형. \(N \le 1000\)이면
  \(O(N^2)\) DP도 통과하지만, \(N \ge 10^5\)이면 \(O(N \log N)\) 강제입니다.
  제약이 곧 어느 구현을 요구하는지 알려 줍니다.
• 변장 출제가 더 많습니다 — "전깃줄/케이블이 교차하지 않게 최대 몇 개",
  "상자를 최대 몇 개 포개기", "두 순열의 LCS"(번호 재매김 후 LIS),
  "수열을 몇 개의 비증가 묶음으로 덮는가"(답이 LIS 길이와 같음 — 딜워스 정리)
• "감소 수열", "증가했다 감소(바이토닉)"도 같은 도구의 방향/양쪽 변형입니다.

풀이 결정 절차

1. \(N\)을 보고 \(O(N^2)\) vs \(O(N \log N)\)을 결정합니다.
2. strict(순증가)인가, 같아도 되는가(비감소) — 문제 문장에서 확정합니다.
   이 한 글자가 이분 탐색 함수 선택을 바꿉니다.
3. 길이만 필요한가, 실제 수열 복원이 필요한가 — 복원이 필요하면 각
   원소가 들어간 위치와 직전 원소 인덱스를 따로 기록해야 합니다.
4. 변장 문제라면 "무엇을 정렬하고 무엇으로 LIS를 잡는지"를 먼저 적습니다
   (예: 전깃줄 — 한쪽 끝 기준 정렬 후 반대쪽 끝 수열의 LIS).

자주 하는 실수

가장 깊은 오해는 tails 배열을 LIS 그 자체로 착각하는 것입니다.
tails[k] = "길이 \(k+1\)인 증가 부분 수열들의 끝값 중 최솟값"일 뿐,
배열을 그대로 출력하면 실제 LIS가 아닌 경우가 많습니다. 길이는 맞지만
내용은 아닙니다.

import bisect

tails = []
pos = []                                  # 복원용: 각 원소가 놓인 길이 인덱스
for x in a:
    i = bisect.bisect_left(tails, x)      # 순증가: bisect_left
    if i == len(tails):
        tails.append(x)
    else:
        tails[i] = x
    pos.append(i)
print(len(tails))                         # 길이는 tails 의 길이

여기서 bisect_left(C++ lower_bound)의 의미는 "\(x\) 이상이 처음 나오는
자리" — 즉 \(x\)가 이을 수 있는 가장 긴 수열 바로 다음 자리를 찾아 끝값을 더
작게 교체하는 것입니다.

• strict/비감소에서 함수 혼동 — 순증가는 bisect_left/lower_bound,
  같은 값 허용(비감소)은 bisect_right/upper_bound입니다. 거꾸로 쓰면
  같은 값이 이어 붙거나(strict 위반) 끊깁니다. 테스트: [3, 3, 3]의 답이
  strict면 1, 비감소면 3이어야 합니다.
• 복원을 tails에서 시도 — 복원은 pos 배열을 뒤에서부터 훑으며
  길이 인덱스가 \(L-1, L-2, \dots, 0\)으로 줄어드는 원소를 차례로 줍습니다.
• \(O(N^2)\) DP에서 초기값 — dp[i] = 1(자기 자신)을 0으로 두는 실수.
• 감소 수열 변형 — 배열을 뒤집거나 부호를 뒤집어 LIS로 환원하는 게
  새 코드를 짜는 것보다 안전합니다.

연습 방법

사이드바 연습 목록에서 \(O(N^2)\)로도 되는 기본 문제 → \(N \ge 10^5\) 강제
문제 → 복원 요구 문제 → 전깃줄/상자류 변장 문제 순서를 권합니다. 특히
복원 문제를 한 번 직접 짜 보면 tails의 의미("각 길이의 최선의 끝값")가
완전히 잡힙니다. 태그된 문제 3문제 이상 해결 시 마스터 처리되어 레이팅
CLASS 보너스에 반영됩니다.