백준 12015번: 가장 긴 증가하는 부분 수열 [python]

난이도 : 골드 2
유형 : 이분 탐색
https://www.acmicpc.net/problem/12015

---

문제 접근

언젠가 풀어봤었던 LIS(Longest Increasing Subsequence) 문제이다. 이분 탐색 방법으로도 풀 수 있다하여 재도전한다.

LIS 리스트를 새로 만든다. 여기에는 A[0] 하나가 들어가 있다.

for로 A의 요소를 돌면서(item으로 두자), item이 LIS의 마지막 원소보다 크면 바로 LIS에 넣어주고, 작거나 같으면 이분탐색 함수로 item을 넣을 인덱스를 찾고 거기에 넣어준다. 이걸 끝까지 반복하면, LIS 리스트는 실제 LIS는 아니지만 "길이" 값 만큼은 조건을 만족하기에, len(LIS)를 print해준다.

핵심 아이디어:
어떤 수를 LIS에 넣을 때,
그 수가 들어갈 수 있는 가장 왼쪽 위치(가능한 낮은 인덱스)에 대체해서 넣는다면,
전체 수열의 증가성을 유지하면서 길이는 정확히 구할 수 있다.

예시 비교:
[10, 20, 30]에 25를 넣는다면 → 30을 25로 교체: [10, 20, 25]
→ 수열은 달라졌지만 길이는 그대로 유지

이유:
이후에 더 긴 수열을 만들려면 뒤에 더 큰 숫자들이 나와야 하는데,

25가 30보다 작으니 오히려 더 많은 경우의 수를 열어준다.

즉, "이 수열 자체는 가짜지만, 이 수열을 이용해 나중에 더 긴 수열을 만들 수 있는 가능성은 더 커지는" 전략

결론: 이분탐색 LIS 풀이의 본질
LIS 배열은 실제 수열 아님
LIS의 길이만이 진짜 정답임

수열을 유지하는 게 아니라, 최대한 많은 길이를 만들 수 있도록 교체하며 저장하는 것

시간복잡도는 O(N log N)으로 매우 효율적

그래서 “길이만 맞다”는 말은?
"실제 수열 내용은 안 맞아도, 최종적으로 만들 수 있는 가장 긴 수열의 길이는 정확하게 구한다"는 의미

해답 및 풀이

import sys

input = sys.stdin.readline

size_A = int(input())
list_A = list(map(int,input().split()))

def lower_bound(arr, target):
    L = 0
    R = len(arr) - 1 
    
    while L <= R:
        mid = (L + R) // 2
        if arr[mid] >= target:
            R = mid - 1
        
        else:
            L = mid + 1
    return L

LIS = []

for num in list_A:
    if not LIS or num > LIS[-1]:
        LIS.append(num)
    else:
        idx = lower_bound(LIS, num)
        LIS[idx] = num
        
print(len(LIS))

느낀점

LIS를 이분탐색의 관점으로 푼다는 것이 처음에 이해가 되지 않았고
수열의 값이 중요하지 않고 길이만으로 푼다는 것도 가능하구나 라는 것을 조금이나마 받아들이게 되었다. 시간복잡도를 O(N^2) 에서 O(nlogn)으로 줄이기 위해 이런 방식이 나왔는데 시간복잡도에 대해 더 공부해보고 고민해볼 필요를 느꼈다.