[PS] 백준 14003 - 가장 긴 증가하는 부분 수열 5

📌 알고리즘 분류

---

해당 문제는 LIS( 가장 긴 증가하는 부분 수열 )에 대한 이해가 필요한 문제입니다.
LIS 알고리즘

📖 문제

---

백준 14003

문제의 입력을 보면 수열 A의 크기가 최대 10만으로 정해져 있습니다. 이 경우에 N^2 알고리즘을 작성하게 되면 10만 * 10만 = 100억이 되어서 시간을 초과하게 될 것 입니다. 따라서 최소한 nlogn 정도의 성능을 갖는 알고리즘을 사용해야 합니다. DP을 활용하여 LIS를 구현하게 되면 N^2의 성능을 갖게 되고, 세그먼트 트리 혹은 Lower_bound을 활용하여 LIS를 구현해야 합니다.

💻 코드

---

코드에서는 2중 for문이 아닌 반복문 하나만을 사용하여 수열 전체를 탐색합니다. 그 안에서 C++ STL에서 제공하는 lower_bound 함수를 이용하여, 최장 증가 부분 수열을 업데이트를 진행합니다. 해당 글에서는 lower_bound의 동작 방법은 자세하게 설명하지 않기 때문에 별도의 레퍼런스를 참고하길 바랍니다.

📌 마무리

---