[백준]11053- 가장 긴 증가하는 부분 수열 문제 풀이(파이썬,Python)

문제

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

 

들어가며

DP 문제의 대표격이다.

하지만, 이 문제는 이분 탐색으로도 풀 수 있다.

이 글은 이분 탐색으로 어떻게 푸는지에 대한 이야기이다.

 

코드

from typing import MutableSequence


def lis_binary_search(arr : MutableSequence):
    lis = []  # LIS 배열 초기화
    for num in arr:
        pos = binary_search(lis, num)
        if pos == len(lis):
            lis.append(num)  # num이 가장 크다면 추가
        else:
            lis[pos] = num  # num으로 기존 값을 교체
    return len(lis)

def binary_search(lst : MutableSequence, data):
    left = 0
    right = len(lst)
    while left < right:
        middle = (left + right) // 2
        if lst[middle] < data:
            left = middle + 1
        else:
            right = middle
    return left

n = int(input())
arr = list(map(int, input().split()))

# 결과 출력
print(lis_binary_search(arr))

 

풀이

이분 탐색으로 푸는 방식을 생각보다 엄청 직관적이다.

바로 증가하는 부분 수열 직접 만들어나가면서 최대 길이를 찾는 것이다.

이 부분 수열을 만드는 메소드가 바로 lis_binary_search()이다.

def lis_binary_search(arr : MutableSequence):
    lis = []  # LIS 배열 초기화
    for num in arr:
        pos = binary_search(lis, num)
        if pos == len(lis):
            lis.append(num)  # num이 가장 크다면 추가
        else:
            lis[pos] = num  # num으로 기존 값을 교체
    return len(lis)

전체 수열을 한번 도는 for문을 진행한다.

그리고 현재 부분 수열 내부에서 선택한 값의 위치를 이분 탐색을 이용해서 찾는다.

그럴 때, 만약 이분 탐색 결과로 배열의 길이가 나왔다면 맨마지막까지 갔다는 것으로 이는 배열에서 최대값임을 의미한다.

그래서 append를 진행해서 맨 뒤에 넣어준다.

검색하는 값이 최대값이 아니라는 것이다. 그래서 이미 배열에 있는 값이라면 그 위치를, 없는 값이면 가장 가까운 값을 pos가 가리키게 된다. 이는 이분 탐색의 결과로 만들어낸 것이다.

그리고 그 기존값과 교체한다

 

그러면 왜 교체하는가?

이는 LIS의 배열 길이를 유지하기 위함이다.

결국 이런 경우는 10 20 10 이 있을 때, 마지막 10을 부분 수열 배열에 추가할려는 상황과 일치한다.

이진 탐색은 0을 리턴할 것이다.

기존 값이랑 교체를 한다면 LIS 배열은 전혀 손상이 없이 계속 증가하는 수열을 유지하게 된다.

이를 반복해서 마지막까지 나아가면 최종 LIS 배열이 완성이 돼고 이는 가장 긴 증가하는 부분 수열이 되게 된다.

 

이분 탐색을 어떻게 구현하는가?

이거도 매우 중요하다.

정확히 바꿔야하는 자리를 가리켜야만 한다.

def binary_search(lst : MutableSequence, data):
    left = 0
    right = len(lst)
    while left < right:
        middle = (left + right) // 2
        if lst[middle] < data:
            left = middle + 1
        else:
            right = middle
    return left

위와 같이 구현하였는데 이는 자주 쓰는 right = len(lst) - 1과 큰 차이가 존재한다.

right = len(lst) - 1 는 left와 right를 전혀 포함하지 않는다. (left, right) 라고 표현한다.

하지만 위 코드는 left는 포함하지만 right는 포함하지 않는다. [left, right) 라고 표현한다.

left는 포함하지만 right는 포함하지 않는다는 특징 때문에, lst에 빈 배열이 들어가도 문제가 없으며, for range 문의 작동 방식과 유사하므로 매우 직관적이다.

그리고 파이썬 표준 라이브러리들의 이진 탐색은 다 위와 같이 구현되어 있다고 한다.