가을의 개발 일지

코딩테스트/백준

[백준/Python3] 12015번. 가장 긴 증가하는 부분 수열 2 - 가장 쉬운 원리 이해

가을고양이 2026. 2. 13. 06:03

문제

https://www.acmicpc.net/problem/12015

 

자야 하는데, 이미 알고리즘 문제 풀이로 도파민이 돌아버려서 잠이 안 왔다.

마침 가장 긴 증가하는 부분 수열(Longest Incresing Subsequence, 이하 LIS) 문제를 푼 김에, 호기롭게 플래티넘 문제를 구경하러 갔다.

 

그리고 n이 1,000,000인 거보고 아, 이건 DP로 안 풀린다. ($O(N^2)$라서)라는 걸 직감하고, $O(n \log n)$으로 풀 방법을 구글링했었다.

 

그러나 설명이 좀 아쉬운 부분들이 많아, 나도 정리할 겸, 다른 사람들에게도 도움될 겸 이렇게 글을 작성한다.

풀이

학습 과정

 $O(n \log n)$로 푸는 열쇠는 이분 탐색이다.

하지만, 많은 사람들이 왜 이 문제가 이분 탐색인가를 시원하게 말해주진 못했다.

 

어떻게 이 문제를 보고, 이분 탐색을 적용해야지! 라고 생각할 수 있을까?

 

 

결론부터 말하자면, LIS 유형을 전혀 풀어보지 않은 사람이 이분 탐색부터 떠올리는 건 불가능한 일이다. 그게 내 결론이다.

 

그도 그럴 것이, 사실 이 알고리즘은 이분 탐색보단 그리디가 핵심이기 때문이다. DP로 시간초과가 나서, 그리디한 방법을 떠올리고, 해당 알고리즘을 구현한 후에, 최적화를 위해 이진 탐색을 적용한 느낌이다. 그러니, 먼저 그리디라고 생각하고 흐름을 따라가보자.

 

우린 지금껏 LIS 문제를 DP로 풀었다. 왜일까? 현재까지의 최선이 미래에도 최선이 아니기 때문이다.

 

내가 [10, 11, 12, 3, 4]까지 배열을 보고, [10, 11, 12]를 가장 긴 증가하는 부분 수열로 잡았었는데, 갑자기 뒤에 5, 6이 붙어서 [3, 4, 5, 6]이 답이 된다면? 그런 가능성을 배제할 수 없었기에, 우린 모든 경우의 수를 주시하고 있는 DP를 선택했다.

 

그랬더니, 이번엔 모든 경우의 수를 신경 쓰는 바람에 시간 초과가 난다. 웃기지 않은가. 그리디를 쓰지 못해 DP를 선택했는데, DP로 시간 초과가 나서 다시 그리디로 회귀한다는 게.

 

여기서, 과거 누군가가 기막힌 아이디어를 하나 냈었나보다. 주어진 i까지 구한 수많은 LIS들 중에, 마지막 숫자가 가장 작은 LIS만 들고 가자고. 모든 경우의 수를 고려해서 시간 초과가 났으니, 버릴 수 있는 경우의 수는 버리고 가자고.

 

예를 들어, 길이가 3인 LIS를 여럿 찾았는데, 각각 [1, 2, 12], [3, 4, 5], [2, 3, 9]라고 해보자.

 

이 뒤에 13이 온다면, 모든 LIS의 길이가 4로 증가한다.

하지만, 이 뒤에 6이 온다면, 오직 [3, 4, 5]만이 길이가 늘어난다. [3, 4, 5, 6]은 LIS지만, [1, 2, 12, 6]과 [2, 3, 9, 6]은 아니니까.

그렇기에, 우리는 오직 1개의 LIS만 들고 간다.

 

그럼, 누군가 질문할 수 있다. 만약 그 [3, 4, 5]마저 나중에 버려진다면 어떻게 하는가?

