회고
입력이 무려 백만!! 헐헐헐 1,000,000!!
기존 O(n²) 알고리즘으로는 불가능 하다.
텅 빈 수열에서 시작해 숫자를 하나씩 추가해 나가며 각 길이를 갖는 증가 수열 중 가장 마지막 수가 작은 것은 무엇인지를 추적한다.
즉, dp[i] = 지금까지 만든 부분 배열이 갖는 길이 i 인 증가 부분 수열 중 최소의 마지막 값.
이분검색을 하는 과정이 필요하므로, O(nlgn) 으로 가능
풀이
문제
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)
출력
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
예제 입력 1
6 10 20 10 30 20 50
예제 출력 1
4
소스
'스터디 > 알고리즘 문제풀이' 카테고리의 다른 글
| [이러닝] 숫자만들기 (1) | 2019.01.20 |
|---|---|
| [백준 2157][DP] 여행 (0) | 2018.12.04 |
| [백준 11055] 가장 큰 증가하는 부분 수열 (0) | 2018.12.03 |
| [백준 11053] 가장 긴 증가하는 부분 수열 (LIS) (0) | 2018.12.03 |
| [백준 1600] 말이 되고픈 원숭이 (0) | 2018.11.26 |
