/*
#include<stdio.h>
int a[26][26]= {};
int k, num=0;
int dx,dy;
int queue[2][10000]={};
int f=-1,r=-1;
void enq(int x, int y)
{
a[x][y]=0;
r++;
queue[0][r]=x;
queue[1][r]=y;
}
void deq()
{
f++;
dx=queue[0][f];
dy=queue[1][f];
}
void bfs(int x, int y) // a[x][y]에서 bfs
{
if( x+1<k && a[x+1][y]==1 ) enq(x+1,y);
if(y+1<k && a[x][y+1]==1) enq(x, y+1);
if( x-1>=0 && a[x-1][y]==1 ) enq(x-1,y);
if(y-1>=0 && a[x][y-1]==1) enq(x, y-1);
}
int main()
{
int i, j, n=0;
scanf("%d", &k);
for(i=0; i<k; i++)
{
for(j=0; j<k; j++)
scanf("%1d", &a[i][j]);
}
enq(0,1);
while(f!=r) //큐가 차있는동안
{
deq();
printf("%d %d\n",dx,dy);
bfs(dx,dy);
n++;
}
printf("%d", n);
}
/*
#include<stdio.h>
int a[1000][1000]={}, day=0, k;
int dx,dy;
int m, n;
int queue[2][10000]={};
int f=-1,r=-1;
void enq(int x, int y)
{
a[x][y]=1;
r++;
queue[0][r]=x;
queue[1][r]=y;
}
void deq()
{
f++;
dx=queue[0][f];
dy=queue[1][f];
}
void bfs(int x, int y) // a[x][y]에서 bfs
{
if( x+1<m && a[x+1][y]==0 ) enq(x+1,y);
if(y+1<n && a[x][y+1]==0) enq(x, y+1);
if( x-1>=0 && a[x-1][y]==0 ) enq(x-1,y);
if(y-1>=0 && a[x][y-1]==0) enq(x, y-1);
}
int main()
{
int i, j;
scanf("%d %d", &n, &m);
for(i=0; i<m; i++)
{
for(j=0; j<n; j++)
{
scanf("%d", &a[i][j]);
}
}
for(i=0; i<m; i++)
{
for(j=0; j<n; j++)
{
if(a[i][j]==1)
{
enq(i, j);
}
}
}
k=r+1;
while(f!=r) //큐가 차있는동안
{
deq();
bfs(dx,dy);
if(f==k)
{
day++;
k=r;
}
}
for(i=0; i<m; i++)
{
for(j=0; j<n; j++)
{
if(a[i][j]==0)
{
printf("-1");
return 0;
}
}
}
printf("%d", day);
}
스택 큐
정렬 퀵정렬 (이진탐색)
dfs/bfs
binary search
//기억력 테스트3
#include <stdio.h>
int arr[10]={1,3,5,7,8,9,11,12,16,17};
int bs(int s, int e, int k)
{
int mid=(s+e)/2;
if(s>e) return -1; //not found
if(arr[mid]==k) return mid;
else if(arr[mid]>k) bs(s,mid-1,k);
else bs(mid+1,e,k);
}
int main()
{
int n;
scanf("%d",&n);
printf("%d",bs(0,9,n));
}
#include<stdio.h>
int arr[100001]={};
int bs(int s, int e, int k)
{
int mid=(s+e)/2;
if(s>e) return -1; //not found
if(arr[mid]==k) return mid;
else if(arr[mid]>k) bs(s,mid-1,k);
else bs(mid+1,e,k);
}
int main()
{
int n, m, num, i;
scanf("%d", &n);
for(i=1; i<=n; i++)
scanf("%d", &arr[i]);
scanf("%d", &m);
for(i=0; i<m; i++)
{
scanf("%d", &num);
printf("%d ", bs(1,n,num));
}
}
퀵정렬 + 이분탐색
#include<stdio.h>
int a[50000]={}, a1[50000]={};
void swap(int x,int y)
{
int data=a[x];
a[x]=a[y];
a[y]=data;
}
void qs(int s, int e)
{
if(s>=e)
return;
int pivot=s;
int low=s, high=e+1;
do
{
do
{
high--;
}
while(a[pivot]<a[high]);
do
{
low++;
}
while(a[pivot]>a[low]);
if(low<high)
swap(low,high);
}
while(low<high);
swap(pivot,high);
qs(s,high-1);
qs(high+1,e);
}
int bs(int s, int e, int k)
{
int mid=(s+e)/2;
if(a[mid]==k) return mid;
else if(a[mid]>k) bs(s,mid-1,k);
else bs(mid+1,e,k);
}
int main()
{
int i, n;
scanf("%d", &n);
for(i=0; i<n; i++)
{
scanf("%d", &a[i]);
a1[i]=a[i];
}
for(i=0; i<n; i++)
{
printf("%d ", bs(0,n,a1[i]));
}
}
*/