추억이 새록새록 난다 ... 하아 ....

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define PI 3.141592;

// pointerFuntion 준말
typedef void (*pF)(char *str);

void act_1( char *str )
{
        int intValue = 0;
        printf("거리 입력 ? (킬로미터) ");
        scanf("%d", &intValue);
        printf("%d킬로미터는 %f마일입니다.\n" , intValue , (float)(intValue / 1.609344));

    return;
}

void act_2( char *str )
{
        int intValue = 0;
        float area, dulre;
        printf("반지름 ? ");
        scanf("%d", &intValue);
        area= intValue * intValue * PI;
        dulre= 2 * intValue * PI;
        printf("반지름이 %d인 원의 둘레 : %f\n" , intValue , dulre);
        printf("반지름이 %d인 원의 넓이 : %f\n" , intValue , area);

    return;
}

void act_3( char *str )
{
        int maxValue , intValueArray[3];
        for(int i = 0;i < 3;i++)
        {
            printf("%d번째 값을 입력해주세요. " , (i+1));
            scanf("%d", &intValueArray[i]);
        }

        // 삼항연산자 이용.
        maxValue = intValueArray[0] > intValueArray[1] ? intValueArray[0] : intValueArray[1];
        maxValue = maxValue > intValueArray[2] ? maxValue : intValueArray[2];
        
        printf("세가지( %d , %d , %d )중에서 제일큰 값은 %d입니다.\n" , intValueArray[0] , intValueArray[1] , intValueArray[2] , maxValue);

    return;
}

void act_4( char *str )
{    
        char ch;
        float floatValue = 0;
        printf ("위에문자를 입력하세요.(P 이면 pound -> kg, K 이면 kg -> pound) ? ");
        ch = getchar();

        // 소문자로 무조건 교환
        if( 'A' <= ch && ch <= 'Z' )
            ch += 32;

        switch( ch )
        {
            case 'p' :
                printf("파운드 입력 값은 ? ");
                scanf("%f", &floatValue);
                printf("%.2f파운드는 %f킬로그램입니다.\n" , floatValue , (floatValue * 0.453592));
                break;
            case 'k' :
                printf("킬로그램 입력 값은 ? ");
                scanf("%f", &floatValue);
                printf("%.2f킬로그램은 %f파운드입니다.\n" , floatValue , (floatValue * 2.204623));
                break;
            default :
                printf ("'%c'문자열은 p 와 k 의 문자가 아닙니다.\n" , ch);
                break;
        }
        
    return;
}

// functionArray 준말
void (*fA[4])( char *str) = {act_1 , act_2 , act_3 , act_4};

// functionExcute 준말
pF fE(int i)
{
    return fA[i];
}

void main(void)
{
        int form = 0;
        char ch;
    
        printf ("====== 다음중 계산식을 고르시오 =====\n\n");
        printf ("1. 킬로미터 => 마일 계산\n");
        printf ("2. 반지름 => 원의 둘레,넓이 계산\n");
        printf ("3. 세가지의 숫자중 큰값 계산\n");
        printf ("4. 킬로그람 => 파운드 또는 파운드 => 킬로그람 계산\n\n");
        printf ("위에 숫자중 계산하고 싶은 항목을 고르시오 (숫자하나) ");

        ch = getchar();
        fflush(stdin); // 개행문자 비우기. 또는 getchar() 한번더 실행해도 된다.
        form = (int)ch - 48; // 48을 빼주는 이유는 숫자의 기본 캐릭터 코드 넘버가 숫자 + 48이기 때문.
        if(!( form > 0 && form <= 4 ))
        {
            printf("숫자 5이상 입력하지마시오.\n실행이 종료됩니다.\n");
            system("pause");
            return;
        }
 
        fE(--form)("test");
        system("pause");

    return;    

}

 

먼저 이 글을 읽고 숙지하기에 앞서 이 글은
순전히 C언어 프로그래밍 초보자들을 위한 코딩 기법을 설명한 것임을
알려드립니다. 자신이 초보자가 아니면 그냥 넘어가시면 되겠습니다.
그러나 제가 만나 본 대부분의 프로그래머들(중수 이상 역시 포함)은
이런 규칙을 전혀 지키지 않고 코딩하더군요..
제가 쓴 글을 읽고 코딩한다면 누가 보더라도 정갈하고 깔끔한
코드가 될 것입니다. 나중에 스스로 짠 코드가 뭔 소린지 몰라
한참을 헤메지 않도록 열심히 노력합시다.
그럼 본론으로 들어갑니다..


1. 변수의 이름

보통의 경우 변수의 이름은 아무 뜻도 없거나 무진장 줄여 자신이 짠
코드도 나중에 보면 무슨 소린지 무슨 내용인지 전혀 알아 보지 못하는
경우가 있습니다. 이럴 때 변수의 이름만이라도 변수의 용도에 맞춰서
쓴다면 그 얼마나 좋겠습니까..

변수의 이름을 정할 때는 반드시 헝가리안 표기법을 사용합니다.

코드:

int nCounter=0;

이런식으로 변수의 이름 앞에 변수의 종류를 쓰는 것입니다.

보통 숫자는 number의 앞 글자인 n, boolean 변수는 b, 포인터 변수는 ptr,
문자형 변수는 c, 문자열 변수는 str 등 변수의 이름 앞에 특징을 기술하는 것입니다.

아래의 예를 보시기 바랍니다.

코드:

nSum=0; nGrandTotal=0; cAlphabet=NULL; strSum[6]={0,}; ptrNextChain=NULL; sum=0; grandTotal=0; alphabet=NULL; sum[6]={0,}; nextChain=NULL;

위와 아래는 보기에도 차이가 납니다.
특히 alphabet 변수와 nextChain 변수는 아래의 예만 봤을 때 무슨
변수인지 전혀 알아 볼 수 없습니다. 그러나 위의 예를 보게 되면
최소한 알파벳 변수가 문자형 변수이고 넥스트체인 변수가 포인터라는
것은 변수의 이름을 통해 유추할 수 있습니다.

2. 변수의 초기화
변수의 초기화는 대단히 중요하면서도 간과하기 쉬운 예입니다.
변수는 로컬 변수, 글로벌 변수를 불문하고 무조건 변수 선언할 때
초기화를 해줍니다. 보통의 C 컴파일러는 변수를 초기화하지 않고
그냥 사용하는 경우(즉, 초기화 없이 변수의 값을 읽는 경우) 워닝
메시지를 뿌리거나 메시지 없이 계속 컴파일합니다. 이것으로 생기는
side-effect(부작용)은 컴파일러도 책임지지 않습니다.
프로그램 코드가 길어지면 길어질수록 이런 변수 초기화를 하지 않아
생기는 문제는 더더욱 찾기 어려워집니다.

3. 변수의 용도 또는 사용 목적 기술
보통 위의 방법을 지켜 선언하더라도 변수를 선언할 때는 아래와 같이 하는
프로그래머들이 종종 있습니다.

코드:

int nCounter=0, nSum=0, nMaxBound=0;

나중에 코드를 읽는데 보기에 대단히 좋지 않은 방법입니다.
헝가리안 표기법으로 변수의 이름을 설정했지만 사실상 대략적인
의미만 파악할 수 있을 뿐 그 정확한 용도를 알아보기 힘듭니다.
따라서 아래와 같이 코딩합니다.

코드:

int nCounter=0; /* for문의 카운터로 사용하기 위해 선언 */ int nSum=0;     /* 성적의 합을 저장하기 위해 선언*/ int nMaxBound=0;   /* 그래프의 최대 한계값을 저장하기 위해 선언 */

자, 어떻습니까? 변수를 여러줄에 나눠서 선언한다고 해서 컴파일
시간이 비약적으로 늘어나는 것도 아니고 주석을 많이 단다고 해서
지저분한 프로그램 코드가 되는 것도 아닙니다. 위와 같이 코드를
짜놓으니 변수만 보고서도 무엇하는 프로그램인지 대충의 감을 잡게 됩니다.
프로그램 코드의 분석은 변수의 용도를 파악하기만 해도 절반은 된 것입니다.

잔소리. 저는 최대한 표준 C언어에 가깝게 코딩합니다. 보통의
컴파일러는 표준을 어기더라도 약간 느슨하게 허용하는 경우가 있으나
컴파일러간의 이식률을 높이기 위해 반드시 표준을 지켜서 코딩합시다.