수열이 [3, 1, 4, 2, 5, 3, 4]처럼 이어져서, 우리가 5번째 수까지 볼 땐 [3, 4, 5]가 최소였는데, 정답이 [1, 2, 3, 4]고, [3, 4, 5]를 쓰지 않게 되면, 우리는 틀리는 게 아닌가?

 

그 말이 맞다. 그래서, 약간의 DP를 사용한다. 여기까지 흐름을 따라왔다면, 우리가 단 하나의 수열만 갖고 있을 거라 생각할 텐데, 아니다. 사실 우리가 가져가는 건, 길이가 N일 때, 마지막 원소가 최소인 부분 수열들을 가져간다.

(앞으로, 마지막 원소가 최소인 부분 수열을 최소 종료 수열이라 명하겠다.)

 

즉, 실제로 우리가 짤 코드에선, 길이가 1일 때 최소 종료 수열, 길이가 2일 때 최소 종료 수열, 길이가 3일 때 최소 종료 수열을 모두 저장한다. 그리고, 만약 길이가 동등한 새로운 LIS가 발견되었을 때, 마지막 원소의 크기를 비교하고, 갱신한다.

 

말로만 보면 어렵다. 간단히, 아까 전의 예시로 이어가보자.

[3, 1, 4, 2, 5, 3, 4]에서, 메모이제이션과, 아까 만든 그리디한 규칙을 적용해보자. 맨 앞에서부터 수열을 한 칸씩 늘려가며, 아래처럼 진행한다.

 

먼저 [3]의 경우, LIS의 길이는 1이다. 따라서, 아래와 같이 저장한다.

# DP[부분 수열의 길이] = 해당 수열의 마지막 원소
DP[1] = 3

 

이제 [3, 1]로 가보자. 부분 수열의 길이가 2가 될 수 있는지부터 살펴봐야 한다.

아쉽게도, 1은 우리가 발견한 길이 1짜리 수열의 마지막 원소, 쉽게 말해 3보다 작다. 따라서, 길이가 2인 LIS는 존재하지 않는다.

하지만, 1은 3보다 작기에, 새로운 길이가 1인 수열이 될 수 있으니, 값을 갱신한다.

DP[1] = 1

 

다시 전진해보자. 이제 [3, 1, 4]다.

4는 1보다 큰가? 그렇다. 이제, 우리가 찾았던 LIS의 길이가 늘어났다.

DP[1] = 1
DP[2] = 4

 

이렇게, DP배열은 [1, 4]가 저장됐다. 다시 움직여보자.

 

[3, 1, 4, 2]까지 왔다. 2는 1보단 크지만, 4보단 작다. 4보다 작기에 수열의 길이를 늘릴 수는 없지만, 1보단 크기에 값을 갱신할 순 있다.

DP[1] = 1
DP[2] = 2

 

여기서, 눈치가 빠른 사람이라면 떠올릴 수 있는 로직이 있다. 수열이 한 칸 늘어나면, 우리는 해당 칸의 숫자를 받게 된다. 그리고, 그 숫자가 들어갈 수 있는 위치를 찾고 있다.

 

[1, 4]에서, 방금은 2가 들어왔고, 1 < 2 < 4인 상황이었다. 만약 0이 들어왔다면 어땠을까? 0 < 1 < 4, 0은 맨 앞에 오게 된다. 그렇다면 맨 앞의 수열이 변경되었을 것이다. (그러나, [0, 1]이 되진 않는다. 실제 수열은 [3, 1, 4, 0]일 테니.)

 

오름차순으로 정렬된 배열에서, 어떤 수가 주어졌을 때, 해당 수가 들어가야 할 위치를 구한다. 이때 가장 빠르게 탐색하는 로직이 바로 이분 탐색이다. 그래서, 이 문제가 이분 탐색 문제로 불리는 것이다.

이분 탐색은 가니쉬고, 메인 디시는 그리디, 혹은 DP다.

 

그럼, 이 로직을 이제 아래처럼 정리할 수 있다.

