[백준 12738] 가장 긴 증가하는 부분 수열3

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

 

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)

 

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

---

접근

이진탐색으로 LIS를 구현하였다.

두 개의 과정으로 나눌 수 있다. 

1. LIS 배열을 채워나가는 과정

2. 이진탐색을 통해 대입할 자리 찾기

 

LIS 배열을 채워나갈 때는 초기에 0번째 인덱스의 수를 LIS 리스트에 넣고 이어서 1번 인덱스부터 탐색을 한다.

LIS의 마지막 원소와 비교하여 현재 숫자가 크다면 LIS 마지막 원소 뒤에 추가한다.

하지만 작다면 현재 원소가 들어갈 위치를 이진탐색을 통해 찾는다.

 

이진 탐색에서는 LIS 배열을 탐색하여 해당 원소를 찾고 들어갈 인덱스를 반환한다.

이후 반환된 인덱스에 해당 원소를 대입하는 과정을 거치게된다.

 

구현

- lis라는 리스트에 numbers의 첫 번재 원소를 넣는다.

- 이어서 numbers의 1번 인덱스부터 탐색을 진행한다.

- 현재 원소가 lis의 마지막 원소보다 크다면 그대로 lis 뒤에 추가한다.

- 그렇지않다면 현재 원소를 넣을 위치를 이진탐색으로 찾는다.

- 이진탐색을 통해 들어갈 자리를 받고 해당 원소를 그 자리에 대입한다.

N = int(input())
numbers = list(map(int, input().split()))
lis = [numbers[0], ]

for i in range(1, N):
    if lis[-1] < numbers[i]:
        lis.append(numbers[i])
    else:
        idx = binary_search(0, len(lis)-1, numbers[i])
        lis[idx] = numbers[i]

- 이진탐색을 통해 target이 들어갈 자리를 찾는다.

def binary_search(left, right, target):
    while left < right:
        mid = (left + right) // 2
        if lis[mid] < target:
            left = mid + 1
        else:
            right = mid

    return right

---

전체 코드

import sys
input = sys.stdin.readline

def binary_search(left, right, target):
    while left < right:
        mid = (left + right) // 2
        if lis[mid] < target:
            left = mid + 1
        else:
            right = mid

    return right

N = int(input())
numbers = list(map(int, input().split()))
lis = [numbers[0], ]

for i in range(1, N):
    if lis[-1] < numbers[i]:
        lis.append(numbers[i])
    else:
        idx = binary_search(0, len(lis)-1, numbers[i])
        lis[idx] = numbers[i]

print(len(lis))