가장 긴 증가하는 부분수열 3

문제분석

꼬인 전깃줄을 풀었던 방법으로 푸는 LIS문제다.

2진 검색을 활용해 해당 숫자가 들어갈 수 있는 위치를 찾아간다. 그림을 보며 이해해보자. 아래의 숫자들을 예시로 썼는데, 이해를 돕기 위해 예제에서 숫자를 조금 변형해서 가져왔다.

10 20 5 30 25 50

Crepe

  • 리스트에 원소가 없거나 가장 마지막 원소보다 숫자가 크다면, 리스트에 해당 숫자를 추가해준다.
  • 10, 20을 위의 방법으로 추가해주었다.
  • 5가 들어갈 수 있는 위치를 찾아보자. 이 경우에는 Lower Bound를 이용해 숫자를 넣어준다. (Lower Bound로 숫자를 넣을 곳을 찾는 이유는 솔직히 아직 완전히 이해하지 못했다.) 이 방법을 사용하면 정렬을 깨지 않으면서 숫자를 넣을 수 있다고 한다. 추후에 보충해서 포스팅 하도록 하겠다…!
  • 위의 그림에서는 5와 25를 lower bound를 이용해서 리스트에 집어넣었다.

이렇게 만들어진 리스트의 길이는 LIS의 길이와 같다. 하지만, 그림에서도 볼 수 있듯이 이 리스트는 LIS원소들과는 차이가 있기 때문에 LIS자체를 알고 싶을 때는 추가적인 방법으로 구해주어야 한다. 원래 오늘 이 부분까지 다루려 했지만, 풀지 못한 관계로 이번 주 내로 포스팅 하도록 하겠다. 비슷한 유형의 문제로는 ‘전깃줄-2’ 가 있다. 다른 사람의 풀이를 참고해서 풀었었는데 2주만에 다시풀려고 하니 다시 백지 상태로 돌아갔다.

  • 이진 탐색에 대해서도 좀 더 공부해야할 필요성을 느꼈다.

CODE

import sys
read = sys.stdin.readline

n = int(read())
num = list(map(int, read().split()))

dp = [num[0]]

def binsearch(x):
    l, r = 0, len(dp)
    while True:
        mid = (l+r)//2
        if dp[mid] == x:
            break
        elif mid == 0:
            if dp[mid] > x:
                dp[mid] = x
                break
            else:
                l += 1
        elif dp[mid] > x:
            if dp[mid-1] < x:
                dp[mid] = x
                break
            elif dp[mid-1] == x:
                break
            else:
                r = mid-1
        else:
            l = mid+1
    return


for x in num[1:]:
    if x > dp[-1]:
        dp.append(x)
    else:
        if len(dp) != 1:
            binsearch(x)
        else:
            dp = [x]
print(len(dp))


틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다! 감사합니다.👍

[꼭 다시 풀어보기]