알고리즘 구현하기
이 문서는 알고리즘을 프로그램으로 구현하는 모습을 시연을 통해 보이기 위한 문서입니다. 아래에서 구현된 모든 프로그램은 http://ideone.com 에서 C로 작성한 것들입니다.
n!을 구하는 재귀적 알고리즘
알고리즘
procedure n! if (n>1) then n!=n×(n-1)! if (n=1) then n!=1
프로그램
#include <stdio.h>
long Factorial (int n) // n을 받아 n!을 반환하는 함수 정의
{
if (n>1) return (n*Factorial(n-1)); // n>1이면, n!=n×(n-1)!
else return 1; // n=1이면, n!=1
}
int main (void)
{
int number; // 변수 number 선언
scanf("%d",&number); // number 값 입력 받기
printf ("%d! = %ld",number,Factorial(number)); // n! 출력하기
return 0;
}
교체 알고리즘
void Swap (int *a, int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
최대값 알고리즘
프로그램
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 8
int Max (int *List, int n)
{
int MaxNum = List[0];
int k=1;
while (k<n) {
if (MaxNum < List[k]) MaxNum = List[k];
k = k + 1;
}
return MaxNum;
}
int main(void) {
int NumList[N];
int i=0;
srand(time(NULL)); // 랜덤 함수 초기화
while (i<N) {
NumList[i] = rand()%100 + 1; // 1부터 100까지의 수 중에 랜덤으로 NumList에 입력
printf ("%d\t",NumList[i]); // NumList를 탭 단위로 출력
i = i + 1;
}
printf ("\nThe biggest number is %d", Max(NumList,N)); // 한 줄 다음에 최대값 출력
return 0;
}
버블 정렬
void BubbleSort (int *List, int n)
{
int i,j;
for (i=0;i<n-1;i=i+1)
for (j=i+1;j<n;j=j+1)
if (List[i] > List[j]) Swap(List+i,List+j);
}
퀵 정렬
int Partition (int *List, int n)
{
int i,j;
for (i=1,j=1;i<n;i=i+1) {
if (List[0]>List[i]) {
if (i>j) Swap (List+j,List+i);
j = j + 1;
}
}
Swap (List,List+j-1);
return j;
}
void QuickSort (int *List, int n)
{
if (n<=1) return;
int cut;
cut = Partition (List,n);
QuickSort(List,cut);
QuickSort(List+cut,n-cut);
}
순차 검색 알고리즘
알고리즘
procedure SequentialSearch (List,TargetValue)
if (List가 비어 있음)
then (검색의 실패를 선언한다)
else
(리스트상의 첫 번째 항목을 TestEntry로 선택한다;
while (TargetValue<TestEntry이고 비교할 항목이 남아 있음)
do (리스트상의 다음 항목을 TestEntry로 선택한다);
if (TargetValue=TestEntry)
then (검색의 성공을 선언한다)
else (검색의 실패를 선언한다)
) end if
프로그램
#include <stdio.h>
#define NOT_EXIST 0
#define EXIST 1
int SequentialSearch (int *List, int n,int TargetValue)
{
if (n<1) return NOT_EXIST;
else {
int test;
test = 0;
while (TargetValue > List[test] && test < n)
{
test = test + 1;
}
if (TargetValue==List[test]) return EXIST;
else return NOT_EXIST;
}
}
int main (void)
{
int TargetValue, List[8];
List[0] = 3; List[1] = 4; List[2]= 10; List[3]=23;
List[4] = 32; List[5] = 43; List[6]=55; List[7]=90;
scanf ("%d", &TargetValue);
if (SequentialSearch(List,8,TargetValue)==1) printf("%d is exist.",TargetValue);
else printf("%d is not exist.",TargetValue);
return 0;
}
이진 검색 알고리즘
알고리즘
procedure BinarySearch (List,TargetValue)
if (List가 비어 있음)
then
(검색 실패를 보고한다)
else
[리스트의 "중앙" 항목을 TestEntry로 선택한다;
if (TargetValue=TestEntry)
(검색 성공을 보고한다)
else if (TargetValue<TestEntry)
(TargetValue가 TestEntry 앞의 리스트 부분에 있는지 보기 위해
BinarySearch 프로시저를 적용하고, 검색 결과를 보고한다)
else if (TargetValue>TestEntry)
(TargetValue가 TestEntry 뒤의 리스트 부분에 있는지 보기 위해
BinarySearch 프로시저를 적용하고, 검색 결과를 보고한다)
] end if
프로그램
#include <stdio.h>
#define NOT_EXIST 0
#define EXIST 1
int BinarySearch (int *List, int n, int TargetValue)
{
if (n==0) return NOT_EXIST;
else {
int test;
test = (n-1)/2;
printf ("항목 %d와 비교\n",test,List[test]);
if (TargetValue == List[test]) return EXIST;
else if (TargetValue > List[test]) return BinarySearch (List+test+1,n-test-1,TargetValue);
else return BinarySearch(List,test,TargetValue);
}
}
int main (void)
{
int TargetValue, List[8];
List[0] = 3; List[1] = 4; List[2]= 10; List[3]=23;
List[4] = 32; List[5] = 43; List[6]=55; List[7]=90;
scanf ("%d", &TargetValue);
if (BinarySearch(List,8,TargetValue)==1) printf("%d is exist.",TargetValue);
else printf("%d is not exist.",TargetValue);
return 0;
}
모두 구현해보기
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 10000
#define NOT_EXIST 0
#define EXIST 1
void Swap (int*, int*);
void MakingList (int*, int);
void MakingSortedList (int*, int);
void PrintList (int*, int);
void BubbleSort (int*, int);
int Partition (int*, int);
void QuickSort (int*, int);
int SequentialSearch (int*, int, int);
int BinarySearch (int*, int, int);
void PrintSearchResult (int*, int, int);
int main(void) {
int NumList[N];
int TargetValue;
MakingSortedList(NumList,N);
PrintList(NumList,N);
scanf("%d",&TargetValue);
PrintSearchResult (NumList,N,TargetValue);
return 0;
}
void MakingList (int* List, int n)
{
int i;
for (i=0;i<n;i=i+1)
List[i] = rand()%(N*10) + 1;
}
void MakingSortedList (int* List, int n)
{
MakingList(List,n);
QuickSort (List,n);
}
void PrintList (int* List, int n)
{
int i;
for (i=0;i<n;i=i+1) {
printf("%d\t",List[i]);
if (i%16==15) printf("\n");
}
printf("\n");
}
void Swap (int *a, int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
void BubbleSort (int *List, int n)
{
int i,j;
for (i=0;i<n-1;i=i+1)
for (j=i+1;j<n;j=j+1)
if (List[i] > List[j]) Swap(List+i,List+j);
}
int Partition (int *List, int n)
{
int i,j;
for (i=1,j=1;i<n;i=i+1) {
if (List[0]>List[i]) {
if (i>j) Swap (List+j,List+i);
j = j + 1;
}
}
Swap (List,List+j-1);
return j;
}
void QuickSort (int *List, int n)
{
if (n<=1) return;
int cut;
cut = Partition (List,n);
QuickSort(List,cut);
QuickSort(List+cut,n-cut);
}
int SequentialSearch (int *List, int n,int TargetValue)
{
if (n<1) return NOT_EXIST;
else {
int test;
test = 0;
while (TargetValue > List[test] && test < n)
{
test = test + 1;
}
if (TargetValue==List[test]) return EXIST;
else return NOT_EXIST;
}
}
int BinarySearch (int *List, int n, int TargetValue)
{
if (n==0) return NOT_EXIST;
else {
int test;
test = (n-1)/2;
if (TargetValue == List[test]) return EXIST;
else if (TargetValue > List[test]) return BinarySearch (List+test+1,n-test-1,TargetValue);
else return BinarySearch(List,test,TargetValue);
}
}
void PrintSearchResult (int *List, int n, int TargetValue)
{
if (BinarySearch(List,n,TargetValue)) printf("%d is exist.",TargetValue);
else printf("%d is not exist",TargetValue);
}