가장 긴 증가하는 부분 수열 2 ( 12015 번 )

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

 

---

🧠 알고리즘

• 이진 탐색 (Binary Search)

 

✔️ 동작 방식

1. answer 리스트를 만들어, 현재까지 찾은 증가 부분 수열의 마지막 원소 후보들을 저장한다.
2. 입력된 각 원소 i에 대해
   • _b_search(i, answer)로 answer에서 i가 들어갈 위치(=이진 탐색 결과)를 찾는다.
   • 만약 i가 answer의 마지막 원소보다 크면 (point == len(answer)), 수열을 확장하기 위해 answer.append(i) 한다.
   • 그렇지 않으면 기존 원소를 i로 교체하여 더 작은 값으로 갱신해, 이후 더 긴 수열이 나올 수 있도록 만든다.
3. 최종적으로 answer의 길이가 가장 긴 증가하는 부분 수열의 길이가 된다.

---

 

🧾 코드

import sys

def _b_search(num, now_list):
    l, r = 0, len(now_list) - 1
    answer = 0

    while l <= r:
        mid = (l + r) // 2
        now_num = now_list[mid]

        if now_num < num:
            l = mid + 1
        else:
            r = mid - 1

    return l
            

def _main(n, n_list):
    answer = []

    for i in n_list:
        point = _b_search(i, answer)
        if point == len(answer):
            answer.append(i)
        else:
            answer[point] = i

    return len(answer)

    
n = int(sys.stdin.readline().rstrip())
n_list = list(map(int, sys.stdin.readline().rstrip().split()))

print(_main(n, n_list))

---

 

⏱️ 시간 복잡도

for i in n_list : 주어진 숫자들을 순회 ( 선형 시간 복잡도 )
	_b_search(i, answer) : 들어갈 위치를 이진탐색으로 구함 ( 로그 시간 복잡도 )

해당 알고리즘 시간 복잡도 : 선형 로그 시간 복잡도 ( O(n log n) )