4. 줄 맞추기
이건 잔소리 안할래야 안할 수 없습니다. 제가 대학시절 수업을
들을 당시 C언어를 강의한다는 강사라는 사람도 줄맞추기를
대충하더군요.. 줄맞추기는 칼 같이 해야합니다. 이건 권고사항이
아니라 반드시 지켜야할 강제사항입니다. 줄 맞추기 위해서
스페이스를 두 번 뚜드리던 탭을 한번 하던 그것은 여러분들의
자유지만 어떤 방법을 쓰더라도 줄 맞추기는 통일성 있게
칼 같이 해줘야 합니다. 어떨 때는 스페이스 2번으로 했다가
어떨 때는 탭으로 했다가 하는 짓은 줄 맞추기를 아니한만 못합니다.
코드를 분석해야하는 사람의 입장에서는 굉장히 괴로운 일입니다.
결국에는 눈물을 머금고 코드 줄 맞추기를 한 뒤에 그제서야
코드를 읽기 시작합니다. 무심코 빼먹은 줄 맞추기가 여러 사람 괴롭힙니다.

5. 중괄호 쓰기
코드를 아름답게 하는 방법중에는 중괄호를 많이 쓰는 방법도 있습니다.
중괄호를 많이 쓰면 그만큼 코드를 읽기 편해집니다. 영역이 명시적으로
표시되기 때문이지요.. 예를 볼까요?

코드:

while(i>0) if(i>0) printf("안녕?"); else i--; while(nCounter>0) {   if(nCounter>0)   {     printf("안녕?");   }   else   {     nCounter--;   } }

극단적인 예이기는 하지만 저런 식으로 코딩하는 양반들도
종종 있습니다. 프로그래머라고 할 수도 없는 사람들이지만 말입니다.
아래의 예를 보면 어디서부터 어디까지 무슨 기능을 하는지 명시적으로
표현되어 있습니다. 단 한줄의 코드라도 for, do ~ while, switch ~ case, if ~ else 등
중괄호를 사용할 수 있으면 하라는 것입니다.
사실 중괄호는 아무데나 사용할 수 있습니다만 보통은 변수의 범위를
적절하게 설정하기 위해 코드 중간에 다음과 같이 사용하기도 합니다.

코드:

...   {     int nCounter=0;     for(nCounter=10; nCounter > 0; nCounter--)     {       ...     }   } ...

6. Comment(주석)의 사용
누가 Comment를 주석이라고 이름 붙였는지 모르지만 주석이라는
단어의 사전적인 의미를 모르겠군요.. 그냥 주석은 이런저런 것이다는
것을 경험에 비추어 알고 있지만 말입니다. (일본식 단어인 것 같은
느낌을 팍팍 주는군요..) 저는 코멘트라고 하겠습니다.

용어야 어쨌거나 말았거나 코멘트는 많으면 많을 수록 좋다는 것이
제 지론입니다. 코멘트가 많으면 일단 프로그램을 읽는데 훨씬 수월해집니다.
긴 말 필요 없이 예를 보도록 하겠습니다. 아주 나쁜 예입니다.

코드:

int main(void) {   int n,m,i,j,x,y,z,dae,so;   while(1)   {     printf("두수를 입력하시오 : ");     scanf("%d,%d",&n,&m);     if(n==0 || m==0)     {       break;     }     x=n;     y=m;     for(;;)     {       z=x%y;       if(z==0)       {         break;       }       else       {         x=y,y=z;       }     }     so=y;     printf("%d\t,",so);     dae=n*m/so;     printf("%d\n",dae);   }   return 0; }

아.. 줄 맞춤은 제대로 되었지만 언뜻 봐서는 이거 뭐하는 프로그램인지
도무지 알 수가 없습니다.. 5초 안에 알아보실 수 있겠습니까?
변수 이름도 엉망진창이고 주석도 하나 없고 도무지 알아 먹을 수 있는
코드가 아닙니다. 만약 이 코드를 5초안에 알아 볼 수 있다면
이 프로그램을 1시간 전에 짰거나 이 알고리즘을 자다 일어나서도 외울 수
있을 정도인 사람이거나 당신은 정말 코드 분석의 천재입니다.
훌륭한 예를 보겠습니다.

코드:

/************************************************************* Promgrammed by Chronoshift at 2003.10.12 If you want to contact me, send email to taktaktak@aheheh.com   아규먼트   없음 부작용   없음 프로그램의 내용   두 수를 입력 받고 입력 받은 두 수를 가지고   먼저 최대공약수를 계산하고 최대공약수와   입력받은 두 수를 가지고 최소공배수를 계산한다. *************************************************************/ int main(void) {   int nInputNumber1  = 0;  /* 입력 받은 숫자를 저장하는 변수 */   int nInputNumber2  = 0;  /* 입력 받은 숫자를 저장하는 변수 */   int nNumberBuffer1 = 0;  /* 공약수 계산을 위한 임시 저장소 */   int nNumberBuffer2 = 0;  /* 공약수 계산을 위한 임시 저장소 */   int nBalance       = 0;  /* 나머지 값을 저장 */   int nGCM           = 0;  /* 최대공약수 */   int nLCM           = 0;  /* 최소공배수 */   while(1)   {     /* 수를 입력 받는 부분 */     printf("두 수를 입력하시오 <예) 43 22> : ");     scanf("%d,%d",&nInputNumber1,&nInputNumber2);     /* 입력이 잘 못 된 경우 */     if(nInputNumber1==0 || nInputNumber2==0)     {       printf("This program not support 0 to input.\r\nPlease input other number again.");       break;     }     /* 입력 받은 수를 최대공약수 계산을 위해 임시 저장 */     nNumberBuffer1 = nInputNumber1;     nNumberBuffer2 = nInputNumber2;     /* 최대 공약수 계산 부분 */     /* 최대 공약수를 구하는 알고리즘은(X/Y)%Z == 0 일때까지 무한 반복 */     /* 만약 X=69 이고 Y=93이면 나머지 69가 된다 */     /*  X  Y  Z       */     /* 69 93 69       */     /*   ↙ ↙        */     /* 93 69 24       */     /*   ↙ ↙        */     /* 69 24 21       */     /*   ↙ ↙        */     /* 24 21 3        */     /*   ↙ ↙        */     /* 21 3 0         */     /*   ↙           */     /* 최대공약수 : 3 */     for(;;)     {       /* 두 수를 나눈 나머지 계산*/       nBalance = nNumberBuffer1 % nNumberBuffer2;             /* 나머지가 0이면 GCM을 찾은 것이다 */       if(nBalance == 0)       {         break;       }       /* 그렇지 않으면 알고리즘에 의해 Y를 X에 넣고 */       /* 나머지를 Y에 넣고 재계산한다 */       else       {         nNumberBuffer1 = nNumberBuffer2;         nNumberBuffer2 = nBalance;       }     }     nGCM = nNumberBuffer2;         /* 최소공배수는 두 수를 곱하고 최대공약수로 나누면 된다 */     nLCM = nInputNumber1 * nInputNumber2 / nGCM;     printf("%d\t%d\r\n", nGCM, nLCM);   }   return 0; }

얼마나 아름다운 코드입니까.. 코드를 모두 제거하고
주석만 남기더라도 뭐하는 프로그램인지, 어떻게 돌아가는지,
어떻게 코드를 짜야하는지 금방 알 수 있습니다.
이것이 바로 아름다운 1줄의 예술이라는 것입니다.
7. 맺음말..
더 이상 할 말이 없습니다. 앞에서 얘기한 6가지 원칙을 지키면
누구라도 한 줄의 예술을 할 수 있는 것입니다. 거만하게도 여러분들이
저를 보시기에 제가 고수라고 느끼실런지 몰라도 저 역시 하수일 뿐입니다.
진정한 고수라고 생각되는 사람이 저희 회사에 한 명이 있는데
그 양반 코드는 아주 소설입니다. 프로그래밍을 할 때 아주 소설책을 씁니다.
줄줄이 소설을 쓴 뒤에는 그 소설을 코멘트로 해서 코드를 써갑니다.
코드를 작성한다기 보다 쓴다고 해야 옳은 표현일겁니다.
물론 프로그래밍 마인드가 있어야 가능한 일이기는 합니다.
어쨌거나 코멘트를 바탕으로 코드를 작성해야 하는 원칙은 어느 언어든지
틀린 이야기가 아닙니다. 어렸을 때 전산학원을 다닌 사람들은 알 겁니다.
프로그램 언어를 배우기 전에 순서도를 배우죠. 그리고 순서도를 먼저
그리고 그것으로 프로그래밍하라고 배우죠. 사실은 순서도를 코멘트로
변환하고 그것으로 코딩해야 하지만 말입니다..
에이 모르겠다.. 역시 저는 글쟁이는 안되나 봅니다.
찝찝하더라도 여기서 끝입니다. -끝-

