[PYTHON] 백준 11053 - 가장 긴 증가하는 부분 수열

성능 요약

메모리: 114488 KB, 시간: 128 ms

분류

다이나믹 프로그래밍

문제 설명

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

---

아이디어, 문제풀이

• 이분탐색 으로는 통과가 불가능한 문제
• dp 개념 이해를 위한 문제라고 생각된다.
• 기본적인 아이디어는, 각 원소마다 자기보다 앞쪽 원소들을 비교하며 그 값이 작을경우 앞쪽 dp배열중 가장 큰 count 값에 +1을 한뒤 저장하는것
• 위 아이디어를 코드 그대로 구현하면 정답이 된다.

---

TROUBLE SHOOTING

• 일단, 이 문제를 이분탐색으로 풀려고 시도했던 코드들을 첨부하고 싶다.

  #https://www.acmicpc.net/problem/11053
  #가장 긴 증가하는 부분 수열
  #11053
  
  import sys
  
  input = sys.stdin.readline 
  
  n = int(input())
  arr = list(map(int, input().split()))
  
  result = [1] * n
  for i in range(1, n):
      left, right = 0, i - 1
      while left <= right:
          mid = (left + right) // 2
          if arr[mid] < arr[i]:
              left = mid + 1
          else:
              right = mid - 1
      result[i] = max(result[j] for j in range(i) if arr[j] < arr[i]) + 1
  
  print(max(result))

  일단 이문제는, 이분탐색으로 해결할 수 있기는 하다. 실제로 시간복잡도도 nlogn < n^2 로 줄일수 있다. 문제는, dp를 활용하지 않으면 문제 자체에 접근하는 난이도가 기하급수 적으로 올라간다. 물론 구현할순 있겠지만, 나는 1시간 내에 생각해 내지 못했다. 그래서 결론은… 이 문제는 dp를 알아야 한다.
  

• dp에 관한 개념은 나중에 dp문제를 풀때에 더 자세하게 정리해서 업로드 할 예정이다. 이 문제를 풀이하기위한 간단한 키워드는 dp의 가장 큰 특징인 메모이제이션이다. 데이터를 캐싱하듯 메모해둔 뒤, 바로 꺼내서 사용한다! 정도로 알고 있으면, 이 문제를 해결할때 큰 어려움은 없었다.

• 다른 자료들을 찾아봤을땐 dp를 구현하는것에 그친 코드들이 많았지만, 나는… 무슨 오기가 생겼는지 이 dp를 활용해서 이분탐색까지 적용시켜보고 싶었다. 일단, 적용전의 코드도 함께 업로드 하겠다.

  #https://www.acmicpc.net/problem/11053
  #가장 긴 증가하는 부분 수열
  #11053
  
  n = int(input())
  n_list = list(map(int, input().split()))
  
  dp = [0] * n
  # print(dp)
  for i in range(n):
      for j in range(i):
          if n_list[i] > n_list[j] and dp[i] < dp[j]:
              dp[i] = dp[j]
      dp[i] += 1
  
      # print(dp)
  
  print(max(dp))

  이분탐색은 이 과정속에서, 순차탐색만 이분탐색으로 바꿔주면 된다.
  

---

코드

import sys

input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))

dp = [0] * n  # dp[i]는 i를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이
length = 0  # 현재까지 가장 긴 증가하는 부분 수열의 길이

for i in range(n):
    left, right = 0, length

    while left < right:
        mid = (left + right) // 2
        if dp[mid] < arr[i]:
            left = mid + 1
        else:
            right = mid

    dp[left] = arr[i]

    if left == length:
        length += 1

print(length)