★DP Expert(Easy) I - 4 Solved★

★ 14003 가장 긴 증가하는 부분 수열 5 ★

 

import sys
input=sys.stdin.readline
N=int(input())
A=list(map(int,input().split()))

#binary search
def binary_search(l, i, x):
    start,end=0,len(l)-1
    while start<=end:
        mid=(start+end)//2
        if x <= l[mid]:
            end=mid-1
            ans=mid
        else:
            start=mid+1
    l[ans]=x
    i.append(ans+1)
    return l, i

#LIS
ans_i=[1]
ans_num=[A[0]]
cur_ans_l=1
LIS=[]

for x in range(1,N):
    if ans_num[-1] < A[x]: #just add
        cur_ans_l+=1
        ans_i.append(cur_ans_l)
        ans_num.append(A[x])
    else: #searching the spot
        ans_num,ans_i=binary_search(ans_num, ans_i, A[x])
    
LIS_length = len(ans_num)
print(LIS_length)
for i in range(len(ans_i)-1,-1,-1):
    if LIS_length == 0:
        break

    if ans_i[i] == LIS_length:
        LIS.append(A[i])
        LIS_length-=1

print(*reversed(LIS))

 

⛹️ LIS의 길이와 내용을 O(nlogn) 시간 복잡도 이내로 구하는 교과서 문제. LIS의 길이는 ans_num list에서 binary search로 update하며 내용 추가. LIS의 내용은 ans_i list에서 앞선 binary search로 삽입되는 원소의 index를 update하며 거꾸로 최댓값부터 1이 될때까지 해당 되는 index의 list 원소 수열. 자세한 내용은 LIS 포스팅 참조

---

★ 23035 가톨릭대는 고양이를 사랑해 ★

import sys
input=sys.stdin.readline

def binary_search_lis(arr,n):
    start,end=0,len(arr)-1
    while start<=end:
        mid=(start+end)//2
        if n < arr[mid]:
            ans = mid
            end = mid-1
        else:
            start = mid+1
    arr[ans] = n
    return arr

N,M=map(int,input().split())
cats=[]
T=int(input())
for _ in range(T):
    r,c=map(int,input().split())
    if 0<=r<=N and 0<=c<=M:
        cats.append((c,r))
cats=sorted(cats,key=lambda x: (x[0],x[1]))
n=len(cats)

dp=[cats[0][1]]

for i in range(1,n):
    if dp[-1]<=cats[i][1]:
        dp.append(cats[i][1])
    else:
        dp=binary_search_lis(dp,cats[i][1])
print(len(dp))

 

⛹️ 중복을 허용하는 변형 LIS(Longest Increasing Subsequence) "LNDS(Longest Non-Decreasing Subsequence)" 문제.

 

⛹️ 예시 분석

: 위 첫번째 예시로 주어진 고양이의 위치를 y를 기준으로 오름차순 정렬 - 이후 x를 기준으로 오름차순 정렬하면 아래와 같다.

 

★ ① y를 기준으로 정렬 → x를 기준으로 정렬

: 쿠기는 무조건 가장 빠르게 다솔관까지 이동한다고 가정했다. 따라서, 쿠기는 y좌표를 기준으로 계속 증가하는 방향(아래로 내려가는 방향) & x좌표 기준으로 계속 증가하는 방향(오른쪽으로 이동하는 방향)으로만 이동한다.

 

이는, y와 x 좌표 기준 두 방향 모두 비내림차순 정렬을 해야한다는 뜻. y기준으로 일단 비내림차순 정렬 후, 동일 y좌표를 가진 고양이가 있다면(동일한 위치를 가진 2마리 이상의 고양이는 존재하지 않는다 가정), x 기준 비내림차순 정렬 필요.(위 (x,y) (1,6), (5,6) 해당)

 

★ ② y 기준으로 정렬된 여러 x에서 LNDS의 길이 찾기

