/*
#include <stdio.h>
typedef struct
{
int a;
int b;
int c;
}myint;
int main()
{
int i,j,n;
myint temp;
myint arr[1001];
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d %d",&arr[i].b,&arr[i].c);
arr[i].a=i;
}
for(i=1;i<n;i++)
{
for(j=1;j<=n-i;j++)
{
if(arr[j].b<arr[j+1].b)
{
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
else if(arr[j].b==arr[j+1].b)
{
if(arr[j].c>arr[j+1].c)
{
continue;
}
else if(arr[j].c<arr[j+1].c)
{
temp=arr[j+1];
arr[j+1]=arr[j];
arr[j]=temp;
}
}
}
}
for(i=1;i<=n;i++)
{
printf("%d %d %d\n",arr[i].a,arr[i].b,arr[i].c);
}
return 0;
}
*/
/*
#include <stdio.h>
#include <string.h>
typedef struct
{
int b,c,d;
char a[100];
}myint;
int main()
{
int i,j,n;
myint temp;
myint arr[101];
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%s %d %d %d",&arr[i].a,&arr[i].b,&arr[i].c,&arr[i].d);
}
for(i=1;i<=n;i++)
{
for(j=1;j<=n-i;j++)
{
if(arr[j].b>arr[j+1].b)
{
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
else if(arr[j].b==arr[j+1].b)
{
if(arr[j].c==arr[j+1].c)
{
if(arr[j].d<arr[j+1].d)
{
continue;
}
else if(arr[j].d>arr[j+1].d)
{
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
else if(arr[j].d==arr[j+1].d)
{
if(strcmp(arr[j].a,arr[j+1].a)>0)
{
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
else if(arr[j].c<arr[j+1].c)
{
continue;
}
else if(arr[j].c>arr[j+1].c)
{
temp=arr[j+1];
arr[j+1]=arr[j];
arr[j]=temp;
}
}
}
}
for(i=1;i<=n;i++)
{
printf("%s\n",arr[i].a);
}
}
5 1 4 2 3
round1. a[1]에 와야하는 값 선택해서 교환 ( 최소값이 있는 자리를 찾기)
1 // 5 4 2 3
round2. a[2]에 와야 하는 값 선택해서 교환
1 2 // 4 5 3
round3.
1 2 3 // 5 4
round4.
1 2 3 4 // 5 -> end
*/
/*
#include <stdio.h>
int a[10001];
int n, i, j, temp, min;
int main() {
scanf("%d", &n);
for (i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (i=1; i<n; i++) {
min=i;
for (j=i+1; j<=n; j++)
{
if(a[j]<a[min])
{
min=j;
}
}
temp = a[i];
a[i] = a[min];
a[min] = temp;
}
for (i=1; i<=n; i++)
printf("%d\n", a[i]);
return 0;
}
*/
/*
#include <stdio.h>
int a[101];
int i,j,n,temp,max;
int main()
{
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(i=1;i<n;i++)
{
max=i;
for(j=i+1;j<=n;j++)
{
if(a[j]>a[max])
{
max=j;
}
}
temp=a[i];
a[i]=a[max];
a[max]=temp;
}
for(i=1;i<=n;i++)
{
printf("%d ",a[i]);
}
return 0;
}
탐색 : 어떤 데이터셋에 내가 찾는 데이터가 있는지? 찾아보는것
방 50개
1. 순차탐색 1번방 2번방 3번방 .... 50번방
2. 이진탐색(이분탐색)-- ( 정렬이 되어있을 때만!!!)
1 ~50 사이의 수 1번 확인 -> 25개 -> 12 -> 6 -> 3 -> 1
start end
1 .......................n
k=3
1 3 5 7 9 10 11 13 15
1 2 3 4 5 6 7 8 9
#include <stdio.h>
int a[101];
int i,j,n,temp,max;
int bs(int start, int end, int k)
// a[start] ~ a[end] 에서 "k값의 위치" 리턴
{
if(a[end]<k) return -1; // 없으면
int mid = (start+end)/2;
if(a[mid]==k) return mid;
else if(k < a[mid]) return bs(start,mid-1,k);
else return bs(mid+1,end,k);
}
int main()
{
int k;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
scanf("%d",&k);
printf("%d",bs(1,n,k));
}
*/
/*
#include <stdio.h>
int a[1000005]={};
int b[100001]={};
int main()
{
int i,j,n;
}
*/