문제 풀이 이분 탐색을 사용한다. 가장 긴 증가하는 부분 수열을 찾는 문제이다. 내가 알던 방법은 O(N * N)으로 전체 계산 수가 16억이 되어 시간 초과가 발생한다. 입력이 들어오면서 검사를 실시한다. 입력값이 현재 수열의 가장 끝에 있는 수를 초과한 경우 바로 수열에 추가된다. 이하일 경우엔 이분 탐색을 실시한다. 현재 수열에서 입력값 이하의 값 중, 최댓값을 입력값으로 교체한다. 이렇게 하면 시간 복잡도가 O(N * logN)으로 줄어든다. 코드 #include #include #include using namespace std; vector nums; // 기존에 입력된 nums에서 num 이하의 값중에서 // 최댓값을 num으로 교체한다. void binary_input(int num) { ..