알고리즘·자료구조 학습에서의 문제
우리는 알고리즘 카탈로그를 배웁니다. 이미 그러한 해법이 존재하고, 그것이 최고이며, 따라서 그것을 달달 외우고 이해해야 합니다. 좀 똑똑한 친구들은 종종 "이야 이거 정말 기가 막힌 해법이군!"하고 감탄할지도 모릅니다. 대부분의 나머지 학생들은 그 해법을 이해하려고 머리를 쥐어짜고 한참을 씨름한 후에야 어렴풋이 왜 이 해법이 그 문제를 해결하는지 납득하게 됩니다.

그리고는 그 '증명'은 책 속에 덮어두고 까맣게 사라져버립니다. 앞으로는 그냥 '사용'하면 되는 것입니다. 더 많은 대다수의 학생은 이 과정이 무의미하다는 것을 알기 때문에 왜 이 해법이 이 문제를 문제없이 해결하는지의 증명은 간단히 건너뜁니다.

이런 학생들은 이미 주어진 알고리즘을 사용하는 일종의 객관식 혹은 문제 출제자가 존재하는 시험장 상황에서는 뛰어난 성적을 보일 것임은 자명합니다. 하지만 스스로가 문제와 해답을 모두 만들어내야 하는 상황이라면, 또는 해답이 존재하지 않을 가능성이 있는 상황이라면, 혹은 최적해를 구하는 것이 불가능에 가깝다면, 혹은 알고리즘을 완전히 새로 고안해내야 하거나 기존 알고리즘을 변형해야 하는 상황이라면 어떨까요?

교육은 물고기를 잡는 방법을 가르쳐야 합니다. 어떤 알고리즘을 배운다면 그 알고리즘을 고안해낸 사람이 어떤 사고 과정을 거쳐 그 해법에 도달했는지를 구경할 수 있어야 하고, 학생은 각자 스스로만의 해법을 차근차근 '구성'(construct)할 수 있어야 합니다(이를 교육철학에서 구성주의라고 합니다. 교육철학자 삐아제(Jean Piaget)의 제자이자, 마빈 민스키와 함께 MIT 미디어랩의 선구자인 세이머 페퍼트 박사가 주창했습니다). 전문가가 하는 것을 배우지 말고, 그들이 어떻게 전문가가 되었는지를 배우고 흉내 내야 합니다.

결국은 소크라테스적인 대화법입니다. 해답을 가르쳐 주지 않으면서도 초등학교 학생이 자신이 가진 지식만으로 스스로 퀵소트를 유도할 수 있도록 옆에서 도와줄 수 있습니까? 이것이 우리 스스로와 교사들에게 물어야 할 질문입니다.

왜 우리는 학교에서 '프로그래밍을 하는 과정'이나 '디자인 과정'(소프트웨어 공학에서 말하는 개발 프로세스가 아니라 몇 시간이나 몇 십 분 단위의, 개인적인 차원의 사고 과정 등을 일컫습니다)을 명시적으로 배운 적이 없을까요? 왜 해답에 이르는 과정을 가르쳐주는 사람이 없나요? 우리가 보는 것은 모조리 이미 훌륭히 완성된, 종적 상태의 결과물로서의 프로그램뿐입니다. 어느 날 문득 하늘에서 완성된 프로그램이 뚝 떨어지는 경우는 없는데 말입니다.

교수가 어떤 알고리즘 문제의 해답을 가르칠 때, "교수님, 교수님께서는 어떤 사고 과정을 거쳐, 그리고 어떤 디자인 과정과 프로그래밍 과정을 거쳐서 그 프로그램을 만드셨습니까?"하고 물어봅시다. 만약 여기에 어떤 체계적인 답변도 할 수 없는 분이라면 그 분은 자신의 사고에 대해 '사고'해 본 적이 없거나 문제 해결에 어떤 효율적 체계를 갖추지 못한 분이며, 따라서 아직 남을 가르칠 준비가 되어있지 않은 분일 것입니다. 만약 정말 그렇다면 우리는 어떻게 해야 할까요?

자료구조와 알고리즘 공부
제가 생각건대, 교육적인 목적에서는 자료구조나 알고리즘을 처음 공부할 때 우선은 특정 언어로 구현된 것을 보지 않는 것이 좋을 때가 많습니다. 대신 말로 된 설명이나 의사코드(pseudo-code) 등으로 그 개념까지만 이해하는 것이죠. 그 아이디어를 절차형(C, 어셈블리어)이나 함수형(LISP, Scheme, Haskell), 객체지향(자바, 스몰토크) 언어 등으로 직접 구현해 보는 겁니다. 그 다음에는 다른 사람이나 다른 책의 코드와 비교합니다. 이 경험을 애초에 박탈당한 사람은 귀중한 배움과 깨달음의 기회를 잃은 셈입니다.

만약 여러 사람이 함께 공부한다면 각자 동일한 아이디어를 같은 언어로 혹은 다른 언어로 어떻게 다르게 표현했는지를 서로 비교해 보면 배우는 것이 무척 많습니다.

우리가 자료구조나 알고리즘을 공부하는 이유는, 특정 '실세계의 문제'를 어떠한 '수학적 아이디어'로 매핑시켜 해결할 수 있는지, 그것이 효율적인지, 또 이를 컴퓨터에 어떻게 효율적으로 구현할 수 있는지 따지고, 그것을 실제로 구현하기 위해서입니다. 따라서 이 과정에 있어 실세계의 문제를 수학 문제로, 그리고 수학적 개념을 프로그래밍 언어로 효율적으로 표현해내는 것은 아주 중요한 능력이 됩니다.

알고리즘 공부에서 중요한 것
개별 알고리즘의 목록을 이해, 암기하며 익히는 것도 중요하지만 더 중요한 것은 다음 네 가지입니다.
①알고리즘을 스스로 생각해낼 수 있는 능력
②다른 알고리즘과 효율을 비교할 수 있는 능력
③알고리즘을 컴퓨터와 다른 사람이 이해할 수 있는 언어로 표현해낼 수 있는 능력
④이것의 정상작동(correctness) 여부를 검증해 내는 능력

첫 번째가 제대로 훈련되지 못한 사람은 알고리즘 목록의 스테레오 타입에만 길들여져 있어서 모든 문제를 자신이 아는 알고리즘 목록에 끼워 맞추려고 합니다. 디자인패턴을 잘못 공부한 사람과 비슷합니다. 이런 사람들은 마치 과거에 수학 정석만 수십 번 공부해 문제를 하나 던져주기만 하면, 생각해보지도 않고 자신이 풀었던 문제들의 패턴 중 가장 비슷한 것 하나를 기계적·무의식적으로 풀어제끼는 문제풀이기계와 비슷합니다. 그들에게 도중에 물어보십시오. "너 지금 무슨 문제 풀고 있는 거니?" 열심히 연습장에 뭔가 풀어나가고는 있지만 그들은 자신이 뭘 풀고 있는지도 제대로 인식하지 못 하는 경우가 많습니다.

머리가 푸는 게 아니고 손이 푸는 것이죠. 이렇게 되면 도구에 종속되는 '망치의 오류'에 빠지기 쉽습니다. 새로운 알고리즘을 고안해야 하는 상황에서도 기존 알고리즘에 계속 매달릴 뿐입니다. 알고리즘을 새로 고안해 내건 혹은 기존의 것을 조합하건 스스로 생각해 내는 훈련이 필요합니다.

두 번째가 제대로 훈련되지 못한 사람은 일일이 구현해 보고 실험해 봐야만 알고리즘 간의 효율을 비교할 수 있습니다. 특히 자신이 가진 카탈로그를 벗어난 알고리즘을 만나면 이 문제가 생깁니다. 이건 상당한 대가를 치르게 합니다.

