[python] 가장 긴 증가하는 부분 수열 시리즈

가장 긴 증가하는 부분 수열 (백준 11053번)

 

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

 

import sys
input = sys.stdin.readline

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

dp = [0 for _ in range(n)]
maxa = 0

for i in range(n):
    maxt = 0
    for j in range(i):
        if a[i] > a[j]:
            maxt = max(maxt, dp[j])
    dp[i] = maxt + 1
    maxa = max(maxa, dp[i])

print(maxa)

dp[i] : 0부터 i까지 i를 포함하는 가장 길게 증가하는 수열의 길이

앞의 계산을 뒤의 계산에서 활용하기 위해서 마지막 요소를 포함시켜 점화식을 정의하는 방식이다. dp에서 자주 보이는 방식이다.

점화식 : dp[i] = max(dp[k]) + 1 (dp[i]보다 dp[k]가 작은 0과 i-1 사이의 k에 대해...)

(정답)

 

---

 

가장 긴 증가하는 부분 수열 2 (백준 12015번)

 

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

 

import sys
input = sys.stdin.readline

n = int(input())
a = [0] + list(map(int, input().split()))

dp = [0 for _ in range(n + 1)]
b = [0 for _ in range(n + 1)]
idx = 0
maxl = 1
b[1] = a[1]
dp[1] = 1

def binarysearch(l, r, now):
    while l < r:
        mid = (l + r) // 2
        if b[mid] < now:
            l = mid + 1
        else:
            r = mid
    return l

for i in range(2, n + 1):
    if b[maxl] < a[i]:
        maxl += 1
        b[maxl] = a[i]
        dp[i] = maxl
    else:
        idx = binarysearch(1, maxl, a[i])
        b[idx] = a[i]
        dp[i] = idx

print(maxl)

dp 배열과 점화식은 위와 동일하다. 그런데 위의 풀이대로 풀면 시간 초과가 나온다. (오답)

시간을 줄이기 위해 dp 배열을 채울 때 순차 탐색이 아닌 이분 탐색을 활용하여야 한다. 

이분 탐색은 정렬된 데이터에만 적용할 수 있으므로 필요한 데이터들을 추가 공간 b에 오름차순 정렬이 되도록 채워가며 b에서 이분 탐색을 해주는 것이다. (정답)

 

---

 

가장 긴 증가하는 부분 수열 3 (백준 12738번)

 

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

 

import sys
input = sys.stdin.readline

n = int(input())
a = [0] + list(map(int, input().split()))

dp = [0 for _ in range(n + 1)]
b = [0 for _ in range(n + 1)]
idx = 0
maxl = 1
b[1] = a[1]
dp[1] = 1

def binarysearch(l, r, now):
    while l < r:
        mid = (l + r) // 2
        if b[mid] < now:
            l = mid + 1
        else:
            r = mid
    return l

for i in range(2, n + 1):
    if b[maxl] < a[i]:
        maxl += 1
        b[maxl] = a[i]
        dp[i] = maxl
    else:
        idx = binarysearch(1, maxl, a[i])
        b[idx] = a[i]
        dp[i] = idx

print(maxl)

두번째 문제와 동일하게 풀면 되었다. (정답)

 

---

 

가장 긴 증가하는 부분 수열 4 (백준 14002번)

 

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

 

import sys
input = sys.stdin.readline

n = int(input())
a = [0] + list(map(int, input().split()))

dp = [0 for _ in range(n + 1)]
maxa = 0

for i in range(1, n + 1):
    maxt = 0
    for j in range(i):
        if a[i] > a[j]:
            maxt = max(maxt, dp[j])
    dp[i] = maxt + 1
    maxa = max(maxa, dp[i])

idx = maxa
ans = [0 for _ in range(idx + 1)]
for i in range(n, 0, -1):
    if dp[i] == idx:
        ans[idx] = a[i]
        idx -= 1

print(maxa)
for i in range(1, maxa + 1):
    print(ans[i], end = ' ')

dp 배열과 점화식은 위와 동일하다. 그런데 이번에는 가장 긴 증가하는 부분 수열의 길이뿐만 아니라 해당 수열까지 출력을 해야 한다.

나머지 풀이(dp 정의, dp 채우기 등)는 동일한데 마지막에 dp 배열을 역순으로 하나씩 탐색하며 저장한 뒤 출력하면 된다. (정답)

 

---

 

가장 긴 증가하는 부분 수열 5 (백준 14003번)

 

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

 

import sys
input = sys.stdin.readline

n = int(input())
a = [0] + list(map(int, input().split()))

dp = [0 for _ in range(n + 1)]
b = [0 for _ in range(n + 1)]
idx = 0
maxl = 1
b[1] = a[1]
dp[1] = 1

def binarysearch(l, r, now):
    while l < r:
        mid = (l + r) // 2
        if b[mid] < now:
            l = mid + 1
        else:
            r = mid
    return l

for i in range(2, n + 1):
    if b[maxl] < a[i]:
        maxl += 1
        b[maxl] = a[i]
        dp[i] = maxl
    else:
        idx = binarysearch(1, maxl, a[i])
        b[idx] = a[i]
        dp[i] = idx

idx = maxl
ans = [0 for _ in range(idx + 1)]
for i in range(n, 0, -1):
    if dp[i] == idx:
        ans[idx] = a[i]
        idx -= 1

print(maxl)
for i in range(1, maxl + 1):
    print(ans[i], end = ' ')

세번째 문제와 네번째 문제를 합치기만 하면 된다. 

즉, dp 배열을 채울 때는 이분 탐색을 이용해서 채우고, 마지막에 출력할 때는 dp 배열을 거꾸로 탐색하며 정답 수열을 구하는 것이다. (정답)