/*
#include <stdio.h>
typedef struct
{
int nu;
int ma;
int inf;
} student;
int main()
{
int n,i,j;
student arr[1000],temp;
scanf("%d",&n);
for(i=1; i<=n; i++)
{
scanf("%d %d",&arr[i].ma,&arr[i].inf);
arr[i].nu=i;
}
for(i=1; i<n; i++)
{
for(j=1; j<=n-i; j++)
{
if (arr[j].ma < arr[j+1].ma)
{
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
else if (arr[j].ma == arr[j+1].ma)
{
if(arr[j].inf < arr[j+1].inf)
{
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
else if(arr[j].inf == arr[j+1].inf)
{
if(arr[j].nu > arr[j+1].nu)
{
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
for(i=1; i<=n; i++)
{
printf("%d %d %d\n",arr[i].nu,arr[i].ma,arr[i].inf);
}
return 0;
}
*/
/*
#include <stdio.h>
int a[10001];
int n, i, j, temp, key;
int main() {
scanf("%d", &n);
for (i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (i=2; i<=n; i++)
{
key=a[i];
for(j=i-1;j>0&& a[j]<key;j--)
{
a[j+1]=a[j];
}
a[j+1]=key;
}
for (i=1; i<=n; i++)
printf("%d ", a[i]);
return 0;
}
*/
/*
#include <stdio.h>
int a[10001];
int n, i, j, temp;
int main() {
n=3;
for (i=1; i<=n; i++)
scanf("%d", &a[i]);
for(i=1; i<n; i++)
{
for(j=0;j<=n-i;j++)
{
if (a[j] > a[j+1])
{
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
for (i = 1; i <= n; i++)
printf("%d ", a[i]);
return 0;
}
*/
/*
#include <stdio.h>
//quick_sort
int a[100000];
void qs(int s, int e) // arr[s] ~ arr[e]를 퀵정렬 하라
{
int p = s; //맨 처음 값을 기준으로 잡는다
int low=s, high=e+1,temp;
do
{
do{
low++;
} while(a[p]>a[low]);
do{
high--;
} while(a[p]<a[high]);
if(low<high)
{
temp=a[low];
a[low]=a[high];
a[high]=temp;
}
} while(low<high);
temp=a[p];
a[p]=a[high];
a[high]=temp;
if(s<high-1)
qs(s,high-1);
if(high+1<e)
qs(high+1,e);
}
int main()
{
int n,i;
scanf("%d",&n);
for(i=0; i<n; i++)
scanf("%d",&a[i]);
qs(0,n-1);
for(i=0; i<n; i++)
printf("%d\n",a[i]);
}
이진탐색 이분탐색 binary search
정렬되어있는 배열에서 반씩 쪼개면서 탐색 (재귀)
int a[100];
int bs(int s, int e, int k) // a[s] ~ a[e]에서 k의 위치를 리턴 없으면 -1리턴
{
int mid=(s+e)/2;
if(s>e) return -1;
if(a[mid]==k) return mid; //찾음
else if(a[mid]<k) bs(mid+1,e,k);
else bs(s,mid-1,k);
}
정렬 1635
이진탐색 3002
이진탐색 변형 2633
3004 퀵정렬+이진탐색
*/
/*
#include <stdio.h>
int a[1000000];
int bs(int s, int e, int k) // a[s] ~ a[e]에서 k의 위치를 리턴 없으면 -1리턴
{
int mid=(s+e)/2;
if(s>e) return -1;
if(a[mid]==k) return mid+1; //찾음
else if(a[mid]<k) bs(mid+1,e,k);
else bs(s,mid-1,k);
}
int main()
{
int n,m,i,t;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
scanf("%d",&m);
for(i=0;i<m;i++)
{
scanf("%d",&t);
printf("%d ",bs(0,n-1,t));
}
}
*/