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

📌 알고리즘 분류

---

해당 문제는 최장 증가 부분 수열(LIS)에 대한 이해가 필요한 문제입니다.
해당 문제는 이분 탐색 대한 이해가 필요한 문제입니다.
최장 증가 부분 수열
이분 탐색

📖 문제

---

백준 12015

💻 코드

---

수열이 입력으로 주어졌을 때, 증가하는 부분 수열 중 길이가 가장 긴 부분 수열을 찾는 문제입니다. 수열의 전체 크기가 10만으로 주어지기 때문에 이중 반복문으로 풀게 되면, 시간 복잡도가 O(N^2)이 되어 시간안에 해결할 수 없습니다. 따라서 이분 탐색 알고리즘을 추가로 사용해야 합니다. 이분 탐색을 직접 구현하지 않고, c++의 stl lower_bound를 이용하여, 수열의 새로 등장하는 원소가 DP에 마지막 저장된 부분보다 작다면, 찾아서 교체하는 방식으로 구현했습니다. 자세한 부분은 알고리즘 분류에서 알고리즘을 추가로 보면 되겠습니다.

📌 마무리

---

두 가지 알고리즘이 사용되었기 때문에, 까다로운 문제입니다. LIS 문제 중 등장할 수 있는 문제라 알아두면 좋겠습니다.