/*
#include<stdio.h>
int total,bridge,visit[502][502]={},arr[502][502]={},count[502]={},ar[502]={};
void dfs(int k,int p,int l)
{
int i;
if(arr[k][p]==1){
visit[l][p]=1;
if(p<l){
for(i=1;i<=total;i++)
{
if(visit[p][i]==1){
visit[l][i]=1;
}
}
}
else{
dfs(p,1,l);
ar[p]=1;
}
}
if(p<total){
dfs(k,p+1,l);
}
}
int main()
{
int i,j,a,b,ct=0;
scanf("%d",&total);
scanf("%d",&bridge);
for(i=0;i<bridge;i++)
{
scanf("%d %d",&a,&b);
arr[a][b]=1;
}
for(i=1;i<=total;i++)
{
dfs(i,1,i);
}
for(i=1;i<=total;i++)
{
for(j=1;j<=total;j++)
{
if(visit[i][j]==1){
count[i]++;
count[j]++;
}
}
}
for(i=1;i<=total;i++)
{
if(count[i]==total-1){
ct++;
}
}
printf("%d",ct);
return 0;
}
정렬
1. 느리지만 간단한 ( 버블, 선택, 삽입 ) -> 중첩반복문
2. 빠르지만 복잡한 ( 퀵, 병합, 기수 ,,,,, ) ->
버블정렬 -> 가장 느림, 코드가 짱쉬움 + 개선
n=5 ->
5 1 4 2 3
round 1. 4번비교
1 5 4 2 3
1 4 5 2 3
1 4 2 5 3
1 4 2 3 (5)
round 2. 3번비교
1 4 2 3
1 4 2 3
1 2 4 3
1 2 3 (4)
round 3. 2번비교
1 2 3
1 2 3
1 2 (3)
round 4.
1 2
1 (2)
1 2 3 4 5
1 2 3 4 5 .... 100 102 101
1 2 3 4 5 .... 100 101 (102)
*/
/*
#include <stdio.h>
int a[10001];
int n, i, j, temp;
int main() {
scanf("%d", &n);
for (i=1; i<=n; i++)
scanf("%d", &a[i]);
for(i=1; i<n; i++)
{
for(j=1;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\n", a[i]);
return 0;
}
*/
/*
#include <stdio.h>
int a[10001];
int n, i, j, temp;
int main() {
scanf("%d", &n);
for (i=1; i<=n; i++)
scanf("%d", &a[i]);
for(i=1; i<n; i++)
{
for(j=1;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>
int a[10001]={};
int n,i,j,temp,count=0;
int main()
{
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
for(i=1;i<n;i++)
{
for(j=1;j<=n-i;j++)
{
if(a[j]>a[j+1]){
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
count++;
}
}
if(count==0){
break;
}
count=0;
}
printf("%d",i-1);
return 0;
}
선택정렬 : 인간적
5 1 4 2 3
round 1. arr[1]에 와야 할 숫자를 찾아서 옮긴다
(1) 5 4 2 3
round 2. arr[2]에 와야 할 숫자를 찾아서 옮긴다.
(1) (2) 4 5 3
..
round 4.
(1 2 3 4) 5
*/
/*
#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 main()
{
int a[10001]={};
int n,i,j,temp,max;
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;
}
삽입정렬 : 코드 복잡 but 장점 ( 정렬이 어느정도 되어있는 데이터 )
(정렬완료 숫자들) 정렬할애
5 1 4 2 3
(5) 1 4 2 3
key=1
round 1.
(1 5 ) 4 2 3
key=4
round 2.
(1 4 5 ) 2 3
key=2
round 3.
(1 2 4 5) 3
key=3
round 4.
(1 2 3 4 5)
*/
/*
#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>=1&&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;
}
재귀함수 : for 인간
탐색
순차탐색 ( 냅다 있는걸 다 탐색 순서대로 )
이진탐색 ( 정렬이 되어있는 상태 ) -> 반씩 쪼개서
binary search
int bs(int s, int e, int k) // a[s] ~a[e]에서 k값의 위치 리턴
{
int mid = (s+e)/2;
if(s>e) return -1; // 종료조건 못찾았을때
if(a[mid]==k) return mid;
else if( a[mid] > k) return bs(s,mid-1,k);
else return bs(mid+1,e,k);
}
#include<stdio.h>
int a[1000001]={};
int bs(int s,int e, int k)
{
int mid=(s+e)/2;
if(s>e) return -1;
if(a[mid]==k) return mid;
else if(a[mid]>k) return bs(s,mid-1,k);
else return bs(mid+1,e,k);
}
int main()
{
int n,m,i;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
scanf("%d",&m);
for(i=0;i<m;i++)
{
int temp;
scanf("%d",&temp);
printf("%d ",bs(1,n,temp));
}
return 0;
}
*/
#include<stdio.h>
int a[100001]={};
void qs(int s, int e)
{
int pivot = s;
int left = s, right = e+1;
if(s>=e) return;
do
{
do{
left++;
}while(a[pivot] > a[left]);
do{
right--;
} while(a[pivot] < a[right]);
if(left<right){
int temp;
temp=a[left];
a[left]=a[right];
a[right]=temp;
}
}while(left<right);
int temp=a[right];
a[right]=a[pivot];
a[pivot]=temp;
qs(s,right-1);
qs(right+1,e);
}
int main()
{
int n,m,i;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
qs(1,n);
for(i=1;i<=n;i++)
{
printf("%d\n",a[i]);
}
return 0;
}
/*
#include<stdio.h>
int total,bridge,visit[502][502]={},arr[502][502]={},count[502]={},ar[502]={};
void dfs(int k,int p,int l)
{
int i;
if(arr[k][p]==1){
visit[l][p]=1;
if(p<l){
for(i=1;i<=total;i++)
{
if(visit[p][i]==1){
visit[l][i]=1;
}
}
}
else{
dfs(p,1,l);
ar[p]=1;
}
}
if(p<total){
dfs(k,p+1,l);
}
}
int main()
{
int i,j,a,b,ct=0;
scanf("%d",&total);
scanf("%d",&bridge);
for(i=0;i<bridge;i++)
{
scanf("%d %d",&a,&b);
arr[a][b]=1;
}
for(i=1;i<=total;i++)
{
dfs(i,1,i);
}
for(i=1;i<=total;i++)
{
for(j=1;j<=total;j++)
{
if(visit[i][j]==1){
count[i]++;
count[j]++;
}
}
}
for(i=1;i<=total;i++)
{
if(count[i]==total-1){
ct++;
}
}
printf("%d",ct);
return 0;
}
정렬
1. 느리지만 간단한 ( 버블, 선택, 삽입 ) -> 중첩반복문
2. 빠르지만 복잡한 ( 퀵, 병합, 기수 ,,,,, ) ->
버블정렬 -> 가장 느림, 코드가 짱쉬움 + 개선
n=5 ->
5 1 4 2 3
round 1. 4번비교
1 5 4 2 3
1 4 5 2 3
1 4 2 5 3
1 4 2 3 (5)
round 2. 3번비교
1 4 2 3
1 4 2 3
1 2 4 3
1 2 3 (4)
round 3. 2번비교
1 2 3
1 2 3
1 2 (3)
round 4.
1 2
1 (2)
1 2 3 4 5
1 2 3 4 5 .... 100 102 101
1 2 3 4 5 .... 100 101 (102)
*/
/*
#include <stdio.h>
int a[10001];
int n, i, j, temp;
int main() {
scanf("%d", &n);
for (i=1; i<=n; i++)
scanf("%d", &a[i]);
for(i=1; i<n; i++)
{
for(j=1;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\n", a[i]);
return 0;
}
*/
/*
#include <stdio.h>
int a[10001];
int n, i, j, temp;
int main() {
scanf("%d", &n);
for (i=1; i<=n; i++)
scanf("%d", &a[i]);
for(i=1; i<n; i++)
{
for(j=1;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;
}
*/
/*
int a[10001]={};
int n,i,j,temp,count=0;
int main()
{
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
for(i=1;i<n;i++)
{
for(j=1;j<=n-i;j++)
{
if(a[j]>a[j+1]){
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
count++;
}
}
if(count==0){
break;
}
count=0;
}
printf("%d",i-1);
return 0;
}
선택정렬 : 인간적
5 1 4 2 3
round 1. arr[1]에 와야 할 숫자를 찾아서 옮긴다
(1) 5 4 2 3
round 2. arr[2]에 와야 할 숫자를 찾아서 옮긴다.
(1) (2) 4 5 3
..
round 4.
(1 2 3 4) 5
*/
/*
#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 main()
{
int a[10001]={};
int n,i,j,temp,max;
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;
}
삽입정렬 : 코드 복잡 but 장점 ( 정렬이 어느정도 되어있는 데이터 )
(정렬완료 숫자들) 정렬할애
5 1 4 2 3
(5) 1 4 2 3
key=1
round 1.
(1 5 ) 4 2 3
key=4
round 2.
(1 4 5 ) 2 3
key=2
round 3.
(1 2 4 5) 3
key=3
round 4.
(1 2 3 4 5)
*/
/*
#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>=1&&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;
}
재귀함수 : for 인간
탐색
순차탐색 ( 냅다 있는걸 다 탐색 순서대로 )
이진탐색 ( 정렬이 되어있는 상태 ) -> 반씩 쪼개서
binary search
int bs(int s, int e, int k) // a[s] ~a[e]에서 k값의 위치 리턴
{
int mid = (s+e)/2;
if(s>e) return -1; // 종료조건 못찾았을때
if(a[mid]==k) return mid;
else if( a[mid] > k) return bs(s,mid-1,k);
else return bs(mid+1,e,k);
}
#include<stdio.h>
int a[1000001]={};
int bs(int s,int e, int k)
{
int mid=(s+e)/2;
if(s>e) return -1;
if(a[mid]==k) return mid;
else if(a[mid]>k) return bs(s,mid-1,k);
else return bs(mid+1,e,k);
}
int main()
{
int n,m,i;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
scanf("%d",&m);
for(i=0;i<m;i++)
{
int temp;
scanf("%d",&temp);
printf("%d ",bs(1,n,temp));
}
return 0;
}
*/
#include<stdio.h>
int a[100001]={};
void qs(int s, int e)
{
int pivot = s;
int left = s, right = e+1;
if(s>=e) return;
do
{
do{
left++;
}while(a[pivot] > a[left]);
do{
right--;
} while(a[pivot] < a[right]);
if(left<right){
int temp;
temp=a[left];
a[left]=a[right];
a[right]=temp;
}
}while(left<right);
int temp=a[right];
a[right]=a[pivot];
a[pivot]=temp;
qs(s,right-1);
qs(right+1,e);
}
int main()
{
int n,m,i;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
qs(1,n);
for(i=1;i<=n;i++)
{
printf("%d\n",a[i]);
}
return 0;
}