티스토리 뷰
문제
알고리즘
LIS, 이분 탐색
풀이
N일 동안의 주가가 주어졌을 때, K일 동안 첫날을 제외하고 직전 날 산 주가보다 비싸게 구매할 수 있는지를 묻고 있습니다.
유명한 Longest Increasing Subsequence 문제입니다. 다이나믹 프로그래밍으로 O(N2)에 해결 가능합니다. 하지만 주어지는 테스트케이스가 100개에 N제한이 1만이므로 해당 알고리즘을 사용하면 시간 초과가 발생합니다.
처음에 정렬된 배열을 하나 갖고 시작합니다. 처음이므로 정렬된 빈 배열을 갖고 있습니다. N개의 값을 순차적으로 보며 해당 값을 정렬된 배열 어디에 위치한지 찾습니다. 정렬된 배열에서 위치를 찾는 것이므로 이분 탐색으로 찾을 수 있습니다. 위치를 찾았다면 해당 위치를 업데이트 하고 만약 배열의 길이와 해당 인덱스가 같다면 len을 증가시켜줍니다. 이는 정렬된 배열에서 맨 뒤에 값을 넣는 것과 동일합니다. 만들어진 배열의 길이는 O(NlogN)에 찾을 수 있는 LIS의 길이입니다. 정렬된 배열 안에는 실제 LIS값과는 다른 값이 들어있습니다.
이분탐색으로 정렬된 배열을 업데이트 해주는 행동은 여러 subsequence들을 관리하는 것과 비슷합니다.
배열 [1,5,10,2,4,7]이 주어졌을 때 정렬된 배열의 변화는 다음과 같습니다.
[1]
[1,5]
[1,5,10]
[1,2,10]
[1,2,4]
[1,2,4,7]
정렬된 배열의 상태가 [1,2,10] 일때 우리가 갖고 관리하는 subsequence들 중 정답 후보가 될 수 있는 것은 [1,5,10] 와 [1,2] 입니다. [1,2,10]으로 나타내어도 우리가 원하는 LIS의 길이를 구하는 것에는 전혀 지장이 없습니다.
코드
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,n) for(int i=1;i<=n;++i)
#define FAST cin.tie(NULL);cout.tie(NULL); ios::sync_with_stdio(false)
using namespace std;
int tc,n,k;
int arr[10000];
int main() {
FAST;
cin >> tc;
REP(CASE,tc) {
cin >> n >> k;
memset(arr, 0, sizeof(arr));
int len = 0;
rep(i, n) {
int val;
cin >> val;
int pos = lower_bound(arr, arr + len, val) - arr;
arr[pos] = val;
if (len == pos) ++len;
}
cout << "Case #" << CASE << '\n';
cout << (len >= k) << '\n';
}
return 0;
}
'Algorithm' 카테고리의 다른 글
[백준 1517] 버블 소트 (0) | 2020.10.10 |
---|---|
[백준 3584] 가장 가까운 공통 조상 (0) | 2020.10.08 |
[백준 10573] 증가하는 수 (0) | 2020.09.30 |
[백준 17365] 별다줄 (0) | 2020.09.29 |
[백준 17291] 새끼치기 (0) | 2020.09.28 |
- Total
- Today
- Yesterday
- Segment tree
- 정렬
- 이분탐색
- 세그먼트트리
- dfs
- Fenwick
- spring
- sweeping
- dijkstra
- Suffix Array
- SCC
- 펜윅트리
- spring boot
- sorting
- implementation
- string
- 좌표압축
- 트라이
- hld
- 동적계획법
- DP
- greedy
- 2-SAT
- 스위핑
- union find
- knapsack
- 이분매칭
- kmp
- bfs
- Oracle
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |