08. 8차시 수업

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에 대한 자세한 설명은 다음시간에 하겠습니다.