소스코드

이분탐색

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))

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))

풀이

이분탐색

• 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)
  

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