세 번째가 제대로 훈련되지 못한 사람은, 문제를 보면 "아, 이건 이렇게 저렇게 해결하면 됩니다"하는 말은 곧잘 할 수 있지만 막상 컴퓨터 앞에 앉혀 놓으면 아무 것도 하지 못합니다. 심지어 자신이 생각해낸 그 구체적 알고리즘을 남에게 설명해 줄 수는 있지만, 그걸 '컴퓨터에게' 설명하는 데는 실패합니다. 뭔가 생각해낼 수 있다는 것과 그걸 컴퓨터가 이해할 수 있게 설명할 수 있다는 것은 다른 차원의 능력을 필요로 합니다.

네 번째가 제대로 훈련되지 못한 사람은, 알고리즘을 특정 언어로 구현해도, 그것이 옳다는 확신을 할 수 없습니다. 임시변통(ad hoc)의 아슬아슬한 코드가 되거나 이것저것 덧붙인 누더기 코드가 되기 쉽습니다. 이걸 피하려면 두 가지 훈련이 필요합니다.

하나는 수학적·논리학적 증명의 훈련이고, 다른 하나는 테스트 훈련입니다. 전자가 이론적이라면 후자는 실용적인 면이 강합니다. 양자는 상보적인 관계입니다. 특수한 경우들을 개별적으로 테스트해서는 검증해야 할 것이 너무 많고, 또 모든 경우에 대해 확신할 수 없습니다. 테스트가 버그의 부재를 보장할 수는 없습니다. 하지만 수학적 증명을 통하면 그것이 가능합니다. 또, 어떤 경우에는 수학적 증명을 굳이 할 필요 없이 단순히 테스트 케이스 몇 개만으로도 충분히 안정성이 보장되는 경우가 있습니다. 이럴 때는 그냥 테스트만으로 만족할 수 있습니다.

실질적이고 구체적인 문제를 함께 다루라
자료구조와 알고리즘 공부를 할 때에는 가능하면 실질적이고 구체적인 실세계의 문제를 함께 다루는 것이 큰 도움이 됩니다. 모든 학습에 있어 이는 똑같이 적용됩니다. 인류의 지성사를 봐도, 구상(concrete) 다음에 추상(abstract)이 옵니다. 인간 개체 하나의 성장을 봐도 그러합니다. 'be-동사 더하기 to-부정사'가 예정으로 해석될 수 있다는 룰만 외우는 것보다 다양한 예문을 실제 문맥 속에서 여러 번 보는 것이 훨씬 나을 것은 자명합니다. 알고리즘과 자료구조를 공부할 때 여러 친구들과 함께 연습문제(특히 우리가 경험하는 실세계의 대상들과 관련이 있는 것)를 풀어보기도 하고, ACM의 ICPC(International Collegiate Programming Contest: 세계 대학생 프로그래밍 경진 대회) 등의 프로그래밍 경진 대회 문제 중 해당 알고리즘·자료구조가 사용될 수 있는 문제를 같이 풀어보는 것도 아주 좋습니다. 이게 가능하려면 "이 알고리즘이 쓰이는 문제는 이거다"하고 가이드를 해줄 사람이 있으면 좋겠죠. 이것은 그 구체적 알고리즘·자료구조를 훈련하는 것이고, 이와 동시에 어떤 알고리즘을 써야할지 선택, 조합하는 것과 새로운 알고리즘을 만들어내는 훈련도 무척 중요합니다.

