[백준] 2565번 : 전기줄

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

해당문제는 다이나믹 프로그래밍으로 문제를 해결하였습니다.

LIS 문제로 최장증가 부분 수열 을 찾는 문제입니다. ( Longest Increasing Subsequence)

LIS란 : 원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대한 부분 수열을 최장 증가 부분 수열이라고 합니다.

예를들어, {6,2,5,1,7,4,8,3} 이라는 배열이 있을경우, LISSMS { 2,5,7,8 } 이 됩니다.

일반적으로 길이가 얼마인지 푸는 방법은 DP 다이나믹 프로그래밍을 이용하는 것입니다.

N = int(input())

queue = []
for _ in range(N):
    a, b = map(int ,input().split())
    
    queue.append((a,b))
    
queue.sort()

dp = [0 for _ in range(N)]
dp[0] = 1
for i in range(1,len(queue)):
    dp[i] = 1
    for j in range(i):
        if queue[j][1] < queue[i][1]:
            dp[i] = max(dp[j] + 1, dp[i])
                
print(N - max(dp))

시간복잡도를 개선하기 위하여 이분 탐색을 활용합니다.

LIS형태를 유지하기 위해 주어진 배열의 인덱스를 하나씩 살펴보면서 그 숫자가 들어갈 위치를 이분 탐색해서 넣습니다. 이분탐색은 일반적으로 O(logN)으로 알려져 있으므로, 이 문제의 시간복잡도를 O(nlogN)으로 개선 시킬 수 있습니다.

from bisect import bisect_left
N = int(input())

queue = []
for _ in range(N):
    a, b = map(int ,input().split())
    
    queue.append((a,b))
    
queue.sort()

temp = []
temp.append(queue[0][1]) # 첫번째 인자를 넣는다.
for i in range(1,len(queue)):
    if queue[i][1] > temp[-1]:
        temp.append(queue[i][1])
    else:
        idx = bisect_left(temp, queue[i][1])
        temp[idx] = queue[i][1]

print(N - len(temp))