수열의 첫번째 칸부터 N번째 칸까지, 숫자를 하나씩 들여다본다.
DP 배열에서, 해당 숫자가 들어갈 수 있는 칸을 찾는다.
만약, 배열의 끝에 들어간다면(LIS보다 큰 값이라면), 새로운 값으로 추가하며 길이가 늘어난다.
그렇지 않다면, 기존 DP 배열에 저장된 값과 비교한 뒤, 작다면 교체한다.

 

이 단순한 로직만 지켜나간다면, 길이가 얼마나 길어지든, $O(n \log n)$으로 풀어낼 수 있다.

(전체 길이 $N$ $\times$ 이분 탐색 $\log n$)

 

이제 로직이 감이 잡혔는가? 이제 바로 코드로 살펴보자.

 

코드

# 파이썬은 이분 탐색을 지원해준다.
import bisect

# 입력 및 초기값 설정
n = int(input())
nums = list(map(int, input().split()))

# dp[i] = 길이가 i인 증가하는 부분 수열의 마지막 원소
dp = [nums[0]]

# 앞에서부터 하나씩 꺼내본다. i를 쓴다면 첫번째 탐색은 건너뛸 수 있다.
for num in nums:
    # 배열의 맨 끝보다 큰 경우 (기존 LIS 뒤에 붙는 경우)
    if num > dp[-1]:
        dp.append(num)
    # 이분 탐색 결과이므로, num은 항상 dp[pos]보다 작다.
    else:
        dp[bisect.bisect_left(dp, num)] = num

# dp가 곧 가장 긴 증가하는 부분 수열이 되었다.
print(len(dp))

 

코드는 참 어이없을 정도로 단순하다. 하지만, 이 알고리즘을 생각해내는 건, 절대 쉽지 않았으리라.

이게 왜 이분 탐색이냐 트러플 향 첨가도 아니고

 

결과

 

N이 커진 만큼, PyPy3가 더 빠르다.

 

애초에 다양한 분들의 블로그로 학습한 만큼, 맞힌 사람들의 코드를 봐도 거의 비슷했다. 그래서 오늘은 추가 개선은 없다.

아 맞다 비공개로 돌렸어야 했는데

강평

알고리즘 분류도 이분 탐색이고 대부분이 이분 탐색으로 소개하던데, 이분 탐색은 어디까지나 탐색하는 방법이 아닌가. "이분 탐색 문제니까 이분 탐색을 써야지!"보단, "DP에서 쓸모없는 경우의 수는 배제해야지!"로 시작해야, 이 알고리즘을 찾아낼 수 있을 것 같다. 이분 탐색은 거들 뿐

 

이 방법을 응용해서, 단순 LIS 출력을 넘어 어디 인덱스에서 가져왔는지도 저장하는 분이 있던데, 이 역시 필요하다면 쉽게 추가할 수 있을 것이다.

 

내가 읽고, 이해하고, 재해석한 내용을 바탕으로 쓴 포스팅인데, 결국 이는 내가 가장 쉽게 이해한 방법이다. 혹여나 DP 문제를 풀다 여기까지 흘러들어온 분이 계시다면, 그분의 이해에도 조금이나마 도움이 되었다면 좋겠다.

참고 자료

 

 

'코딩테스트 > 백준' 카테고리의 다른 글

[백준/Python3] 25419번. 정수를 끝까지 외치자  (0) 2026.02.11
[백준/Python3] 14238번. 출근 기록  (0) 2026.02.08
[백준/Python3] 1105번. 팔  (0) 2026.02.06
[백준/Python3] 1024번. 수열의 합  (0) 2026.02.02
[백준/Python3] 1018번. 체스판 다시 칠하기  (0) 2026.01.31

'코딩테스트/백준'의 다른글

  • 현재글[백준/Python3] 12015번. 가장 긴 증가하는 부분 수열 2 - 가장 쉬운 원리 이해

관련글

티스토리툴바