백준 14002 가장 긴 증가하는 부분 수열 4 Python 3

 

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

14002번: 가장 긴 증가하는 부분 수열 4

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ14002.py

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

import sys
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
dp = [1]*N
subset = [[num] for num in A]

for i in range(N):
    for j in range(0, i):
        if A[i] > A[j]:
            if dp[i] < dp[j] + 1:
                dp[i] = dp[j] + 1
                subset[i] = subset[j] + [A[i]]

max_i = 0
for i in range(N):
    if dp[max_i] < dp[i]: max_i = i
print(dp[max_i])
print(*subset[max_i])

---

풀이 과정

가장 긴 증가하는 부분 수열 LIS(Longest increasing Subsequence)을 구하는 문제이다.

이 문제를 처음 접해봐서 완전탐색으로 접근하다 보니 시간초과로 문제를 해결하지 못했다.

 

LIS를 구하는 방법은 대표적으로 완전탐색, DP, 이분탐색을 적용하는 3가지 방법이 있다.

 

1. 완전탐색 알고리즘

완전탐색은 이 문제를 푸는데 적용해보니 시간복잡도가 O(N^3)이다. 따라서 효율적이지 못한 방법이다.

import sys
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
dp = [[num] for num in A]
max = [0, []]
for i in range(N):
    for k in range(i+1, N):
        new_dp = [A[i]]
        for j in range(k, N):
            if A[j] > new_dp[-1]:
                new_dp.append(A[j])
        if max[0] < len(new_dp):
            max[0] = len(new_dp)
            max[1] = new_dp[:]

print(max[0])
for num in max[1]:
    print(num, end = ' ')

 

 

2. DP 알고리즘

DP 알고리즘을 활용하면 시간복잡도 O(N^2)으로 문제를 해결할 수 있다.

DP 배열의 인덱스는 수열 A의 인덱스로, DP[i] = i번째 수열까지의 LIS의 길이다.

따라서 2중 포문을 통해 메모이제이션을 활용하여 i번째 수열까지의 LIS를 갱신해나가며 문제를 풀 수 있다.

 

 

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

#dp[i] = i번째 수열까지의 LIS 길이, 초기값은 자기 자신을 최소로 갖기 때문에 1로 설정한다
dp = [1]*N

#subset[i] = i번째 수열까지의 LIS, 초기값은 자기 자신을 갖는다
subset = [[num] for num in A]

for i in range(N):
	#i번째 수열의 LIS를 찾기 위해 0~i-1의 dp와 subset을 탐색한다
    for j in range(0, i):
    	#i번째 수열 값이 j번째 수열 값보다 큰 경우, 
        if A[i] > A[j]:
        	#j번째 LIS에 i번째 수열을 추가한 LIS의 길이가 기존 i번째 수열의 LIS의 길이보다 크다면, i번째 LIS를 갱신한다
            if dp[i] < dp[j] + 1:
                dp[i] = dp[j] + 1
                subset[i] = subset[j] + [A[i]]

max_i = 0
for i in range(N):
    if dp[max_i] < dp[i]: max_i = i
print(dp[max_i])
print(*subset[max_i])
#시간복잡도 = O(N^2), 공간복잡도 = O(N^2)

 

 

3. 이분 탐색 알고리즘

• 참고 -> 2021.10.08 - [코테 노트/백준] - 백준 12015 가장 긴 증가하는 부분 수열 2 Python 3

백준 12015 가장 긴 증가하는 부분 수열 2 Python 3

---

오답노트

처음에는 완전 탐색으로 시작 인덱스를 하나씩 늘려가며 끝까지 탐색해서 가능한 증가 수열을 모두 구하는 식으로 문제를 풀었다.  

결과는 역시 시간초과가 났다.

시간복잡도가 O(N^3)이 소요되고 최대의 경우 N = 1,000이니 당연히 1초 안에 통과할 수 없다.

이번 오답을 계기로 LIS 알고리즘에 대해 공부할 수 있었다..!

 

import sys
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
dp = [[num] for num in A]
max = [0, []]
for i in range(N):
    for k in range(i+1, N):
        new_dp = [A[i]]
        for j in range(k, N):
            if A[j] > new_dp[-1]:
                new_dp.append(A[j])
        if max[0] < len(new_dp):
            max[0] = len(new_dp)
            max[1] = new_dp[:]

print(max[0])
for num in max[1]:
    print(num, end = ' ')