/*
#include <stdio.h>
int main()
{
int n,i,j,arr[24]={};
scanf("%d", &n);
for (i=1;i<=n;i++)
{
scanf("%d", &j);
arr[j]++;
}
for (j=1;j<=23;j++)
{
printf("%d ", arr[j]);
}
return 0;
}
memoization : 배열을 메모하는 용도로 사용하기
arr[i] : i번째 입력된 데이터 (x)
arr[i] : i에 대한 정보를 메모하는 용도 (o)
ex) i가 입력된 횟수 , i가 들어온 적있는지?
후보가 1, 2, 3 번
한 학년에 100명
3 1 1 2 1 2 3 3 3 1 2 1 3 1 2 3 1 .....
arr[1] arr[2] arr[3]
3 2 1
--->
5
2 5 8 1 2
arr[1] 1
arr[2] 2
...
arr[5] 1
...
arr[8] 1
->> 1 2 2 5 8
*/
/*
#include <stdio.h>
int main()
{
int n,i,j,arr[100001]={},min,k;
scanf("%d", &n);
for (i=1;i<=n;i++)
{
scanf("%d", &k);
arr[k]++;
}
for (i=0;i<=100000;i++)
{
for (j=1;j<=arr[i];j++)
{
printf("%d ", i);
}
}
return 0;
}
binary search -> bs
이분탐색 (이진탐색) : 두개로 잘라서 탐색
정렬된 배열 에서만 가능하다!!
1 5 9
1 2 3 4 12 15 18 19 25
위 배열에서 19의 위치를 알려주세요 !
1번 ~ 9번에서 찾아주세요 !
가운데인 5번이랑 비교
6번 ~9번에서 찾아주세요!
가운데인 7번과 비교
8번~9번 에서 찾아주세요!
가운데인 8번과 비교 ---> 찾았음!!!!
//a[s] ~ a[e]에서 k값의 위치 리턴 (없다면 -1)
int bs(int s, int e, int k)
{
int m = (s+e)/2;
if( ) //못찾았다면!
{
return -1;
}
if( a[m] ==k )
{
return m;
}
else if( a[m] <k )
{
return bs( );
}
else
{
return bs( );
}
}
*/
/*
#include <stdio.h>
int arr[1000001]={};
int bs(int s,int e,int k)
{
int d;
d=(s+e)/2;
if (e<s)
{
return -1;
}
if (arr[d]==k)
{
return d;
}
else if(arr[d]>=k)
{
return bs(s,d-1,k);
}
else if (arr[d]<=k)
{
return bs(d+1,e,k);
}
}
int main()
{
int n,k,i;
scanf("%d %d", &n, &k);
for (i=1;i<=n;i++)
{
scanf("%d", &arr[i]);
}
printf("%d", bs(1,n,k));
return 0;
}
*/
/*
#include <stdio.h>
int arr[1000001]={};
int bs(int s,int e,int k)
{
int d;
d=(s+e)/2;
if (e<s)
{
return -1;
}
if (arr[d]==k)
{
return d;
}
else if(arr[d]>=k)
{
return bs(s,d-1,k);
}
else if (arr[d]<=k)
{
return bs(d+1,e,k);
}
}
int main()
{
int n,m,i,a;
scanf("%d", &n);
for (i=1;i<=n;i++)
{
scanf("%d", &arr[i]);
}
scanf("%d", &m);
for (i=1;i<=m;i++)
{
scanf("%d", &a);
printf("%d ",bs(1,n,a));
}
return 0;
}
*/
/*
#include <stdio.h>
int arr[1000001]={},i,n,k;
int bs(int s,int e,int k)
{
int d;
d=s;
if (e<s)
{
return e+1;
}
if (arr[d]==k)
{
return d;
}
else if(arr[d]>=k)
{
return bs(s,d-1,k);
}
else if (arr[d]<=k)
{
return bs(d+1,e,k);
}
}
int main()
{
scanf("%d %d", &n, &k);
for (i=1;i<=n;i++)
{
scanf("%d", &arr[i]);
}
printf("%d", bs(1,n,k));
return 0;
}
정렬이 안된 배열에서 어떤 값을 찾고싶어
1. 1번부터 n번까지 순서대로 본다.
2. 퀵정렬 + 이진탐색으로 찾는다.
*/
/*
#include <stdio.h>
#include <stdlib.h>
int a[50001]={};
int arr[50001]={};
int bs(int s,int e,int k)
{
int d;
d=(s+e)/2;
if (a[d]==k)
{
return d;
}
else if(a[d]>=k)
{
return bs(s,d-1,k);
}
else if (a[d]<=k)
{
return bs(d+1,e,k);
}
}
int c(int* pa, int* pb)
{
if (*pa > *pb)
{
return 1;
}
else if (*pa<*pb)
{
return -1;
}
else
{
return 0;
}
}
int main()
{
int n,i,tmp;
scanf("%d", &n);
for (i=1;i<=n;i++)
{
scanf("%d", &arr[i]);
a[i]=arr[i];
}
qsort(&arr[1],n,sizeof(int),c);
for (i=1;i<=n;i++)
{
tmp = a[i];
a[i] = arr[i];
arr[i]=tmp;
}
for (i=1;i<=n;i++)
{
printf("%d ",bs(1,n,arr[i])-1);
}
return 0;
}
nypc 접수신청 7.11목 ~
https://www.nypc.co.kr/main/main.do
nypc 기출문제풀이 코드업대신 biko
숙제 (
1. nypc 기출 문제 읽어보고 파악하기
2. nypc 기출 문제 원하는거 하나 풀어보기 )
*/