Coding 공부

import sys

def input():
    return sys.stdin.readline().rstrip()



N = int(input())
A = list(map(int,input().split()))
dict_A = {}
for k in range(N):
    dict_A[A[k]] = k

B = list(map(int,input().split()))
convert_B = [0]*N
for ind,k in enumerate(B):
    convert_B[ind] = dict_A[k]
LIS = [convert_B[0]]



for ind in range(1,N):
    if convert_B[ind] > LIS[-1]:
        LIS.append(convert_B[ind])
    else:
        left = -1
        right = len(LIS)
        while left + 1 < right:
            mid = (left + right)//2

            if LIS[mid] >= convert_B[ind]:
                right = mid
            else:
                left = mid
        LIS[right] = convert_B[ind]

print(len(LIS))

사실 이 문제는 LCS로 분류되어있지만, LIS 태그도 포함되어 있어야한다고 생각한다.

기존의 LCS로 하면 N^2이 걸리기 때문에, 입력사항을 보면 터질수 밖에 없다.

근데 우리는 여기서 문제의 조건을 잘 봐야한다.

문제의 조건에서 1부터 N까지 정수가 모두 한 번씩 등장하는 두 수열 A와 B가 주어졌을 때 라고 되어있다.

이 말은 각 수열에 있는 값들은 중복되는것은 없고, 하나하나가 유니크 하나는 것이다.

이 최장 부분수열에서는 인덱스가 증가하는 방향으로 부분수열을 구해야한다.

그렇다는 말은 A와 B라는 각 리스트가 있을 때, B의 각 값들이 A에 어디에 있는지 해놓으면,

B의 값은 A에 위치한 인덱스로 대치가 된다.

그런데 우리는 부분수열을 구할때, 인덱스가 증가하는 수선대로 해야한다.

즉 이렇다는 말은 A의 인덱스로 바뀐 B의 수열을 최장 증가 부분 수열의 길이를 구하면,

이것은 곧 A와 B의 최장 부분 수열이 됨을 알 수 있게 된다.

이러한 트릭을 가지고, LIS의 길이를 구하는 이분탐색 기법을 통해서 구해주면 된다.

N = int(input())
arr = list(map(int,input().split()))

LIS = [arr[0]]
for i in range(1,len(arr)):
    if arr[i] > LIS[-1]:
        LIS.append(arr[i])
    else:
        start = 0
        end = len(LIS)
        idx = len(LIS)-1
        while start < end:
            mid = (start+end)//2
            if LIS[mid] >= arr[i]:
                idx = min(idx,mid)
                end = mid
            else:
                start = mid + 1
        LIS[idx] = arr[i]

LIS_CNT = len(LIS)
print(LIS_CNT)

N = int(input())
arr = list(map(int,input().split()))
LIS = [arr[0]]
parents = [-1]*N
parents[0] = 0
temp = 0
for i in range(1,len(arr)):
    if arr[i] > LIS[-1]:
        parents[i] = len(LIS)
        LIS.append(arr[i])
    else:
        start = 0
        end = len(LIS)
        idx = len(LIS)-1
        while start < end:
            mid = (start+end)//2
            if LIS[mid] >= arr[i]:
                idx = min(idx,mid)
                end = mid
            else:
                start = mid + 1
        LIS[idx] = arr[i]
        parents[i] = idx

LIS_CNT = len(LIS)
result = [-1]*LIS_CNT

for i in range(N-1,-1,-1):
    if parents[i] == LIS_CNT-1:
        result[LIS_CNT-1] = arr[i]
        LIS_CNT -= 1
print(len(result))
print(*result)
    
# https://jins-dev.tistory.com/entry/%EC%B5%9C%EC%A0%81%ED%99%94%EB%90%9C-LISLongest-Increasing-Subsequence-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EA%B3%BC-%ED%95%B4-%EC%B0%BE%EA%B8%B0

https://jins-dev.tistory.com/entry/%EC%B5%9C%EC%A0%81%ED%99%94%EB%90%9C-LISLongest-Increasing-Subsequence-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EA%B3%BC-%ED%95%B4-%EC%B0%BE%EA%B8%B0

위의 블로그를 참조해서 코드를 풀었다.

기본적인 원리는 다음과 같다. LIS를 구하면서 parents라는 배열에 해당 LIS에 들어갔던 idx를 저장해준다.

그리고 난뒤 마지막에 LIS의 크기에서부터 하나씩 내려가면서 그에 맞는 배열 값들을 찾아주면 된다.

def find_lis(array):
    dp = [0]*len(array)

    for i in range(len(array)):
        dp[i] = 1
        for j in range(i+1):
            if arr[i] > arr[j]:
                dp[i] = max(dp[i],dp[j] + 1)
    return dp