알고리즘 디자인 과정의 중요성
알고리즘을 좀더 수월하게, 또 잘 만들려면 알고리즘 디자인 과정에 대해 생각해 봐야 합니다. 그냥 밑도 끝도 없이 문제를 쳐다본다고 해서 알고리즘이 튀어나오진 않습니다. 체계적이고 효율적인 접근법을 사용해야 합니다. 대표적인 것으로 다익스트라(E. W. Dijkstra)와 워스(N. Wirth)의 '조금씩 개선하기'(Stepwise Refinement)가 있습니다. 워스의 「Program Development by Stepwise Refinement」(1971, CACM 14.4, http://www.acm.org/classics/dec95)를 꼭 읽어보길 바랍니다. 여기 소개된 조금씩 개선하기는 구조적 프로그래밍에서 핵심적 역할을 했습니다(구조적 프로그래밍을 'goto 문 제거' 정도로 생각하면 안 됩니다). 다익스트라의 「Stepwise Program Construction」(Selected Writings on Computing: A Personal Perspective, Springer-Verlag, 1982, http://www.cs.utexas.edu/users/EWD/ewd02xx/EWD227.PDF)도 추천합니다.

알고리즘 검증은 알고리즘 디자인과 함께 갑니다. 새로운 알고리즘을 고안할 때 검증해 가면서 디자인하기 때문입니다. 물론 가장 큰 역할은 고안이 끝났을 때의 검증입니다. 알고리즘 검증에는 루프 불변식(loop invariant) 같은 것이 아주 유용합니다. 아주 막강한 무기입니다. 익혀 두면 두고두고 가치를 발휘할 것입니다. 맨버(Udi Manber)의 알고리즘 서적(『Introduction to Algorithms: A Creative Approach』)이 알고리즘 검증과 디자인이 함께 진행해 가는 예로 자주 추천됩니다. 많은 계발을 얻을 것입니다. 고전으로는 다익스트라의 『A Discipline of Programming』과 그라이스(Gries)의 『The Science of Programming』이 있습니다. 특히 전자를 추천합니다. 프로그래밍에 대한 관을 뒤흔들어 놓을 것입니다.

알고리즘과 패러다임
알고리즘을 공부하면 큰 줄기들을 알아야 합니다. 개별 테크닉도 중요하지만 '패러다임'이라고 할만한 것들을 알아야 합니다. 이것에 대해서는 튜링상을 수상한 로버트 플로이드(Robert Floyd)의 튜링상 수상 강연(The Paradigms of Programming, 1978)을 추천합니다. 패러다임을 알아야 알고리즘을 상황에 맞게 마음대로 변통할 수 있습니다. 그리고 자신만의 분류법을 만들어야 합니다. 구체적인 문제들을 케이스 바이 케이스로 여럿 접하는 동안 그냥 지나쳐 버리면 개별자는 영원히 개별자로 남을 뿐입니다. 비슷한 문제들을 서로 묶어서 일반화해야 합니다.

이런 패러다임을 발견하려면 '다시 하기'가 아주 좋습니다. 다른 것들과 마찬가지로, 이 다시 하기는 알고리즘에서만이 아니고 모든 공부에 적용할 수 있습니다. 같은 것을 다시 해보는 것에서 우리는 얼마나 많은 것을 배울 수 있을까요. 대단히 많습니다. 왜 동일한 문제를 여러 번 풀고, 왜 같은 내용의 세미나에 또 다시 참석하고, 같은 프로그램을 거듭 작성할까요? 훨씬 더 많이 배울 수 있기 때문입니다. 화술 교육에서는 같은 주제에 대해 한 번 말해본 연사와 두 번 말해본 연사는 천지 차이가 있다고 말합니다. 같은 일에 대해 두 번의 기회가 주어지면 두 번째에는 첫 번째보다 잘 할 기회가 있습니다. 게다가 첫 번째 경험했던 것을 '터널을 벗어나서' 다소 객관적으로 볼 수 있게 됩니다. 왜 자신이 저번에 이걸 잘 못 했고, 저걸 잘 했는지 알게 되고, 어떻게 하면 그걸 더 잘할 수 있을는지 깨닫게 됩니다. 저는 똑같은 문제를 여러 번 풀더라도 매번 조금씩 다른 해답을 얻습니다. 그러면서 정말 엄청나게 많은 것을 배웁니다. '비슷한 문제'를 모두 풀 능력이 생깁니다.

제가 개인적으로 존경하는 전산학자 로버트 플로이드(Robert W. Floyd)는 1978년도 튜링상 강연에서 다음과 같은 말을 합니다.

제가 어려운 알고리즘을 디자인하는 경험을 생각해 볼 때, 제 능력을 넓히는 데 가장 도움이 되는 특정한 테크닉이 있습니다. 어려운 문제를 푼 후에, 저는 그것을 처음부터 완전히 새로 풉니다. 좀 전에 얻은 해법의 통찰(insight)만을 유지하면서 말이죠. 해법이 제가 희망하는 만큼 명료하고 직접적인 것이 될 때까지 반복합니다. 그런 다음, 비슷한 문제들을 공략할 어떤 일반적인 룰을 찾습니다. 아까 주어진 문제를 아예 처음부터 최고로 효율적인 방향에서 접근하도록 이끌어줬을 그런 룰을 찾는 거죠. 많은 경우에 그런 룰은 불변의 가치가 있습니다. … 포트란의 룰은 몇 시간 내에 배울 수 있습니다. 하지만 관련 패러다임은 훨씬 더 많은 시간이 걸립니다. 배우거나(learn) 배운 것을 잊거나(unlearn) 하는 데 모두.

수학자와 프로그래머를 포함한 모든 문제 해결자들의 고전이 된 죠지 폴리야(George Polya)의 『How to Solve it』에는 이런 말이 있습니다:

심지어는 꽤나 훌륭한 학생들도, 문제의 해법을 얻고 논증을 깨끗하게 적은 다음에는 책을 덮어버리고 뭔가 다른 것을 찾는다. 그렇게 하는 동안 그들은 그 노력의 중요하고도 교육적인 측면을 잃어버리게 된다. … 훌륭한 선생은 어떠한 문제이건 간에 완전히 바닥이 드러나는 경우는 없다는 관점을 스스로 이해하고 또 학생들에게 명심시켜야 한다.

저는 ACM의 ICPC 문제 중에 어떤 문제를 이제까지 열 번도 넘게 풀었습니다. 대부분 짝 프로그래밍이나 세미나를 통해 프로그래밍 시연을 했던 것인데, 제 세미나에 여러 번 참석한 분이 농담조로 웃으며 물었습니다. "신기해요. 창준 씨는 그 문제를 풀 때마다 다른 프로그램을 짜는 것 같아요. 설마 준비를 안 해 와서 그냥 내키는 대로 하는 건 아니죠?" 저는 카오스 시스템과 비슷하게 초기치 민감도가 프로그래밍에도 작용하는 것 같다고 대답했습니다. 저 스스로 다른 해법을 시도하고 싶은 마음이 있으면 출발이 조금 다르고, 또 거기서 나오는 진행 방향도 다르게 됩니다. 그런데 중요한 것은 이렇게 같은 문제를 매번 다르게 풀면서 배우는 것이 엄청나게 많다는 점입니다. 저는 매번, 전보다 개선할 것을 찾아내게 되고, 또 새로운 것을 배웁니다. 마치 마르지 않는 샘물처럼 계속 생각할 거리를 준다는 점이 참 놀랍습니다.

알고리즘 개론 교재로는 CLR(Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest)을 추천합니다. 이와 함께 혹은 이 책을 읽기 전에 존 벤틀리(Jon Bentley)의 『Programming Pearls』도 강력 추천합니다. 세계적인 짱짱한 프로그래머와 전산학자들이 함께 꼽은 위대한 책 목록에서 몇 손가락 안에 드는 책입니다. 아직 이 책을 본 적이 없는 사람은 축하합니다. 아마 몇 주간은 감동 속에 하루하루를 보내게 될 겁니다.



리팩토링 학습에서의 문제
먼저, 본지 2001년 11월호에 제가 썼던 마틴 파울러의 책을 추천하는 글을 인용하겠습니다.

OOP를 하건 안 하건 프로그래밍이란 업을 하는 사람이라면 이 책은 자신의 공력을 서너 단계 레벨업시켜줄 수 있다. 자질구레한 술기를 익히는 것이 아니고 기감과 내공을 증강하는 것이다.

혹자는 DP 이전에 RF를 봐야 한다고도 한다. 이 말이 어느 정도 일리가 있는 것이, 효과적인 학습은 문제의식이 선행해야 하기 때문이다. DP는 거시적 차원에서 해결안을 모아놓은 것이다. RF를 보고 나쁜 냄새(Bad Smell)를 맡을 수 있는 후각을 발달시켜야 한다. RF의 목록을 모두 외우는 것은 큰 의미가 없다. 그것보다 냄새나는 코드를 느낄 수 있는 감수성을 키우는 것이 더 중요하다. 필자는 일주일에 한 가지씩 나쁜 냄새를 정해놓고 그 기간 동안에는 자신이 접하는 모든 코드에서 그 냄새만이라도 확실히 맡도록 집중하는 방법을 권한다. 일명 일취집중후각법. 패턴 개념을 만든 건축가 크리스토퍼 알렉산더나 GoF의 랄프 존슨은 좋은 디자인이란 나쁜 것이 없는 상태라고 한다. 무색 무미 무취의 무위(無爲)적 자연(自然) 코드가 되는 그 날을 위해 오늘도 우리는 리팩토링이라는 유위(有爲)를 익힌다.

주변에서 리팩토링을 잘못 공부하는 경우를 종종 접합니다. 어떤 의미에서 잘못 공부한다고 할까요? '실체화'가 문제입니다. 리팩토링은 도구이고 방편일 뿐인데, 그것에 매달리는 것은 달은 보지 않고 손을 보는 것과 같습니다. 저는 리팩토링 책이 또 하나의 (이미 그 병폐가 많이 드러난) GoF 책이 되는 현상이 매우 걱정됩니다.

리팩토링 공부
사람들이 일반적으로 생각하는 바와는 달리 리팩토링 학습에 있어 어떤 리팩토링이 있는지, 구체적으로 무엇인지 등의 리팩토링 목록에 대한 지식과 각각에 대한 메카닉스(Mechanics: 해당 리팩토링을 해나가는 구체적 단계)는 오히려 덜 중요할 수 있습니다. 더 기본적이고 유용한 것은 코드 냄새(Code Smell)와 짧은 테스트-코드 싸이클입니다. 이것만 제대로 되면 리팩토링 책의 모든 리팩토링을 스스로 구성해낼 수 있으며, 다른 종류의 리팩토링까지 직접 발견해낼 수 있습니다.

그 책에서는 테스트의 중요성이 충분히 강조되지 않았습니다. 하지만 테스트 코드 없는 리팩토링은 안전벨트 없는 자동차 경주와 같습니다. 그리고 테스트 코드가 리팩토링의 방향을 결정하기도 합니다. 양자는 음과 양처럼 서로 엮여 있습니다. 이런 의미에서 리팩토링은 TDD(Test Driven Development)와 함께 수련하는 것이 좋습니다. 훨씬 더 빨리, 훨씬 더 많은 것을 배울 수 있을 겁니다.

리팩토링을 공부할 때는 우선 코드 냄새의 종류를 알고, 왜 그것이 나쁜 냄새가 될 수 있는지 이해하고(그게 불가하다면 리팩토링 공부를 미뤄야 합니다) 거기에 동의할 수 있어야 합니다. 그런 다음, 대충 어떤 종류의 리팩토링이 가능한지 죽 훑어봅니다. 그 중 몇 개는 메카닉스를 따라가면서 실험해 봅니다. 이제는 책을 덮습니다. 그리고 실제 코드를 접하고, 만약 거기에서 냄새를 맡는다면 이 냄새를 없애기 위해 어떻게 해야 할지 스스로 고민합니다. 리팩토링 책의 목록은 일단 무시하십시오. 그 냄새를 없애는 것이 목표이지, 어떤 리팩토링을 여기에 '써먹는 것'이 목표가 되어선 안 됩니다. 이 때, 반드시 테스트 코드가 있어야 합니다. 그래야 '좋은' 리팩토링을 할 수 있습니다. 책을 떠나 있으면서도 책에서 떠나지 않는 방법입니다.

리팩토링을 하기 전에 초록색 불(테스트가 모두 통과)이 들어온 시점에서 코드를 일부 고치면 빨간 불(테스트가 하나라도 실패)로 바뀔 겁니다. 이게 다시 초록색 불이 될 때까지 최소한도의 시간이 걸리도록 하십시오. 현 초록색에서 다음 초록색까지 최소한의 시간을 소비하도록 하면서 코드와 테스팅을 오가게 되면 자기도 모르는 사이에 훌륭한 리팩토링이 자발공으로 터져 나옵니다. 여기서 목적지는 우선은 OAOO(Once And Only Once: 모든 것은 오로지 한 번만 말해야 한다)를 지키는 쪽으로 합니다. 그러면 OAOO와 짧은 테스트-코드 싸이클을 지키는 사이 어느새 탁월한 디자인이 튀어나옵니다. 참고로 저는 '모래시계 프로그래밍'이란 걸 가끔 합니다. 모래시계나 알람 프로그램으로 테스트-코드 사이클의 시간을 재는 것입니다. 그래서 가급적이면 한 사이클이 3분 이내(대부분의 모래시계는 단위가 3분입니다)에 끝나도록 노력합니다. 여기서 성공을 하건 실패를 하건 많은 걸 얻습니다.



리팩토링 수련법
제가 고안, 사용한 몇 가지 리팩토링 수련법을 알려드립니다.

①일취집중후각법: 앞에 소개한 본지 2001년 11월호에서 인용된 글 참조
②주석 최소화: 주석을 최소화하되 코드의 가독성이 떨어지지 않도록(혹은 오히려 올라가도록) 노력합니다. 이렇게 하면 자동으로 리팩토링이 이뤄지는 경우가 많습니다.
③OAOO 따르기: OAOO 법칙을 가능하면 최대한, 엄격하게 따르려고 합니다. 역시 자동으로 좋은 리팩토링이 이뤄집니다. 여기서 디자인패턴이 창발하기도 합니다. GoF 책을 한번도 보지 못한 사람이 디자인패턴을 자유자재로 부리는 경우를 보게 됩니다.
④디미터 법칙(Law of Demeter) 따르기: 디미터 법칙을 가능하면 지키려고 합니다. 어떤 리팩토링이 저절로 이뤄지거나 혹은 필요 없어지는가요?
⑤짝(Pair) 리팩토링: 함께 리팩토링합니다. 혼자 하는 것보다 더 빨리, 더 많은 걸 배우게 됩니다. 특히, 각자 작성했던 코드를 함께 리팩토링하고, 제3자의 코드를 함께 리팩토링해 봅니다. 사람이 많다면 다른 짝이 리팩토링한 것과 서로 비교하고 토론합니다.
⑥'무엇'과 '어떻게'를 분리: 어떻게에서 무엇을 분리해 내도록 합니다. 어떤 리팩토링이 창발합니까?

여기서 번, 짝 리팩토링은 아주 효과적인 방법입니다. 저는 이것을 협동적 학습(Collaborative Learning)이라고 부릅니다. 상대가 나보다 더 많이 아는 경우만이 아니고, 서로 아는 것이 비슷해도 많은 양의 학습이 발생합니다. 특히, 전문가와 함께 짝 프로그래밍을 하면 무서울 만큼 빠른 학습을 경험할 수 있습니다. 저와 짝 프로그래밍을 한 사람이 학습하는 속도에서 경이감을 느낀 적이 한두 번이 아닙니다. 문화는 사회적으로 학습되는 것입니다. 우리가 지식이라고 하는 것의 상당 부분은 문화처럼 암묵적인 지식(Tacit Knowledge)입니다. 전문가가 문제가 생겼을 때 어떻게 사고하고, 어떤 과정을 거쳐 접근하며, 어떻게 디버깅하고, 키보드를 어떤 식으로 누르는지, 사고 도구로 무엇을 사용하는지, 일 계획과 관리를 어떻게 하는지, 동료와 어떻게 대화하는지 등은 성문화되어 있지 않습니다. 그러나 이런 것들은 아주 중요합니다. 프로페셔널의 하루 일과의 대부분을 이루고 있기 때문입니다. 이런 것들은 전문가 바로 옆에서 조금씩 일을 도와주면서 배워야 합니다. 도제 살이(Apprenticeship)입니다. 진정한 전문가는 모든 동작이 우아합니다. 마치 춤을 추는 것 같습니다. 이 모습을 바로 곁에서 지켜보게 되면, 주니어는 한마디로 엄청난 충격을 받습니다. 그리고 스펀지처럼 빨아들이게 됩니다. 도대체 이 경험을 책이나 공장화한 학교가 어떻게 대신하겠습니까. 이와 관련해서는 레이브와 웽거(Jean Lave, Etienne Wenger)의 『Situated Learning : Legitimate Peripheral Participation』을 강력 추천합니다. 이 글을 보는 모든 교육 종사자들이 꼭 읽어봤으면 합니다. 이 협동적 학습은 두 사람만이 아니고 그룹 단위로도 가능합니다. 스터디에 이용하면 재미와 유익함 일석이조를 얻습니다.

이 외에, 특히(어쩌면 가장) 중요한 것은 일취집중후각법 등을 이용해 자신의 코드 후각의 민감도를 높이는 것입니다. 코드 후각의 메타포 말고도 유사한 메타포가 몇 가지 더 있습니다. 켄트 벡은 코드의 소리를 들으라고 하고, 저는 코드를 향해 대화하라고 합니다. 코드의 소리를 듣는 것은 코드가 원하는 것에 귀를 기울이는 것을 말합니다. 코드는 단순해지려는 욕망이 있습니다. 그걸 이뤄주는 것이 프로그래머입니다. 그리고 짝 프로그래밍을 할 때 두 사람의 대화를 코드에 남기도록 합니다. 주석이 아닙니다.

우리 프로그래머들은 항상 공부해야 합니다. 우리는 지식을 중요하게 여깁니다. 하지만 지식에 대한 지식, 즉 내가 그 지식을 얻은 과정이나 방법 같은 것은 소홀히 여기기 쉽습니다. 따라서 지식의 축적과 공유는 있어도 방법론의 축적과 공유는 매우 드문 편입니다. 저는 평소에 이런 생각에서 학교 후배들을 위해 제 자신의 공부 경험을 짬짬이 글로 옮겨놓았고, 이번 기회에 그 글들을 취합, 정리하게 되었습니다. 그 결실이 바로 이 글입니다

이 글은 공부하는 방법과 과정에 관한 글입니다. 이 글은 제가 공부한 성공/실패 경험을 기본 토대로 했고, 지난 몇 년간 주변에서 저보다 먼저 공부한 사람들의 경험을 관찰, 분석한 것에 제가 다시 직접 실험한 것과 그밖에 오랫동안 꾸준히 모아온 자료들을 더했습니다. '만약 다시 공부한다면' 저는 이렇게 공부할 것입니다.

부디 독자 제현께서 이 글을 씨앗으로 삼아 자신만의 나무를 키우고 거기서 열매를 얻고, 또 그 열매의 씨앗이 다시 누군가에게 전해질 수 있다면 더 이상 바랄 것이 없겠습니다.

이 글은 특정 주제들의 학습/교수법에 대한 문제점과 제가 경험한 좋은 공부법을 소개하는 식으로 구성됐습니다. 여기에 선택된 과목은 리팩토링, 알고리즘·자료구조, 디자인패턴, 익스트림 프로그래밍(Extreme Programming 혹은 XP) 네 가지입니다.

이 네 가지가 선택된 이유는 필자가 관심있게 공부했던 것이기 때문만은 아니고, 모든 프로그래머에게 어떻게든 널리 도움이 될만한 교양과목이라 생각하여 선택한 것입니다. 그런데 이 네 가지의 순서가 겉보기와는 달리 어떤 단계적 발전을 함의하는 것은 아닙니다. 수신(修身)이 끝나면 더 이상 수신은 하지 않고 제가(齊家)를 한다는 것이 어불성설인 것과 같습니다.

원래는 글 후미에 일반론으로서의 공부 패턴들을 쓰려고 했습니다. 하지만 지면의 제약도 있고, 독자 스스로 이 글에서 그런 패턴을 추출하는 것도 의미가 있을 것이기에 생략했습니다. 그런 일반론이 여기 저기 숨어있기 때문에 알고리즘 공부에 나온 방법 대부분이 리팩토링 공부에도 적용할 수 있고, 적용되어야 한다는 점을 꼭 기억해 주셨으면 합니다. 다음에 기회가 닿는다면 제가 평소 사용하는 (컴퓨터) 공부패턴들을 소개하겠습니다

복잡도(complexity)의 개념

알고리즘의 성능분석에 있어서의 복잡도(complexity)의 개념에 대해 살펴
보고 공간복잡도(space complexity)와 시간복잡도(time complexity)에 대해
알아본다.

4.1 알고리즘의 성능분석과 복잡도(complexity)
4.2 공간 복잡도(space complexity)
4.3 시간 복잡도(time complexity)

4.1 알고리즘의 성능분석과 복잡도(complexity)
앞 장에서도 언급했듯이 알고리즘은 유한한 횟수의 명령어들을 정해진
순서에 의하여 수행한 다음 언젠가는 반드시 종료되어야 한다.(유한성) 따
라서 알고리즘은 일단 시작된 다음 종료될 때까지의 실행시간이 이치에
맞지 않게 너무 길어서는 안된다. 장기 혹은 바둑과 같은 게임에 대한 알고
리즘을 예를 들어 생각해 볼 수 있다. 이와 같은 게임의 알고리즘을 개발할
때, 게임중 발생할 수 있는 모든 경우를 조사하여 알고리즘을 구성할 수 있
다. 그러나 이러한 방법으로는 알고리즘의 개발 조차도 불가능할 것이며,
그런 방법에 의한 알고리즘의 실행시 얼마만의 시간 안에 계산을 종료할
지도 추측할 수 없게 된다.
따라서, 일반적인 알고리즘은 상식적인 시간 안에 실행을 종료할 수 있어
야 하며, 가능한 한 빠른 시간내에 실행을 종료할 수 있어야 한다. 이러한
관점에서 알고리즘의 성능을 분석하기 위해 시간 복잡도(time complexity)
라는 개념을 사용하게 된다.
알고리즘의 성능 측정을 위한 수단에는 위에 소개된 시간 복잡도(time
complexity) 외에 공간 복잡도(space complexity)도 있다. 시간 복잡도가 알
고리즘의 실행시간을 의미한다면 공간 복잡도는 알고리즘을 수행시키기
위해 필요한 기억장치(memory)의 크기를 의미한다.

[정의4.1] 복잡도(complexity)
시간 복잡도(time complexity): 알고리즘을 실행하여 종료할때까지 필요한
시간
공간 복잡도(space complexity): 알고리즘을 실행하여 종료할때까지 필요
한 기억장치의 크기

4.2 공간 복잡도(space complexity)
주어진 알고리즘을 실행시키기 위해 필요한 기억장치(space)는 다음과
같이 두 가지로 분류해 볼 수 있다.
알고리즘과 무관한 부분: 알고리즘의 특성과는 무관한 부분으로 프로그램
코드를 저장하기 위한 공간, 프로그램을 수행하기 위해 시스템이 필요로
하는 공간 등이 이에 포함된다.
알고리즘과 밀접한 부분: 알고리즘의 특성과 밀접한 관계가 있는 부분으
로서 문제를 해결하기 위해 필요로 하는 공간을 의미한다. 즉, 변수를 저장
하기 위한 공간이나 순환 프로그램일 경우 순환 스택(recursion stack) 등이
이에 포함된다.
일반적으로 알고리즘의 공간 복잡도를 분석할때는 위의 두가지중 두 번
째의 것을 계산하게 된다. 즉, 알고리즘이 문제를 해결하기 위해서 반드시
필요한 부분만을 계산함으로써 주어진 알고리즘의 공간 복잡도를 계산한
다.
다음은 공간 복잡도를 구하는 예이다.
[예제4.1] 공간 복잡도의 계산 1

float abc(float a, float b, float c)
{
return(a + b + b*c + (a + b - c)/(a + b) + 4.0);
}

공간 복잡도 = 0

위의 프로그램에서 공간복잡도를 구하기 위해서 살펴볼 것은 변수 a, b,
c 이다. 따라서, float형의 변수가 한 워드(word)를 차지한다고 가정하면,
공간복잡도는 '3워드'라고 생각할 수 있다. 그러나 변수 a, b, c 는 전달되
는 인자(parameter)로서 함수 abc내에서 해결하고자 하는 문제와는 무관하
다고 볼 수 있으므로 공간 복잡도는 0이다.

[예제4.2] 공간 복잡도 계산 2
float Sum(float a[], int n)
{
float s = 0.0;
for(int i = 1; i < = n; i++)
s += a[i];
return s;
}

공간 복잡도 = n + 3

위의 프로그램에서 사용되는 변수는 a[], n, s, i 이다. 이번 예에서도 a[]
와 n은 인자로 전달 됨을 볼 수 있다. 그러나 [예제4.1]과는 다르게 변수
a[]는 합을 구하기 위하여 반복문 내에서 n개의 원소가 모두 참조되고 있
음을 볼 수 있다. 또한, n은 for-문을 벗어나기 위한 한계값으로 사용된다.
따라서 a[]와 n은 알고리즘이 해결하고자 하는 문제와 밀접한 관련이 있
다고 볼 수 있다. 그러므로 프로그램의 복잡도는 (a[]를 저장하기 위한 공
간) + (변수 n, s, I를 위한 공간) = n + 3 이 된다.

[예제4.3] 공간 복잡도 계산 3
float RSum(float a[], int n)
{
if(n <= 0)
return (0.0);
else
return (RSum(a, n-1) + a[n]);
}

공간 복잡도 = 3(n + 1)

위의 프로그램은 순환기법(resursion)으로 작성된 것이다. 위의 경우 살펴
볼 변수는 a[], n이다. 우선 변수 n은 if-문 내에서 순환의 한계값으로 사용
되고 있음을 볼 수 있다. 또한, 변수 a[]는 합을 구하기 위하여 사용되고
있으며 a[]의 원소 중에서 n번째의 원소만 필요로 한다. 따라서 변수 a[]
와 n이 모두 알고리즘과 밀접한 관계가 있으므로, 프로그램이 필요로 하는
공간은 (a[]의 n번째 원소를 의한 공간) + (n을 위한 공간) = 1 + 1 으로 볼
수 있다. 그러나 위의 프로그램은 순환기법에 의해 작성되었음을 고려해
야 한다. 즉, 프로그램이 순환적으로 실행될 것을 고려해서 몇번의 순환후
에 실행이 종료되는지(the depth of recursion)를 계산해야 하며, 또한 순환
을 위해서 필요한 복귀 주소(return address)를 저장할 공간도 계산해야 한
다. 그러므로 프로그램의 공간 복잡도는 (depth of recursion)×(a[n], n, 복
귀 주소를 위한 공간) = (n+1)×3 이 된다.

4.3 시간 복잡도(time complexity)
시간 복잡도는 알고리즘을 구성하는 명령어들이 몇 번이나 실행이 되는
지를 센 결과(frequency count)에 각 명령어의 실행시간(execution time)을
곱한 합계를 의미한다. 그러나 각 명령어의 실행시간은 특정 하드웨어 혹
은 프로그래밍 언어에 따라서 그 값이 달라질 수 있기 때문에 알고리즘의
일반적인 시간 복잡도는 명령어의 실제 실행시간을 제외한 명령어의 실행
횟수만을 고려하게 된다.
이와 같이 알고리즘을 이루는 명령어들의 실행횟수를 계산하여 알고리
즘의 시간 복잡도를 구하는 일을 알고리즘의 분석(analysis of algorithm)이
라고 한다. 또한, 알고리즘의 분석은 일반적으로 공간 복잡도 보다는 시간
복잡도를 통해서 이루어진다. 따라서 이번 강좌를 통해서 소개되는 알고
리즘들의 분석은 대부분 시간 복잡도를 이용할 것이며 특별한 언급이 없
는 한 '복잡도'는 '시간 복잡도'를 의미하게 된다.
다음은 시간 복잡도를 구하는 예이다.
[예제4.4] 시간 복잡도 계산 1 알고리즘
실행횟수

float Sum(float a[], int n)
{
float s = 0.0; 1
for(int i = 1; i <= n; I++) n+1
s += a[i]; n
return s; 1
}

명령어 총 실행횟수 = 2n + 3, 시간 복잡도 = O(n)
위 알고리즘의 총 실행 횟수는 2n+3 이 되므로 시간 복잡도는 2n+3이다.
또한 복잡도는 일반적으로 'big oh'표기법을 통해서 평균 실행시간을 표현
하게 되는데 위의 알고리즘의 경우는 'big oh' 표기법으로 O(n)이 된다. 복
잡도의 표기 방법에 대해서는 다음절에서 보다 자세히 살펴보도록 하겠다.
순환 알고리즘의 경우, 시간 복잡도를 구하기 위하여 명령어의 실행 횟수
를 세는 것은 위의 [예제4.4]와 같은 방법으로는 어렵다. 따라서 일반적으
로 순환 알고리즘의 시간 복잡도를 구하기 위해서는 순환식(recursive
formula)을 이용하게 된다. [예제4.3]에서 소개된 알고리즘을 예로 들면 다
음과 같다.

[예제4.5] 시간 복잡도 계산 2 알고리즘
실행횟수

float RSum(float a[], int n)
{
if(n <= 0) 1
return (0.0); 1
else
return (RSum(a, n-1) + a[n]); 1 + T(RSum(n-1))
}

명령어 총 실행횟수 = 2n + 1, 시간 복잡도 = O(n)
위의 알고리즘에서 사용된 순환식을 이용하면 명령어의 실행횟수는 다
음과 같음을 알 수 있다.
T(RSum(n)) = 2 ,if n = 0
= 2 + T(RSum(n-1) ,if n > 0
이와 같은 순환식은 또한 순환관계(recurrence relation)라고도 말하는데,
이러한 순환관계로부터 총 명령어 실행횟수를 구하는 방법은 다음과 같다.
T(RSum(n)) = 2 + T(RSum(n-1))
= 2 + ( 2 + T(RSum((n-2)) )
= 2 + ( 2 + ( 2 + T(RSum((n-3)) ) )
......
= 2×n + T(RSum(0))
= 2n + 2
따라서, 명령어 실행횟수의 총 합은 2n+2이고 시간 복잡도는 O(n)이다.

1. 알고리즘의 성능을 측정하기 위한 수단으로서 복잡도(complexity)를 사
용하며, 복잡도에는 알고리즘의 수행에 필요한 시간을 의미하는 시간 복
잡도(time complexity)와 필요한 기억장치(memory)의 크기를 의미하는 공
간 복잡도(space complexity)가 있다.

2. 공간 복잡도는 알고리즘이 해결하고자 하는 문제와 밀접한 관련이 있는
부분 즉, 변수를 저장하기 위한 공간, 순환 프로그램일 경우 순환
스택(recursion stack)등을 모두 합한 값으로 나타낸다.

3. 시간 복잡도는 알고리즘을 구성하는 명령어들의 실행횟수를 모두 합한
값으로 나타내며, 일반적인 알고리즘 분석은 시간 복잡도를 통하여 이루
어진다.

5개로 나눌 때 O 성능 분석

Blum, Floyd, Pratt, Rivest, & Tarjan(1973)의 선택 알고리즘(정확히는 median-of-medians)은 O(n)의 성능으로 순위 통계량(i번째 원소)을 검색할 수 있게 해준다. 이 알고리즘은 n개의 원소를 1) 5개의 집단으로 나누고 각 집단의 중간값(median)을 찾아(Θ(n)) 2) 재귀적으로 _└n/5_┘ 집단의 중간값을 찾는 Select를 호출한다(T(n/5)). 3) 이 중간값을 피봇(pivot) x로 삼고, 원소를 분할(partitioning)한다(Θ(n)). 4) 최악의 경우 x보다 큰(작은) 원소가 ^┌5/2^┐·_└└n/5_┘/2_┘ = 3_└n/10_┘ ≥ n/4개 있으므로(n≥50) n - n/4 = 3n/4개에 대해 재귀호출을 하게 된다(T(3n/4)). 이상에서 T(n) = T(n/5) + T(3n/4) + Θ(n)이고, 강의노트를 참고해 점화식을 풀면 O(n)이 된다. 그런데 이때 집단을 5개가 아니라 3개로 나누면 어떻게 될까? 여전히 O(n)일까?

 

