반응형
https://www.acmicpc.net/problem/12015
12015번: 가장 긴 증가하는 부분 수열 2
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)
www.acmicpc.net
수열의 크기가 백만 단위라서 N^2 의 DP로는 문제로 풀 수 없다.
Binary Search를 활용해서 O(NlogN)으로 풀어낼 수 있다.
자세한 풀이는
최적화된 LIS(Longest Increasing Subsequence) 알고리즘과 해 찾기
LIS는 알고리즘 문제로써도, 코드 구현으로써도 너무나도 유명한 문제이지만 최적화된 해법을 찾는 과정은 문제 해결능력에 있어 큰 도움을 준다. 개인적으로 매력있게 느끼는점은 인간이 직관�
jins-dev.tistory.com
에서 확인할 수 있다.
반응형
'프로그래밍 > 코딩테스트 문제풀이' 카테고리의 다른 글
| [Python] 백준 16918. 봄버맨 (0) | 2020.07.20 |
|---|---|
| [Python] SWExpertAcademy. 수영장 (0) | 2020.07.15 |
| [Python] 백준 2644. 촌수계산 (0) | 2020.07.13 |
| [Python] 백준 5014. 스타트링크 (0) | 2020.07.09 |
| [Python] 백준 1244. 스위치 켜고 끄기 (0) | 2020.07.08 |