소스코드
이분탐색
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
복사
사실 아직 이 코드의 반례를 잘 모르겠습니다. 지피티한테 물어봐도 못 알려주네요. 그렇지만 어찌됐든 틀렸다고 나오는 코드입니다.