문제 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 풀이 이 문제는 '11053번 가장 긴 증가하는 수열' 문제와 유사하지만 입력 범위가 크기 때문에 DP로 풀이하면 시간초과가 발생한다. 대신 LIS를 구하는 다른 방법인 이분 탐색을 활용해 풀이해야한다. 우선 입력 받은 수열을 가장 긴 증가하는 수열로 만드는 방법을 확인해보자. 어느 수열의 첫 5개의 원소가 [30, 35, 40, 10, 20, ...]일 때 현재까지의 LIS는 [30, 35, 40]이 될 것이다. 여기서 이 LIS는 수열의 다음 원소들에 따..

문제 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 풀이 이 문제를 풀이하기 위해 이분 탐색(Binary Search) 알고리즘이 필요하다. 이분 탐색이란 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간값을 선택하고, 찾고자하는 값과 비교해서 중간값이 더 크다면 그 중간값이 새로운 최댓값이 되고, 더 작다면 최솟값이 된다. 그리고 다시 새로운 중간값을 찾고, 찾고자하는 값과 비교해나가는 것이다. 풀이한 코드에서는 binarySe..