def find_lds(array):
    dp = [0]*len(array)

    for i in range(len(array)):
        dp[i] = 1
        for j in range(i+1):
            if array[i] < array[j]:
                dp[i] = max(dp[i],dp[j] + 1)
    return dp
        




N = int(input())

arr = list(map(int,input().split()))

lis_dp = find_lis(arr)
result = 0
for ind in range(N):
    lds_dp = find_lds(arr[ind:])
    result = max(result,lis_dp[ind] + max(lds_dp) -1)
print(result)

처음에 푼 방식이다. 먼저 가장 긴 증가 부분 수열의 길이를 구하고 난뒤,

각 index마다 잘라서 가장 긴 감소 부분 수열을 구해서 더해주었다.

이러한 방식으로 푸니깐 시간이 오래걸렸다.

def find_lis(array):
    dp = [0]*len(array)

    for i in range(len(array)):
        dp[i] = 1
        for j in range(i+1):
            if arr[i] > arr[j]:
                dp[i] = max(dp[i],dp[j] + 1)
    return dp
def find_lds(array):
    dp = [0]*len(array)

    for i in range(len(array)-1,-1,-1):
        dp[i] = 1
        for j in range(i+1,len(array)):
            if array[i] > array[j]:
                dp[i] = max(dp[i],dp[j] + 1)
    return dp
        




N = int(input())

arr = list(map(int,input().split()))

lis_dp = find_lis(arr)
lds_dp = find_lds(arr)

result = 0
for ind in range(N):
    result = max(result,lis_dp[ind]+lds_dp[ind]-1)
print(result)

그 다음으로 푼 방식이다.

LIS를 두군데로 해서 구해주었다.

앞에서 가장 긴 뒤에서 가장 긴 증가 부분수열을 구해주었다.

긴 바이토닉 부분 수열을 보면 가운데를 중심으로 좌측에서는 긴 증가부분 수열이고, 우측은 감소부분수열인데, 이걸 역으로 보면 우측을 거꾸로 돌리면 증가 부분 수열이 된다.

이러한 점을 이용해 좌측에서부터의 긴 증가부분 수열과 수열을 거꾸로 해서 긴 증가부분 수열의 길이를 구해, 서로 더해주면 긴 바이토닉 부분 수열이 나온다.

# 2631 줄 세우기
# LIS의 길이를 구하기 위한 방법 복잡도 O(Nlogn)로 구하기 
N = int(input())
arr = list(int(input()) for _ in range(N))
LIS = []
LIS.append(arr[0])
temp = 0
for number in arr[1:]:
    for ind,val in enumerate(LIS):
        if number > val and number not in LIS:
            temp = number
        elif number < val and number not in LIS:
            LIS[ind] = number
            temp = 0
    if temp:
        LIS.append(temp)
    temp = 0
print(N-len(LIS))
    

 이 문제는 최장 증가 부분 순열을 활용한 문제이다.  크기대로 줄을 세우는 것이기 때문에, 주어진 배열에서, 가장 긴 증가 부분 순열을 제외하고 나머지 부분을 움직이면 정답을 구할 수 있따.

# 2565 전깃줄

N = int(input())
dp = [0]*501
arr = []
for _ in range(N):
    n1,n2 = map(int,input().split())
    arr.append((n1,n2))
arr.sort()
result = []
result.append(arr[0][1])
temp = 0
for k1,k2 in arr[1:]:
    for ind,val in enumerate(result):
        if val > k2 and k2 not in result:
            result[ind] =k2
            temp = 0
        elif val < k2 and k2 not in result:
            temp = k2
    if temp:
        result.append(temp)
    temp = 0


print(N-len(result))

개인적으로 어려워 하는 LIS 계열의 문제였다.

전깃줄 A를 기준으로 sort를 해준 다음에,  전깃줄 B를 기준으로 가장 긴 증가하는 수열의 구해주면 된다.

그렇게 되면, 선이 꼬이지 않고 설치할 수 있는 최대수가 되고, 주어진 N에서 최대수를 빼주면 된다.

코드 자체를 설명해보면 초기값으로 가장 첫번쨰  B 전깃줄을 넣어주고,

전체 데이터 들어진 행렬을 반복문을 돌리면서, LIS가 저장된 값과 비교를 하면서 LIS에 저장된 값보다 적으면 바로 그자리를  교체 해준다. 그리고 LIS가 저장된 값보다 전부다 크면 끝에 추가해주면 된다.

이 방법은 실제 LIS의 수열을 구하는 것이 아닌, 최장 길이를 구하기 위한 O(Nlogn)의 방식이다. 만약 실제 LIS를 구해야 하는 경우에는 다른 풀이를 찾아야한다.