[코딩테스트][백준] 🔥 백준 14003번 "가장 긴 증가하는 부분 수열 5" 문제: Python으로 완벽 해결하기! 🔥

문제 링크

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

🕒 Python 풀이시간: x

from bisect import bisect_left

def lis(arr):
    tails=[]
    tails_idx=[]
    prev_idx=[-1]*n

    for i in range(len(arr)):
        num=arr[i]
        pos=bisect_left(tails,num)
        if pos==len(tails):
            tails.append(num)
            tails_idx.append(i)
        else:
            tails[pos]=num
            tails_idx[pos]=i

        if pos>0:
            prev_idx[i]=tails_idx[pos-1]

    max_length=len(tails)

    list_lis=[]
    k=tails_idx[-1] if tails_idx else -1
    while k!=-1:
        list_lis.append(arr[k])
        k=prev_idx[k]
    list_lis.reverse()
    return max_length,list_lis

n=int(input())
arr=list(map(int,input().split()))
max_length,list_lis=lis(arr)
print(max_length)
print(*list_lis)

가장 긴 증가하는 부분 수열을 만드는 기존의 DP 형식이 아니라 이진 탐색을 이용한 방법으로 따로 prev_idx와 tails_idx를 두어서 전의 원소의 인덱스를 추적하여 복구하는 식으로 만들어진다. 따로 알고리즘이 쓰인거 같아서 정리해 두었다.

https://velog.io/@ouk/%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89%EC%9C%BC%EB%A1%9C-%EB%B9%A0%EB%A5%B4%EA%B2%8C-%ED%91%B8%EB%8A%94-%EC%B5%9C%EC%9E%A5-%EC%A6%9D%EA%B0%80-%EB%B6%80%EB%B6%84-%EC%88%98%EC%97%B4-LIS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%8C%80%EA%B3%B5%EA%B0%9C

이렇게 Python로 백준의 "가장 긴 증가하는 부분 수열5" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