3개로 나눌 때 O 성능 분석

위의 1)에서 3개의 집단으로 나누고(Θ(n)) 2)에서 _└n/3_┚ 집단의 중간값을 찾으며(T(n/3)) 3)은 동일하다(Θ(n)). 4)에서 최악의 경우 x보다 큰(작은) 원소 ^┌3/2^┐·_└└n/3_┘/2_┘ = 2_└n/6_┘ 개에 대해 재귀호출을 한다. 이때의 성능이O(n)이라고 가정하고 추측확인법(guess & verify)을 적용해보자. n≥6일 때 2_└n/6_┘ ≥ n/6이므로, T(n) = T(n/3) + T(5n/6) + Θ(n) ≤ 1/3cn + 5/6cn + Θ(n) = 7/6cn + Θ(n) > cn이 되어 가정이 틀렸음을 알 수 있다. 즉, 3개의 집단으로 나누면 Select 알고리즘의 큰 특성인 선형 성능을 잃는다는 결론을 얻는다.

여기서 만약 O(n²)으로 가정하면 T(n) = 1/9cn² + 25/36cn² + Θ(n) = 29/36cn² + Θ(n) < cn²으로 가정을 만족한다. 더 근접한 상계를 찾기 위해 이번엔 O(n·lg n)이라 가정하면 T(n) = cn/3(lg cn – lg 3) + 5cn/6(lg cn + lg5 – lg 6) + Θ(n) = 7cn/6(lg cn) – cn/6(2lg3 - 5lg5 + 5lg6) + Θ(n) = 7/6cn(lg cn) + cn/6(lg9 – lg25 + lg7776) + Θ(n) > 7/6cn(lg cn) + Θ(n) > cn(lg cn)이므로 가정에 모순이다.