: 무조건 y는 비내림차순으로 쿠거가 이동하는 상태에서 x가 비내림차순으로 되어 있는 고양이들을 밥을 챙겨줄 수 있다. 따라서, 이는 위 ①로 인해 정렬된 후의 x에서 LNDS의 길이를 구하면 된다.

 

★ ③ 관건은, y는 다르되 동일한 x에 위치해 있는 고양이들 고려 필요

: 전형적인 LIS 알고리즘은 '증가'하는 부분수열의 길이를 구하는 알고리즘이다. 하지만, 위 (x,y) (2,1) / (2,2)와 같이 x가 동일한, 즉 가로 방향으로 동일하게 위치해 있을 수 있다. 아래 예시 그림을 확인하자.

: 동일한 y(세로축)에 두 마리 이상의 고양이가 다른 x로 위치해 있는 경우이다. 이 때, 동일한 y(2)에 있는 두 고양이(1, 2) 모두 밥을 주고, 그 다음 y(3)로 내려간다. 이 때, 이전 x(2)와 같아도 y로 내려갔기 때문에 밥을 줄 수 있다. 따라서 전형적인 LIS 알고리즘 코드를 변형한 '가장 긴 비내림차순 수열'의 길이를 구한다. 따라서 위 표와 같이 빨간색 숫자 1, 2, 2, 2, 3 총 5마리에게 밥을 먹일 수 있다.

 

Q. 무조건 동일 y에서 모든 x의 고양이를 먹이는게 가장 많은 고양이를 먹일 수 있을까? 동일 x 방향인 아래 방향으로 내려가서 고양이를 먹이면 안될까?

A: 즉 위 그림과 같이, 빨간색으로 이동하면 4마리만 먹일 수 있고, 하늘색으로 이동하면 5마리를 먹일 수 있다. 따라서 무조건 위 ①대로 정렬이 최적의 해를 보장하지는 않음을 알 수 있다. 그러면 어떻게 위 그림 case까지 적용한 풀이를 생각해낼 수 있을까? 정답은 LIS(Onlogn)의 dp array 구성에 있다.

 

: LIS(Onlogn)의 길이를 구성할 때 최종 dp array의 구성 내용은 실제 LIS의 내용과 다르다. 아래 그림 참고.

: 위 그림과 같이, 우리는 LIS의 '길이'만 궁금하므로, 실제 최종 update된 dp array는 [2, 10, 40, 80]으로 원래 구성된 10 - 2 - 40 - 80 순서와 다르다. 즉, LIS dp array를 update하는 과정에서 위 질문의 실마리를 얻을 수 있다.

ex) [8, 10, 14, 10]이 있다면

(1) 본래 LIS(Onlogn) 알고리즘의 경우 이분 탐색에서 n<= arr[mid] 부등식으로 바꿀 위치 ans index를 업데이트 하기 때문에 기존 10 대신 새로운 10이 들어가 [8, 10, 14] 완성

 

(2) 변형 중복 허용 LNDS(Onlogn) 알고리즘의 경우 이분 탐색에서 n<arr[mid] 부등식으로 기존 14 대신 새로운 10이 들어가 [8, 10, 10]이 완성된다.

 

이는 증가수열이 아니라 중복 허용 비내림차순의 최장 길이를 구해야 하기 때문이다. 중복 허용 비내림차순이라면, 중복은 허용하기 때문에 dp array의 맨 끝 원소가 14가 아니라 중복으로 10을 붙이는게 맞기 때문.

 

: 위 예시의 원리를 다시 위 고양이 그림에 적용하자면, x표인 고양이(2) 대신 그 다음 줄 고양이(1)가 (중복 허용이므로 원래 고양이(1) 그 다음에 와도 된다.) 들어간다. 이는 곧, 같은 줄에 있는 고양이를 먹일 수 있다는 문제(중복 허용 비내림차순 최장 길이 구하기 알고리즘) 내용과 일맥상통한다. 현재 위치에서 뒤로 갈 순 없지만, 같은 줄에 있는 고양이가 있다면 중복 허용해서 ans를 update해주는 원리가 이 문제의 핵심!

 

