백준 - 12738번 가장 긴 증가하는 부분 수열 3 python 문제풀이 [Hellfer]

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

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

🔷 알고리즘 분류 - 이분탐색, O(n log n)   난이도 - 골드 2

🔶 문제 이해하기

 

bisect는 파이썬의 내장 모듈로, 이진 검색(binary search)과 정렬된 리스트에 대한 삽입 연산을 위한 메서드를 제공합니다. 기본적으로 '이미 정렬된' 리스트에 대해 작동하며, 정렬된 리스트에 원소를 삽입하거나, 리스트 내에서 특정 원소의 위치를 찾을 때 사용됩니다.

주로 사용되는 bisect 모듈의 함수들은 다음과 같습니다:

1. bisect_left(list, num, start, end): 이 함수는 정렬된 리스트에서 num이 들어갈 위치를 찾아 반환합니다. 만약 num이 리스트에 이미 존재한다면, 그 원소의 왼쪽 인덱스를 반환합니다. start, end는 검색을 시작할 범위를 나타내며, 생략 가능합니다.

2. bisect_right(list, num, start, end) 또는 bisect(list, num, start, end): 이 함수는 bisect_left와 비슷하지만, num이 리스트에 이미 존재하는 경우 그 원소의 오른쪽 인덱스를 반환합니다.

3. insort_left(list, num, start, end): 이 함수는 num을 이미 정렬된 리스트에 적절한 위치에 삽입합니다(num이 리스트에 이미 존재하는 경우 왼쪽 위치). start, end는 삽입을 시작할 범위를 나타내며, 생략 가능합니다.

4. insort_right(list, num, start, end) 또는 insort(list, num, start, end): num을 이미 정렬된 리스트에 적절한 위치에 삽입합니다(num이 리스트에 이미 존재하는 경우 오른쪽 위치)

 

이들 함수는 모두 이진 검색 알고리즘을 사용하여 실행 시간을 크게 줄입니다. 때문에 큰 리스트에서 원소를 검색하거나 삽입할 때 매우 효율적입니다.

🔶문제풀이 - 이분탐색을 이용한 풀이,   시간복잡도 - O(n log n)

# sys와 bisect 모듈을 가져옵니다.
import sys
import bisect

# 수열의 길이 N을 입력받습니다.
N = int(sys.stdin.readline())
# 수열을 입력받아 정수형으로 변환한 후 리스트에 저장합니다.
sequence = list(map(int, sys.stdin.readline().split()))

# dp 리스트를 생성하고 첫 번째 요소로 수열의 첫 번째 값을 넣습니다.
dp = [sequence[0]]

# 수열의 두 번째 요소부터 마지막 요소까지 순회합니다.
for i in range(1, N):
    # 만약 현재 값이 dp의 마지막 값보다 크다면
    if dp[-1] < sequence[i]:
        # 현재 값을 dp에 추가합니다.
        dp.append(sequence[i])
    else:
        # 만약 현재 값이 dp의 마지막 값보다 작거나 같다면
        # 이분 탐색으로 현재 값이 dp에 들어갈 위치를 찾고, 그 위치의 값을 현재 값으로 변경합니다.
        dp[bisect.bisect_left(dp, sequence[i])] = sequence[i]

# dp 리스트의 길이를 출력합니다. 이 값이 주어진 수열에서 가장 긴 증가하는 부분 수열의 길이입니다.
print(len(dp))

🔶 문제 해결전략

# 수열의 두 번째 요소부터 마지막 요소까지 순회합니다.
for i in range(1, N):
    # 만약 현재 값이 dp의 마지막 값보다 크다면
    if dp[-1] < sequence[i]:
        # 현재 값을 dp에 추가합니다.
        dp.append(sequence[i])
    else:
        # 만약 현재 값이 dp의 마지막 값보다 작거나 같다면
        # 이분 탐색으로 현재 값이 dp에 들어갈 위치를 찾고, 그 위치의 값을 현재 값으로 변경합니다.
        dp[bisect.bisect_left(dp, sequence[i])] = sequence[i]

 

예를 들어, 주어진 수열이 [-10, -20, -10, -30, -20, -50]이라고 가정해 봅시다.

1. dp 리스트를 생성하고 첫 번째 요소로 수열의 첫 번째 값을 넣습니다. 따라서 dp = [-10]

2. 수열의 두 번째 요소부터 마지막 요소까지 순회합니다.
● 두 번째 요소인 -20은 dp의 마지막 값인 -10보다 작습니다. 따라서 이분 탐색을 사용하여 -20이 들어갈 위치를 찾습니다. 이분 탐색 결과 -20은 dp의 첫 번째 위치에 들어가므로, 그 위치의 값을 -20으로 변경합니다. 따라서 dp = [-20]

● 세 번째 요소인 -10은 dp의 마지막 값인 -20보다 크므로 dp에 추가합니다. 따라서 dp = [-20, -10]

● 네 번째 요소인 -30은 dp의 마지막 값인 -10보다 작습니다. 따라서 이분 탐색을 사용하여 -30이 들어갈 위치를 찾습니다. 이분 탐색 결과 -30은 dp의 첫 번째 위치에 들어가므로, 그 위치의 값을 -30으로 변경합니다.

따라서 dp = [-30, -10]

● 다섯 번째 요소인 -20은 dp의 마지막 값인 -10보다 작습니다. 따라서 이분 탐색을 사용하여 -20이 들어갈 위치를 찾습니다. 이분 탐색 결과 -20은 dp의 첫 번째 위치에 들어가므로, 그 위치의 값을 -20으로 변경합니다. 

따라서 dp = [-20, -10]

● 마지막 요소인 -50은 dp의 마지막 값인 -10보다 작습니다. 따라서 이분 탐색을 사용하여 -50이 들어갈 위치를 찾습니다. 이분 탐색 결과 -50은 dp의 첫 번째 위치에 들어가므로, 그 위치의 값을 -50으로 변경합니다.

따라서 dp = [-50, -10]

3. dp 리스트의 길이를 출력합니다. 이 값이 주어진 수열에서 가장 긴 증가하는 부분 수열의 길이입니다.

따라서 결과는 2가 됩니다

 

🤗파이팅입니다~ 여러분!!🤗