�ݺ�ߣ

3.How fast we can sort

과 제 수 행 일 지

A0 조
조원
20063532 조부관
20073547 홍진욱
20083438 김무경
20093447 김도형
20093489 송하윤
20093516 장진승

과제 수행기간 : 4월 9일 ~ 4월 20일 (12일) 총 8시간.

주제 : How fast can we sort?

목표 : 순열과 조합을 이용하여 정렬을 시킨다.

계획.

첫 주(4월 9일~15일)
알고리즘을 정리
익혀야 할 개념에 관하여 연구
과제 1에 관한 문제 해결

둘째주(4월 16~20일)
전 주에 끝내지 못한 부분을 논의
과제 2의 프로그램 소스를 작성

첫 주.

4월 09일 월요일

임무분담
조장 : 송하윤 자료조사 : 김무경, 김도형, 장진승, 프로그램코딩 : 조부관, 홍진
욱

학습할 내용
The fundamental principle of counting.
일어날 수 있는 사건의 가짓수를 말하는 것. 1회의 시행에서 일어날 수 있는 사
건의 가짓수를 n이라고 할 때 이 때의 경우의 수를 n이라고 한다.

sample.
r 개의 서로 다른 원소 중에서 중복을 허용하여 n개를 뽑아서 한 줄로 나열하는
경우의 수.
최초에 r 개를 선택할 수 있고 이후에도 계속 r 개를 선택할 수 있기 때문에 이
순열의 개수는 rⁿ임을 알 수 있다.

selection
서로 다른 n 개의 원소에서 중복을 허락하여 r 개를 뽑는 경우의 수. 중복조합
nHr은 r 개의 원소들을 순서에 상관없이 나열하는 것이다.

k-permutation
서로 다른 n 개의 원소 중에서 r 개(n>=r)를 뽑아서 한 줄로 세우는 경우의 수.
nPr의 형태로 나타낸다. 중복순열과, 원순열, 염주순열 등이 있다. p(n, r) = n!
/ (n-r)!

k-combination
집합에서 일부 원소를 취해 부분집합을 만드는 것을 말한다. n 개의 원소를 가
지는 집합에서 k개의 부분집합을 고르는 조합의 경우의 수는 이항계수라 하며,
nCk로 나타낸다. 중복조합이 있다. C(n, k) = n! / k!(n-k)!

4월 11일 수요일

과제1.
10~29까지 20장의 카드를 방법 1, 2, 3에 따라 정렬시켜라.

방법1.
• 가장 큰 수가 나올 때까지 찾아서 이 카드를 테이블 위에 앞면이 위로 오도록 놓는다.
처음부터 다시 그 다음 큰 수를 찾아서 그 카드위에 놓는다. 이 과정을 모든 카드를
찾을 때까지 반복한다. 정렬되었는가? 예
•전체 카드를 몇 번 보아야 하는가? 최소 20회, 최대 190회의 비교를 해야한다.
•최악의 경우는 어떻게 초기화 되었을 경우인가? 10에서부터 29순으로 정렬되어 있을때
가장 많이 비교를 해야한다. 190회의 비교를 통해 구할수 있다. (20*19 / 2 = 190)
•최선의 경우는 어떻게 초기화 되었을 경우인가? 29에서 10의 순으로 정렬 되어 있을때
가장 적게 비교할 수 있다. 20회의 비교만 하면 된다.
•시간 복잡도는 얼마인가? 시간 복잡도는 n개의 숫자가 있을때 정렬하는 식은 n(n-1) /
2이므로 big O는 O(n²)이다.

방법2.
•카드를 두 뭉치로 나눈다. 하나는 첫 수가 1인 것이고 다른 하나는 첫 수가 2인것이다.
각 뭉치를 방법1을사용하여 두 번째 수를 정렬한다. 첫 번째 뭉치를 두번째 뭉치 위에
놓는다. 정렬되었는가? 예.
•카드의 비교 수는 얼마인가? 110회. 카드의 첫수를 비교하는 횟수가 20회이고,

나누어진 카드 뭉치를 방법1의 방법으로 정렬 하면 각각 10C2가 되므로, 45회씩 2번
즉 90번의 비교를 한다. 따라서 비교 횟수는 110회가 된다.

방법3
•카드의 두 번째 수를 이용하여 10개의 뭉치(0~9)로나눈다. 이제 두 번째 수가 0인
뭉치를 집어서 첫 번째수를 보고 두 뭉치로 나누고 뒤집어 놓는다. 두 번째수가 1인
뭉치를 집어서 다시 첫 번째 수를 보고 두 뭉치로 나누어 앞의 뭉치 위에 뒤집어
놓는다. 모든 카드에 대해 반복한다.
•카드의 비교 횟수는 얼마인가? 30회. 두 번째 수를 정렬시키는 과정에서 20회의
비교가 있고, 첫 번째 수를 정렬하는 과정에서 10번의 비교가 있다. 따라서 30회의
비교가 필요하다.

둘째주.

4월 18일 수요일

최종 소스.

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

void combination(char*, int, int, int, int, int*); // combination func..

int main()
{
int i,j, number ,*array
//i = r , number = n
int c=0;//원소의 개수 = n
int next =0;
int nums = 0;
char a[100] = {0};
char *ap = a;
char ar[21]={0};
printf("수식[ex){a,s,d}3]을 입력하시오 : ");
gets(a);
printf("input item number: ");

for(j=0;j<100;j++)Ð
{
if((a[j]>=65&&a[j]<=90)||(a[j]>=97&&a[j]<=122))
{
ar[next]=a[j];
next++;
}
else if((a[j]>=48&&a[j]<=57)||a[j]==0)
{
i=atoi(ap+j);

break
}
}
while(1)// count 증가부분
{
if(ar[c]==0)break
c++;}

printf("%dn",c);
printf("%d",i);

// create memory..
array = (int*)malloc(sizeof(int)*(c+1));

printf("n* %d - combination >n", i);
combination(ar, 0, 0, i, c, array);

printf("n");

// getch();
free(array); // free memory..
return 0;
}

// recursive combination function..
void combination(char *ar, int now, int count, int step, int number, int*
array)
{
int i;

*(array+count) = now;

if (count == step) // search r-combination ..
{

printf(" { %c", ar[*(array+1)-1]); // print frist item..
for (i = 2; i <= count; i++)
{
printf(", %c", ar[*(array+i)-1]); // print other item..
}

printf(" } "); // close..

return ;
}
// recursive routine..
for (i = now+1; i <= number; i++)
{
combination(ar, i, count+1, step, number, array);
}

결과.

�ݺ�ߣ

2012 Dm A0 03 Pdf

Recommended

More Related Content

Similar to 2012 Dm A0 03 Pdf (20)

2012 Dm A0 03 Pdf