정리충의 정리노트

0. 문제 주소 https://www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주어진다. 이 수들은 1 이상 n 이하이며 서로 같은 수는 없다고 가정하자. www.acmicpc.net 1. 풀이 교점이 생기면 안 된단다. 그냥 LIS 문제다. LIS 풀이는 여러가지가 있지만, 이 문제에선 N 제한이 40000이므로 dp, 즉 O(N^2)로는 풀 수 없다. lower_bound를 사용하면 O(n log n)으로 쉽게 풀 수 있다. 먼저 빈 배열 d를 설정해두고, 기존 배열..