[Python] 백준 14003 - 가장 긴 증가하는 부분 수열 5

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

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

---

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

둘째 줄에는 정답이 될 수 있는 가장 긴 증가하는 부분 수열을 출력한다.

예제 입력 1 

6
10 20 10 30 20 50

예제 출력 1 

4
10 20 30 50

---

 

https://onn5.tistory.com/36

[Python] 백준 12015 - 가장 긴 증가하는 부분 수열 2

위에서 풀었던 가장 긴 증가하는 부분 수열 2는 문제에서 LIS의 길이만 출력하는 문제였다.

그러나 이번 문제는 부분 수열의 길이와 부분 수열의 원소도 모두 출력해야한다. 

 

이전처럼 푼다면 수열의 길이는 잘 나올지는 몰라도 LIS의 원소가 뒤죽박죽으로 출력될 수 있기 때문에 코드를 조금 더 추가해서 풀어야한다.

 

아래 코드를 보면 이전에 풀었던 코드와 비슷하단 것을 알 수 있다.

달라진 점이 있다면 dp 배열을 추가한 것과 아래에 역추적을 했다는 것 뿐이다.

하나씩 살펴보자.

 

dp 배열은 LIS에 들어가는 원소를 (인덱스, 값)으로 저장해준다.

아래 표를 통해 이해해보자.

인덱스	0	1	2	3	4	5
arr	2	1	3	5	9	2
LIS	2
dp	(0,2)

인덱스	0	1	2	3	4	5
arr	2	1	3	5	9	2
LIS	1
dp	(0,2)	(0,1)

인덱스	0	1	2	3	4	5
arr	2	1	3	5	9	2
LIS	1	3
dp	(0,2)	(0,1)	(1,3)

인덱스	0	1	2	3	4	5
arr	2	1	3	5	9	2
LIS	1	3	5
dp	(0,2)	(0,1)	(1,3)	(2,5)

인덱스	0	1	2	3	4	5
arr	2	1	3	5	9	2
LIS	1	3	5	9
dp	(0,2)	(0,1)	(1,3)	(2,5)	(3,9)

인덱스	0	1	2	3	4	5
arr	2	1	3	5	9	2
LIS	1	2	5	9
dp	(0,2)	(0,1)	(1,3)	(2,5)	(3,9)	(1,2)

 

위와 같이 LIS와 dp를 구했다면 역추적을 통해 실제 LIS를 구한다.

현재 LIS => 1 2 5 9

실제 LIS => 1 3 5 9

 

역추적의 알고리즘은 아래와 같다.

0.  last_idx = len(LIS)의 마지막 인덱스, 결과리스트 res=[] 

1. n-1부터 0까지 반복문 실행

2. dp[i][0]과 last_idx가 같다면

2-1. 해당 값인 dp[i][0]을 res에 추가 and last_idx -= 1

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

LIS = [arr[0]]
# dp에는 LIS에 들어간 인덱스를 저장해둔다.
dp = [(0,arr[0])] 

def binarySearch(e):
    start = 0
    end = len(LIS) - 1
    
    while start <= end:
        mid = (start + end) // 2
        
        if LIS[mid] == e:
            return mid
        elif LIS[mid] < e:
            start = mid + 1
        else:
            end = mid - 1
            
    return start


for i in range(1,n):
    if arr[i] > LIS[-1]:
        LIS.append(arr[i])
        dp.append((len(LIS)-1, arr[i]))

    else:
        idx = binarySearch(arr[i])
        LIS[idx] = arr[i]
        dp.append((idx, arr[i]))


print(len(LIS))

# 역추적
last_idx = len(LIS) - 1
res = []
for i in range(len(dp)-1, -1, -1):
    # i번째 값의 index와 마지막 인덱스값과 같다면
    if dp[i][0] == last_idx:
        res.append(dp[i][1])
        last_idx-=1

print(*res[::-1])

 

 

 

역추적이라는 개념이 흥미로웠고, 이분 탐색 문제가 또 어떤게 있는지 궁금해졌다.

당분간은 이분탐색에 빠질 것 같다