백준
1. 이분 탐색
참고1, 참고2
import sys
input = sys.stdin.readline
def lower_bound(start, end, num):
while start < end:
mid = (start + end) // 2
if tmp[mid] < num:
start = mid + 1
else:
end = mid
return end
n = int(input())
array = list(map(int, input().split()))
tmp = []
index = [[0,0] for _ in range(n)]
for i in range(len(array)):
num = array[i]
index[i][1] = num
if len(tmp) == 0:
tmp.append(num)
continue
if tmp[-1] < num:
index[i][0] = len(tmp)
tmp.append(num)
else:
idx = lower_bound(0, len(tmp)-1, num)
index[i][0] = idx
tmp[idx] = num
answer = []
idx = len(tmp) - 1
for i in range(len(index) - 1, -1, -1):
if idx == -1:
break
if idx == index[i][0]:
answer.append(index[i][1])
idx -= 1
print(len(tmp))
print(*answer[::-1])
import sys
from bisect import bisect_left
input = sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
q=[]
temp=[]
for x in a:
if not q or x > q[-1]:
q.append(x)
temp.append((len(q)-1, x))
else:
q[bisect_left(q, x)]=x
temp.append((bisect_left(q, x), x))
ans=[]
last_idx=len(q) - 1
for i in range(len(temp)-1, -1, -1):
if temp[i][0] == last_idx:
ans.append(temp[i][1])
last_idx-=1
print(len(ans))
print(*reversed(ans))
C++
#include <stdio.h>
#include <algorithm>
#include <memory.h>
#define PIV (1<<20)
#define INF 1000000005
using namespace std;
int tree[PIV * 2];
void update(int n, int v)
{
tree[n += PIV] = v;
while (n >>= 1)
tree[n] = max(tree[n], v);
}
int query(int n)
{
int l = PIV, r = n + PIV;
int ret = 0;
while (l <= r)
{
if (l & 1) ret = max(ret, tree[l++]);
if (!(r & 1)) ret = max(ret, tree[r--]);
l >>= 1, r >>= 1;
}
return ret;
}
int N, b[PIV], p[PIV], r[PIV];
struct st {
int n, th;
};
bool operator<(st a, st b)
{
if (a.n == b.n)
return a.th > b.th;
return a.n < b.n;
}
st a[PIV];
int main()
{
scanf("%d", &N);
for (int i = 0, n; i < N; i++)
scanf("%d", &n), a[i] = { n, i }, p[i] = n;
sort(a, a + N);
int ans = 0, retval;
for (int i = 0; i < N; i++)
{
int ret = query(a[i].th - 1);
retval = ret + 1;
update(a[i].th, retval);
b[a[i].th] = retval;
ans = max(ans, retval);
}
printf("%d\n", ans);
int cnt = ans, ret = INF;
for (int i = N - 1; i >= 0; i--)
if (b[i] == cnt && p[i] < ret)
r[--cnt] = p[i], ret = p[i];
for (int i = 0; i < ans; i++)
printf("%d ", r[i]);
printf("\n");
}