LIS를 왜 이분 탐색으로 푸는지는 코딩테스트에서 자주 막히는 대표 포인트입니다. DP로 길이를 구하는 방법은 이해했는데, 갑자기 이분 탐색이 나오면 문제 종류가 바뀐 것처럼 느껴지기 때문입니다.
이번 글에서는 LIS 최적화 풀이를 공식처럼 외우지 않고, 길이별로 가능한 꼬리값을 가장 작게 유지하는 전략으로 설명하겠습니다. 특히 왜 이분 탐색이 “정답 찾기”가 아니라 “교체 위치 찾기”로 쓰이는지도 함께 보겠습니다.
정리된 개념 참고로는 cp-algorithms의 LIS 정리가 있고, 이분 탐색의 경계 감각은 lower_bound 참고와도 연결됩니다.
DP 풀이에서는 무엇을 저장할까
O(n^2) DP에서는 보통 dp[i]를 i에서 끝나는 LIS 길이로 둡니다. 그래서 앞의 원소들을 다 보면서 현재 위치까지의 최적 길이를 계산합니다.
이 방식은 직관적이지만, 모든 i에 대해 이전 j를 다 확인해야 하므로 길이가 커지면 느려집니다. 즉 상태 정의는 분명하지만 비교 횟수가 많습니다.
이분 탐색 풀이에서는 무엇을 저장할까
여기서 핵심 전환이 일어납니다. 이분 탐색 풀이에서는 실제 LIS 전체를 저장하지 않고, 길이 k인 증가 부분 수열이 가질 수 있는 가장 작은 꼬리값을 저장합니다.
이 tails 배열은 “지금까지 찾은 LIS 자체”가 아니라 “앞으로 더 길게 확장되기 좋은 상태”를 저장하는 배열입니다. 그래서 tails 값을 더 작게 유지할수록 이후 숫자를 붙일 기회가 많아집니다.
from bisect import bisect_left
def lis_length(arr):
tails = []
for x in arr:
pos = bisect_left(tails, x)
if pos == len(tails):
tails.append(x)
else:
tails[pos] = x
return len(tails)이 코드에서 진짜 중요한 줄은 tails[pos] = x 입니다. 많은 입문자가 “왜 좋은 수열을 지우고 더 작은 값으로 교체하지?”에서 헷갈립니다. 하지만 이 교체는 길이를 줄이는 것이 아니라, 같은 길이를 더 유리한 꼬리값으로 바꾸는 작업입니다.
왜 이분 탐색이 필요한가
이 비교에서 중요한 것은 빠르기만이 아닙니다. DP는 각 위치의 의미가 잘 보이고, 이분 탐색 풀이는 상태를 더 압축해서 저장합니다. 그래서 후자가 더 빠르지만, 처음에는 왜 그렇게 저장해도 되는지 직관이 약할 수 있습니다.
tails는 항상 오름차순 형태를 유지합니다. 따라서 현재 값 x가 들어갈 자리를 이분 탐색으로 빠르게 찾을 수 있습니다. 즉 우리는 정답을 직접 찾는 것이 아니라, x가 기존 꼬리값 중 어디를 더 좋게 교체할 수 있는지를 찾는 것입니다.
이 점이 일반 lower bound 감각과도 닿아 있습니다. 관련 감각은 lower bound 글과도 이어집니다.
여기서 한 번 더 짚고 넘어가야 할 오해가 있습니다. 많은 사람이 tails 배열을 보면서 “현재까지의 LIS 수열”이라고 생각합니다. 하지만 tails는 실제 수열을 예쁘게 저장하는 용도가 아니라, 각 길이에 대해 가장 유리한 꼬리값을 남기는 압축 상태입니다.
가장 많이 헷갈리는 부분
- tails는 실제 LIS 수열이 아니다
- 교체는 정답을 버리는 게 아니라 더 유리한 꼬리값을 남기는 것이다
- 길이는 append로 늘어나고, 교체는 같은 길이를 더 좋게 유지하는 역할이다
- 실제 LIS 복원 문제는 길이 계산보다 한 단계 더 어렵다
특히 첫 번째가 중요합니다. tails 자체를 출력해서 실제 LIS라고 생각하면 거의 항상 오해가 생깁니다. tails는 길이 계산용 상태이지, 최종 수열 그 자체가 아닐 수 있습니다.
DP 기본 감각은 DP 글과도 이어집니다.
이 추적 도식을 한 번 따라가 보면, 교체는 망가뜨리는 작업이 아니라 더 유리한 상태를 남기는 작업이라는 점이 더 또렷해집니다. LIS 최적화가 갑자기 마법처럼 보이지 않게 되는 순간이 바로 여기입니다.
길이 계산과 수열 복원은 왜 다를까
길이만 구하는 문제에서는 tails처럼 압축된 상태만으로도 충분합니다. 하지만 실제 LIS 수열 하나를 복원하려면 각 원소가 어디에서 왔는지, 어떤 이전 원소를 이어받았는지 추적하는 정보가 추가로 필요합니다.
그래서 LIS 길이 계산을 이해했다고 해서 곧바로 복원 문제까지 쉬워지는 것은 아닙니다. 이 둘은 연결되어 있지만 요구하는 정보량이 다르기 때문입니다.
마무리
LIS에서 이분 탐색이 등장하는 이유는 문제를 위치 찾기로 바꾸기 때문이 아니라, 길이별 가능한 꼬리값을 효율적으로 유지해야 하기 때문입니다.
즉 실제 수열을 저장하는 대신, 더 긴 수열로 확장되기 좋은 상태를 저장한다는 사고 전환이 LIS 최적화의 핵심입니다.
