알고리즘 구현하기

PhiLoSci Wiki
둘러보기로 가기 검색하러 가기

이 문서는 알고리즘을 프로그램으로 구현하는 모습을 시연을 통해 보이기 위한 문서입니다. 아래에서 구현된 모든 프로그램은 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);
}
원본 주소 "http://zolaist.org/wiki/index.php?title=알고리즘_구현하기&oldid=1714"