따라서 1<k≤2인 O(n^k)을 만족한다고 가정한다. 그리고 k를 1.1에서 0.1씩 높이며 대입해 나가면 1.4(소수점 자리를 늘리면 1.3725 정도)에서 최초로 가정이 만족되므로 O(n^1.4)을 찾게 된다.

IRC채널에 올라온 글을 읽던 도중 후배가 int main()와 void main()의 차이점을 물어보았다.

2학년때 C스터디를 진행할 때 이것땜에 곤란을 겪었던 적이 한번 있었는데, 그때는 설렁 설렁 넘어갔던 기억이 있다.

고급계산이론 과제를 하던 도중에 한번 쉬엄쉬엄 찾아볼까 해서 구글링을 해봤는데 알아낸 사실은 다음과 같다.

1. C99 이후의 표준 main 함수는 다음과 같아야 한다.

int main() 이거나
int main(int argc, char *argv[])

2. void main()에 비해서 int main()이 좋은 점은 종료 후 invoker(호출자)에게 해당 값을 넘겨준다. 이는 exit(); 함수와 같은 역할인듯 하다.

3. 다음과 같은 방법으로 바로 직전에 실행 되었던 프로그램이 반환한 값을 알 수 가 있었고, 실제로 넘겨준다는 것을 알 수 있었다.