★ ④ 변형 LNDS(Longest Non-Decreasing Subsequence) (Onlogn) 일부 코드

 

(1) update dp array의 맨 끝 원소보다 크거나 '같다'면 array에 추가

dp=[cats[0][1]]

for i in range(1,n):
    if dp[-1]<=cats[i][1]:
        dp.append(cats[i][1])
    else:
        dp=binary_search_lis(dp,cats[i][1])

 

(2) update dp array의 맨 끝 원소보다 작다면, binary searching에서 n이 자신보다 큰 원소 중 가장 작은 원소 대신 (크거나 같은 원소 x) 대체

def binary_search_lis(arr,n):
    start,end=0,len(arr)-1
    while start<=end:
        mid=(start+end)//2
        if n < arr[mid]:
            ans = mid
            end = mid-1
        else:
            start = mid+1
    arr[ans] = n
    return arr

---

★ 2568 전깃줄 - 2 ★

import sys
input=sys.stdin.readline

def binary_search_lis(arr,arr_i,N):
    start,end=0,len(arr)-1
    while start<=end:
        mid=(start+end)//2
        if N<=arr[mid]:
            ans=mid
            end=mid-1
        else:
            start=mid+1
    arr[ans] = N
    arr_i.append(ans+1)
    return arr,arr_i      



N=int(input())
AB=[]
for _ in range(N):
    a,b=map(int,input().split())
    AB.append((a,b))
AB=sorted(AB,key= lambda x:(x[0]))
values=[x[1] for x in AB]

arr=[values[0]]
arr_i=[1]
cur_i=1

for x in range(1,N):
    if arr[-1] < values[x]:
        cur_i+=1
        arr.append(values[x])
        arr_i.append(cur_i)
    else:
        arr,arr_i=binary_search_lis(arr,arr_i,values[x])

print(N-len(arr))

LIS_length=len(arr) 
remove_idxs=[]
for x in range(N-1,-1,-1):
    if arr_i[x] == LIS_length:
        LIS_length-=1
    else:
        remove_idxs.append(x)
remove_idxs.sort()

for idx in remove_idxs:
    print(AB[idx][0])

 

⛹️ 전봇대 A를 기준으로 오름차순 정렬 후 전봇대 B의 LIS(Onlogn)를 구하는 문제. 이 때 LIS의 내용까지 출력해야 하므로 LIS index 역추적까지 고려. 위 14003 문제와 동일

---

★ 1974 Jump Jump Championship ★

import sys
input=sys.stdin.readline


#binary search
def binary_search(l, i, x):
    start,end=0,len(l)-1
    while start<=end:
        mid=(start+end)//2
        if x <= l[mid]:
            end=mid-1
            ans=mid
        else:
            start=mid+1
    l[ans]=x
    i.append(ans+1)
    return l, i


for _ in range(int(input())):
    N=int(input())
    A=list(map(int,input().split()))
    #LIS
    ans_i=[1]
    ans_num=[A[0]]
    cur_ans_l=1
    LIS_i=[]

    for x in range(1,N):
        if ans_num[-1] < A[x]: #just add
            cur_ans_l+=1
            ans_i.append(cur_ans_l)
            ans_num.append(A[x])
        else: #searching the spot
            ans_num,ans_i=binary_search(ans_num, ans_i, A[x])
        
    LIS_length = len(ans_num)
    print(LIS_length)
    for i in range(len(ans_i)-1,-1,-1):
        if LIS_length == 0:
            break

        if ans_i[i] == LIS_length:
            LIS_i.append(i+1)
            LIS_length-=1

    print(*reversed(LIS_i))

 

⛹️ LIS(Onlogn)의 길이와 역추적 경로 출력 전형적인 문제

---