//이분탐색 = 이진 탐색 = binary search
//-> 정렬이 되어있는 배열에서 특정 데이터의 위치 찾기
/*
ex) 1 ~100 수 -> 50
int arr[100]={};
int bs(int s, int e, int k){ // arr[s] ~arr[e]에서 k의 값의 위치 리턴if ( 못찾았을때 ) return -1;
int mid = (s+e)/2;
if(arr[mid]==k) return mid;
else if( k<arr[mid]) return bs(s,mid-1,k);
return bs(mid+1,e,k);
}
*/
/*
#include <stdio.h>
int arr[1000001];
int bs(int s, int e, int k){ // arr[s] ~arr[e]에서 k의 값의 위치 리턴
if(s>e) return -1;
int mid = (s+e)/2;
if(arr[mid]==k) return mid+1;
else if( k<arr[mid]) return bs(s,mid-1,k);
return bs(mid+1,e,k);
}
int main()
{
int n,i,a,b;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
scanf("%d",&a);
for(i=0;i<a;i++)
{
scanf("%d",&b);
printf("%d ",bs(0,n-1,b));
}
}*/
//3004 -> 퀵정렬+이진탐색 + ( 약간의아이디어 )
//2633 -> 이진탐색 변형 문제
/*
#include <stdio.h>
int arr[50001];
int compare(int*pa,int*pb){
if(*pa>*pb) return 1;
else if(*pa<*pb) return -1;
else return 0;
}
int bs(int s,int e,int k){
if(s>e) return -1;
int mid = (s+e)/2;
if(arr[mid]==k) return mid;
else if(arr[mid]>k) return bs(s,mid-1,k);
return bs(mid+1,e,k);
}
int main()
{
int arr1[50001],a,n,i,s=0;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&arr[i]);
arr1[i] =arr[i];
}
qsort(arr,n,sizeof(int),compare);
for(i=0;i<n;i++)
{
printf("%d ",bs(0,n-1,arr1[i]));
}
return 0;
}
*/
/*
#include <stdio.h>
int arr[100001],n;
int bs(int s, int e, int k){ // arr[s] ~arr[e]에서 k의 값의 위치 리턴
int mid = (s+e)/2;
if(s==e){
if(arr[s]>=k){
return s+1;
}
else{
return n+1;
}
}
if(s>e) return n+1;
if(arr[mid]>=k){
return bs(s,mid,k);
}
else
return bs(mid+1,e,k);
}
int main()
{
int k,i;
scanf("%d %d",&n,&k);
for(i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
printf("%d",bs(0,n-1,k));
}
*/
/*
// DFS 로 푼 코드
#include <stdio.h>
int map[101][101]={0};
int v[101]={0};
int a;
int cnt=0;
void dfs(int x)
{
v[x]=1; //방문해따 ~
// x 노드에서부터 다녀올수있는 곳을 모두 다녀오기
for(int i=1;i<=a;i++)
{
// node x와 node i가 연결o && 방문x
if(map[x][i]==1 && v[i]==0)
{
cnt++;
//printf("->%d",i);
dfs(i);
}
}
}
int main()
{
int b,c,d,i,j;
scanf("%d %d",&a,&b);
for(i=0;i<b;i++)
{
scanf("%d %d",&c,&d);
map[c][d] = 1;
map[d][c] = 1;
}
dfs(1);
printf("%d",cnt);
}
*/
/*
for(i=0;i<=a;i++)
{
for(j=0;j<=a;j++)
{
printf("%d",map[i][j]);
}
printf("\n");
}
return 0;
}
*/
/*
#include <stdio.h>
int arr[27][27]={};
int n;
void dfs(int i, int j)
{
arr[i][j]=0; // 방문햇따!
//arr[i][j]의 상하좌우에서 갈수 있는 곳 모두 가기
if(arr[i-1][j]==1){
dfs(i-1,j);
}
if(arr[i+1][j]==1){
dfs(i+1,j);
}
if(arr[i][j+1]==1){
dfs(i,j+1);
}
if(arr[i][j-1]==1){
dfs(i,j-1);
}
}
int main()
{
int i,j;
int cnt=0;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf("%1d",&arr[i][j]);
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(arr[i][j]==1)
{
dfs(i,j);
// printf("%d %d\n",i,j);
cnt++;
}
}
}
printf("%d",cnt);
}
캔디팡 -> 단지+a
호수의수 -> 단지 ( 문자, 8방향 연결)
*/