다음과 같은 소스 코드를 작성한다.

#include <cstdio>

int main() {
        return 1;
}

컴파일 후 다음과 같이 해본다.

[libe@aslab libe]$ ./a.out
[libe@aslab libe]$ echo $?
1

근데 이것은 linux상에서 확인한 결과이고, 실제로 windows상에서는 어떤 방식으로 확인을 할 수 있을지 궁금하다(아시는 분께서 답변을 해주시면 감사하겠습니다.). 요사이 관심사 중에 하나가 run-time error 체킹을 쉽게 하는 방법에는 무엇이 있을까? 였는데, linux상에서 테스트 해본 결과 assert를 이용한 run-time error의 경우 138, segmentation fault의 경우 139라는 값을 확인 할 수 있었다. 생각 했던 것 보다 쉽다 ~_~

첨가 - windows의 경우
구글링을 해본 결과 Windows에서도 다음과 같은 batch file을 생성하면 확인을 할 수 있다.

@echo off
실행파일명
@if "%ERRORLEVEL%" == "0" goto good

:fail
    echo Execution Failed
    echo return value = %ERRORLEVEL%
    goto end

:good
    echo Execution Succeded
    echo return value = %ERRORLEVEL%
    goto end

:end

하지만 linux와 다른점은 assert()의 경우엔 얌전히 동작하는데, scanf("%d",a); 와 같은 코드에서 오류창을 띄운다음에 아마 메모리 주소로 추정되는 값을 내뱉는다-_-; 조금더 연구해봐야할 필요가 있을듯 싶다.

그런데 exit를 쓰면 void main()도 마찬가지의 기능을 할 수 있을텐데(테스트 결과도 마찬가지 였다.)  int main()의 좋은점이라고 하면 cstdlib헤더를 첨가 하지 않아도 된다는 점이라고 해야하나?