문제 https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 풀이 파라메트릭 서치를 활용한 풀이 그리디한 접근법 A[i][j]값을 1차원 배열에 기록 후 오름차순 정렬을 통해 원하는 값 B[K]를 구하는 방식 해당 방식으로 풀이하게 될 경우 N^2만큼의 메모리가 필요할 뿐더러 시간 또한 O(N^2)만큼 걸리기 때문에 AC를 받을 수 없음 LowerBound 접근 위의 방식에서 이분탐색을 추가해서 탐색 시간을 줄여야하는데 ..

Concept 기존 dp 메모이제이션을 활용한 LIS에서 시간복잡도를 줄이기 위해 이분탐색을 활용 기존 LIS에서 앞쪽 수열을 보고 큰 값을 찾고 값을 갱신하는데 드는 시간인 O(N)을 줄일 수 없을까에서 비롯된 방식 사전지식으로 LowerBound 이분탐색에 대한 이해와 O(N^2)방식의 이해가 요구. Feature 시간복잡도의 경우 모든 원소를 탐색하는 시간 O(N)에 대해 이분탐색 O(NlogN)을 수행함으로 총 O(N * NlogN)이므로 O(NlogN)의 시간으로 최장 증가 수열을 구할 수 있음. Implement 1. 각각의 원소 i에 대해서 현재 기록된 lis배열의 끝 인덱스와 비교하여 i가 더 크다면 뒤에 추가 2. i가 더 작을 경우 이분탐색을 통해 해당 원소가 들어갈 수 있는 자리를 탐..