백준 : 11053 가장 긴 증가하는 부분수열

문제 이해

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열(LIS)을 구하는 프로그램을 작성하라. 여기서 가장 긴 증가하는 부분 수열이란, 어떤 수열에서 원래 순서를 유지하면서 앞보다 뒤가 점점 커지는 숫자들이며 그 중 가장 길게 고를 수 있는 경우를 출력하면 된다.

문제 분석

처음 이 문제를 접했을 때, 가장 먼저 고민한 것은 start와 end 값을 어떻게 정해야 할지였다. 이진 탐색의 구조를 떠올리긴 했지만, target 값은 매 반복마다 바뀌게 되고, 우리가 구하고자 하는 건 "원래 위치"가 아니라 LIS를 만들기 위한 위치이기 때문에 mid 값이 의미가 있는 건지 확신이 서지 않았다. 원래의 위치를 정확히 추적하려면 리스트를 정렬할 수 없고, 그렇다면 이진 탐색을 어떻게 시작할지 막막했다.

초기 구상은 단순했다. start부터 end까지 범위를 잡고, 조건에 따라 하나씩 값을 비교해가며 target보다 작은 값들을 별도의 리스트에 저장해보는 방식이었다. 그러나 이 방식은 결국 모든 값을 순차적으로 확인해야 하므로 완전 탐색에 가까웠다.

이 과정에서 고민하게 된 핵심은 무엇과 무엇을 비교해야 data 리스트에 값을 넣을 수 있느냐는 것이었다. 문득, 이 구조가 스택과 비슷하다는 느낌이 들었다. 새로운 수(target)가 들어올 때, data 리스트의 마지막 값보다 크다면 그대로 append해주는 방식으로 생각할 수 있었다.

그렇다면 원본 리스트를 순회하며 target을 바꾸고, 해당 값이 들어갈 위치를 data 리스트에서 찾아 넣어주는 방향으로 생각했다. 구체적으로는 target이 리스트 마지막 값보다 크면 append 하고 그렇지 않으면 이진 탐색으로 찾아낸 위치에 교체한다. 이러면 원본 배열을 정렬하지 않아도, 새로 만드는 리스트는 항상 정렬된 상태를 유지할 수 있다. 문제의 핵심은 원본 배열에서 하나씩 값을 꺼내서, 현재까지 만들어진 증가 수열의 후보가 되는 리스트(data)에 들어갈 자리를 이진 탐색으로 찾아가며 수열을 만드는 것이다.

변수 설명

n : 수열의 길이

A : 원본 수열

target : 현재 탐색 대상 숫자 (원본 수열 순회)

data : LIS 후보 리스트

idx : target이 들어갈 위치 (numbers 함수에서 리턴되는 인덱스)

처음에는 data=[A[0]]으로 시작. A의 나머지 수를 하나씩 target으로 뽑아서 비교하며 data[-1] < target 으로 증가 수열일 경우에는 append 하고 아니면 이진 탐색으로 적절한 위치를 찾아서 교체한다.

최종 코드

def numbers (target, data):
    start = 0
    end = len(data)-1
    
    while start <= end :
        mid = (start+end)//2
        if data[mid] == target :
            return mid
        if data[mid] >= target :
            end = mid -1
        else :
            start = mid + 1
    return start
n = int(input())
A = list(map(int, input().split()))
data = [A[0]]

for i in range (1, n):
    target = A[i]
    if data[-1] < target :  # data[-1] : 리스트의 마지막 원소
        data.append(target)
    else:
        idx = numbers(target, data)
        data[idx] = target
print(len(data))

손 코딩으로 이해하는 로직 설명

for 문에서 target을 설정 후에, 함수를 호출하며 위의 함수로 데이터가 넘어간다. 함수에서는 start 와 end를 기준으로 범위를 재설정하는 역할을 하며, 재설정된 범위로 for문에서 재탐색한다. 기존 백준 문제에서 주어지는 인풋 값이 아닌, 반례 사이트에서 코드 수정 전에 마주쳤던 반례를 기준으로 설정했다.