작심 24/7

#include using namespace std; int arr[8] = {1, 2, 4, 5, 10, 21, 21, 22}; int binarySearch(int st, int en, int target) { // target 찾음 while (st

14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net O(NlogN) LIS 알고리즘으로 풀어야 하는 문제이다. arr 배열엔 입력 값을 저장한다. tmp 배열의 인덱스는 수열의 길이를 나타내고 각 값은 현재 길이를 가진 수열의 마지막 원소 중 가장 작은 값의 위치를 저장한다. dp 배열엔 각 인덱스가 연결하고 있는 인덱스를 저장한다. 변수 len엔 지금까지 가장 긴 수열의 길이를 저장한다. 계산이 모두 끝나면 tmp[len]이 LIS의 마지막 원소의 위치를 가리키고 있으므로 dp[tm..