01.cpp - 회전초밥
*제가 짠 소스가 아닙니다*
/*
#include <stdio.h>
#define MAX_DISH 3000001
#define MAX_FISH 3001
int dishes[MAX_DISH];
int hash[MAX_FISH];
int head_idx = 0, tail_idx = 0;
int safe_increment(const unsigned int index, const unsigned int dish){
//dishes에 필요한 인덱스가 범위를 넘어가지 않도록 한다
return (index + 1) % dish;
}
int enqueue(const unsigned int current_num, const unsigned int dish){
const unsigned int ret =
(++hash[dishes[head_idx]] == 1) ? (current_num + 1) : (current_num);
head_idx = safe_increment(head_idx, dish);
return ret;
}
int dequeue(const unsigned int current_num, const unsigned int dish){
const unsigned int ret =
(--hash[dishes[tail_idx]] == 0) ? (current_num - 1) : (current_num);
tail_idx = safe_increment(tail_idx, dish);
return ret;
}
int main(){
int n_dish, n_fish, k, coupon;
int i, max = 1; //1은 최초에 쿠폰으로 1개 먹기 때문
int enq = 0;
scanf("%d %d %d %d", &n_dish, &n_fish, &k, &coupon);
for(i = 0; i < n_dish; ++i){
scanf("%d", &dishes[i]);
}
hash[coupon]++;
for(i = 0; i < k; ++i){
enq = enqueue(max, n_dish);
max = (enq > max) ? enq : max ;
}
for(i = 0; i < n_dish - 1; ++i){
int j;
enq = enqueue(dequeue(enq, n_dish), n_dish);
max = (enq > max) ? enq : max;
}
printf("%d", max);
}
*/
02.cpp - binary search. 이진탐색
//binary search
#include <stdio.h>
#include <algorithm>
using namespace std;
int first, last;
int arr[100001];
int original[100001];
int want_to_find;
int N;
int binary_search(){
if(last<first) return -1;
int middle=(last+first+1)/2;
if(want_to_find==arr[middle]) return middle;
else if(want_to_find<arr[middle]) last=middle-
1;
else first=middle+1;
return binary_search();
}
int main(){
scanf("%d", &N);
last=N;
int cnt=1;
for(int i=1; i<=N; ++i){
scanf("%d", &arr[i]);
original[arr[i]]=cnt++;
}
puts("want to find(it need not to be sorted)");
scanf("%d", &want_to_find);
sort(arr, arr+N);
printf("that's on %d index(starts from zero)", original[binary_search()]);
}
이진탐색입니다. 항상 정렬된 배열 기준으로 first부터 last까지의 값 중 중간값((first+last+1)/2)을 구해서 그 값이 want_to_find와 같으면 그 인덱스를 리턴, 그 중간값이 want_to_find보다 작으면 first를 중간값+1로 옮기고 그 반대면 last를 중간값-1로 옮긴 후 재귀 돌립니다.
숫자 맞추기 게임(up&down게임)의 공략이기도 한 이진탐색입니다.
선생님 : 숫자 1부터 100까지 중 내가 뭘생각하고있게? 숫자 말하면 그 숫자가 내가 생각한 숫자보다 높은지 낮은지만 알려줄게!
총 7번만 말하면 찾을 수 있겠죠
03.cpp - Lis algorithm <ver.1 : find temp's length>
//longest increasing subsequence
//ver.1
#include <stdio.h>
int arr[100000];
int temp[100000];
int t_last=0;
int first=0, last;
int N;
int upgraded_b_search(int target, int range_f, int range_l){
if(range_f==range_l) return range_l;
else if(range_f+1==range_l){
return range_l;
}
int middle=(first+last+1)/2;
if(temp[middle]==target) return middle;
else if(temp[middle]>target){
range_l=middle;
last=middle-1;
}
else{
range_f=middle;
first=middle+1;
}
return upgraded_b_search(target, range_f, range_l);
}
void find_Lis_length(){
for(int i=1; i<N; ++i){
first=0;
last=t_last;
if(arr[i]>temp[t_last]){
temp[++t_last]=arr[i];
//printf("okay\n");
}
else{
//printf("b_search : ");
int d=upgraded_b_search(arr[i], 0, t_last);
//printf("upgraded_b_search(arr[i], 0, t_last) : %d\n",d);
temp[d]=arr[i];
}
//for(int i=0; i<t_last; ++i){
// printf("%d ", temp[i]);
//}
//printf("\n");
}
return;
}
int main(){
scanf("%d", &N);
for(int i=0; i<N; ++i){
scanf("%d", &arr[i]);
}
temp[0]=arr[0];
find_Lis_length();
printf("\n");
for(int i=0; i<t_last+1; ++i){
printf("%d ", temp[i]);
}
printf("\n");
printf("length : %d", t_last+1);//index starts from zero. so +1.
}
LIS알고리즘 중 binary-search를 이용해서 temp의 길이를 구하는 코드입니다.
원래는 lower-bound를 이용해서 푸는게 정석이지만 lower-bound까지 구현하고 싶어서 이렇게 짜봤습니다.
우선 결론 : lower-bound씁시다
그럼 이제 설명하겠습니다.
<temp배열을 만드는 방법>
1. 준비물 : arr배열, binary-search 함수 등등
2. 로직을 설명드리겠습니다.
(1) temp[0]에 arr[0]을 대입합니다.
(2) arr[1]부터 arr[n]까지 temp의 가장 마지막 숫자와 비교합니다.
arr[i]가 temp[last]보다 크면 ++last에 arr[i]를 대입합니다.
그 반대면 temp에서 arr[i]보다 큰 최소의 수를 binaray search(이진탐색)을 이용해서 찾습니다. 그리고 그 수에 arr[i]를 대입합니다. 이때 last는 변하지 않습니다.
(3) 배열의 길이는 last+1입니다. (배열이 0부터 시작하기 때문에)
LIS에 대한 자세한 설명은 다음시간에 하겠습니다.