😵‍💫

가장 긴 증가하는 부분 수열

www.acmicpc.net

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

소스코드

이분탐색

import sys
input = sys.stdin.readline

N = int(input().strip())
A = list(map(int, input().strip().split()))

def binary_search(list, target):
    start = 0
    end = len(list)

    while start < end:
        mid = (start + end) // 2

        if list[mid] < target:
            start = mid + 1
        else:
            end = mid

    return start # 삽입할 인덱스

def solve(A):
    list = []
    
    for value in A:
        index = binary_search(list, value)
        if index == len(list):
            list.append(value)
        else:
            list[index] = value

    return len(list)

print(solve(A))

Python

복사

DP

import sys
input = sys.stdin.readline

N = int(input().strip())
A = list(map(int, input().strip().split()))

lengths = [1] * N # DP 테이블 : A[i]를 마지막 원소로 하는 가장 긴 증가하는 부분 수열의 최대길이
for i in range(N):
	for j in range(i):
		if A[j] < A[i]:
			lengths[i] = max(lengths[i], lengths[j] + 1)

print(max(lengths))

Python

복사

풀이

이분탐색

•

A의 원소를 리스트의 적절한 위치에 삽입해주면 됩니다.

•

이때 삽입할 위치를 찾기 위해 이분탐색을 사용합니다.

•

이분탐색을 거쳐 삽입할 위치의 인덱스를 찾아내고, 해당 인덱스의 값을 A의 원소로 만들어주면 됩니다. 물론 매번 이분탐색을 할 필요는 없고 부분수열의 마지막 값보다 크면 곧바로 삽입하면 됩니다(매번 이분탐색을 해도 됨)

DP

•

N의 사이즈는 최대 1000입니다. 이 말은, 1초 제한시간 동안에 이중반복문을 통해 O(N^2)의 시간복잡도를 가져도 시간초과가 되지 않는다는 소리입니다.

•

그러나 단순히 이중반복을 통해 제일 큰 값을 갱신해가며 카운트를 하면 안되더라구요 :

import sys
input = sys.stdin.readline

N = int(input().strip())
A = list(map(int, input().strip().split()))
result = 0 # 가장 긴 증가하는 부분 수열의 길이

for i in range(N):
	num = A[i]
	temp_result = 1
	
	for j in range(i+1, N):
		if num < A[j]:
			num = A[j]
			temp_result += 1
	
	result = max(result, temp_result)

print(result)

Python

복사

사실 아직 이 코드의 반례를 잘 모르겠습니다. 지피티한테 물어봐도 못 알려주네요. 그렇지만 어찌됐든 틀렸다고 나오는 코드입니다.