처음에 문제에 대해 요구사항이 무엇인지 파악하기 힘들었다.
간단하게 생각하면 처음 숫자부터 오름차순으로 가장 길게 나열할 수 있는 수열을 찾는 줄 알았다.
하지만 주어진 수열안에서 처음 숫자가 시작점이 아니더라도 가장 길게 오름차순으로 나열할 수 있는 수열이 존재한다.
예를 들자면
수열 A = [40, 10, 30, 20, 50, 60] 일때
➡️ [40, 10, 30, 20, 50, 60]
그러므로 각 지점까지 최장 오름차순 수열 개수를 저장해놓고 마지막까지 비교하며 업데이트하는 동적 계획법을 생각해볼 수 있었다.
동적계획법 풀이
n = int(input())
num_list = list(map(int,input().split()))
dp = [1 for _ in range(n)]
for i in range(1,n): # 현재 비교할 값
for j in range(i): # i 이전까지 비교할 값
if num_list[j] < num_list[i] and dp[i] < dp[j]+1:
dp[i] = dp[j]+1
print(max(dp))코드 설명
- dp: 각 지점까지 최장 오름차순 수열 개수
- 자기 자신을 포함하고 시작하므로 1로 초기화- 조건문: 수열 A에서 이전값보다 현재값이 클 경우와 이전까지 저장해놓은 최장 오름차순 수열 개수 + 1이 현재까지 저장해놓은 값보다 클 경우
동적계획법을 사용하면 시간복잡도가 O(n^2)이다.
주어진 수열 A의 최대 길이는 1000으로 시간제한 1초를 통과할 수 있는 코드이긴하다.
만약 수열 A를 탐색하면서 최장 오름차순 수열이 될 수 있는 값들만 찾는 알고리즘을 사용하여 수열을 만들면 시간복잡도를 줄일 수 있을것이다.
이분탐색 풀이
n = int(input())
num_list = list(map(int,input().split()))
bin_arr = [num_list[0]]
def binary_search(arr,value): # 이분 탐색
left, right = 0, len(arr)-1
while left < right:
mid = (left + right) // 2
if arr[mid] < value:
left = mid+1
else:
right = mid
return left
for i in range(1,n):
now = num_list[i]
if bin_arr[-1] < now:
bin_arr.append(now)
else:
index = binary_search(bin_arr,now)
bin_arr[index] = now
print(len(bin_arr))코드 설명
- bin_arr: 최장 오름차순 수열을 저장하는 배열
- 조건문: bin_arr에서 가장 큰 수보다 큰 값이면 값 추가
아니면 해당 값이 bin_arr에서의 위치(인덱스) 업데이트
이분 탐색 알고리즘을 사용해서 최장 오름차순 수열을 업데이트 해 나가면 시간복잡도 O(nlogn)으로 해결 가능하다.
두 풀이의 시간복잡도 차이는 112ms > 44ms로 후자가 더 빠르다.
