[디딤돌 자료구조와 알고리즘 with C] 2. 반복 알고리즘

2. 반복 알고리즘

 

 문제를 해결하는 다양한 방법 중에서 반복적인 방법으로 문제를 해결하는 것은 매우 흔합니다. 이번 장에서는 반복적인 방법으로 문제를 해결하는 반복 알고리즘을 다룹니다. 특히 반복 알고리즘으로 어떠한 문제를 해결할 수 있다는 것을 증명하기 위해서는 어떠한 특징을 고려해야 하는지 살펴볼 것입니다.

 

2. 1 루프 변성과 루프 불변성

 반복 알고리즘으로 어떠한 문제를 해결할 수 있는지 증명할 때는 루프 변성과 루프 불변성을 이용합니다. 루프 변성은 반복문을 수행하면서 변하는 성질이며 루프 불변성은 변하지 않는 성질을 말합니다.

 

 예를 들어 정수 start에서 end 사이의 합계를 구하는 문제가 있다고 가정합시다. 이 문제는 다음과 같은 방법으로 해결할 수 있습니다.

 

특정 범위의 합계 구하기(start:시작 값, end: 끝 값)

    sum:= 0

    반복(index:=start; index<=end; index:=index+1)

        sum := sum+index

    반환 sum

 

 위 알고리즘은 반복할 때마다 index값이 변하므로 index 값이 변하는 성질은 루프 변성입니다. sum은 언제나 start에서 현재 index까지의 합계를 갖습니다. 이러한 성질을 루프 불변성이라 부릅니다. 위의 알고리즘에서는 index 값이 end까지 변하는 루프 변성과 sum이 start에서 index까지의 합계를 갖는다는 루프 불변성으로 타당한(correct) 알고리즘 전개임을 증명할 수 있습니다.

 

 이처럼 문제를 해결할 수 있다는 것을 증명하였으면 코드로 표현할 준비를 갖춘 것입니다. 이 책에서는 C언어를 이용해 알고리즘을 코드로 표현할 것입니다. 컴퓨터 프로그래밍은 컴퓨터와 대화하는 작업입니다. 따라서 반드시 코드로 표현하여 제대로 동작하는지 확인하는 과정을 생략하지 마십시오.

 

 알고리즘을 학습할 때 머리로 이해하고 넘어가는 것만 반복하면 실질적인 프로그래밍 능력이 균형있게 발전하지 못 할 수 있습니다.

 

 알고리즘을 프로그래밍 언어를 이용하여 코드로 표현하다보면 오탈자가 생기거나 문법적인 부분에 문제가 있어 컴파일 오류가 발생하거나 혹은 알고리즘이 정확하지 않아 논리적 버그가 발생할 수 있습니다. 여러분은 이러한 컴파일 오류를 수정하고 논리적 버그를 잡는 등의 작업을 통해 기본적인 프로그래밍 경험적 기술을 쌓을 수 있을 것입니다.

 

 

 

 여러분께서 알고리즘을 전개하였으면 이제 코드로 표현하는 것을 시작합시다. 먼저 함수 이름과 원형(입력 매개변수 리스트와 리턴 형식)을 결정합시다.

int GetSumAToB(int a,int b);

 

 그리고 테스트 로직을 정의합니다. 많은 개발자들은 구현한 이후에 테스트 로직을 구현하여 테스트를 하거나 테스트 과정을 생략하는데 이는 매우 위험한 습관입니다. 우리가 전개한 알고리즘이나 구현한 결과물에 문제가 있을 때 이를 얼마나 빠르게 인지하여 수정하는가는 전체 개발 비용에 중요한 영향을 끼칩니다.

 

 C언어에서 테스트를 할 때 assert 함수는 매우 유용합니다. assert 함수는 입력 인자의 표현이 거짓이면 프로세스가 멈추고 어느 소스 파일의 몇 번째 라인에서 문제가 있는지 알려줍니다.

 

 예를 들어 assert(3<2); 코드를 만나면 입력 인자로 전달한 표현이 거짓이므로 프로세스는 멈추고 문제가 있는 코드가 어느 파일의 몇 번째 라인인지 알려줍니다.

 

[그림 2.1] assert 함수에 입력 인자가 거짓일 때의 실행 화면

 

 GetSumAtoB 함수의 테스트 로직은 다음처럼 작성할게요. 여기에서는 어떠한 공정으로 학습하는지를 보여주는 것이며 앞으로 여러분께서 알고리즘을 학습할 때 적절한 테스트 로직을 작성하세요.

#include <assert.h>

#include <stdio.h>

void TestGetSumAToB()

{

    assert(GetSumAToB(1,10)==55);

    assert(GetSumAToB(5,10)==45);

    printf("GetSumAToB 테스트성공\n");

}

 

 이처럼 테스트 로직을 만들고 난 후에 GetSumAtoB 함수를 작성하면 논리적 버그가 있으면 [그림 2.1]처럼 테스트 로직이 있는 소스 파일과 라인 수를 출력하고 프로세스는 이 후 구문을 수행하지 못합니다. 만약 논리적 버그가 없다면 GetSumAToB 테스트 성공 구문을 볼 수 있겠죠.

 

 

 이제 GetSumAToB를 구현합니다.

int GetSumAToB(int a,int b)

{

    int index = 0;

    int sum = 0; //sum:= 0

    for(index = a;index<=b;++index) //반복(index:=start;index<=end;index:=index+1)

    {

        sum += index; //sum := sum+index

    }

    return sum;//반환sum

}

 

▷코드

특정 범위의 합계 구하기.c

//특정 범위의 합계 구하기

#include <assert.h>

#include <stdio.h>

int GetSumAToB(int a,int b)

{

    int index = 0;

    int sum = 0; //sum:= 0

    for(index = a; index<=b; ++index)//반복(index:=start; index<=end; index:=index+1)

    {

        sum += index; //sum := sum+index   

    }

    return sum;//반환 sum

}

void TestGetSumAToB()

{

    assert(GetSumAToB(1,10)==55);

    assert(GetSumAToB(5,10)==45);

    printf("GetSumAToB 테스트 성공\n");

}

int main()

{

    TestGetSumAToB();       

    return 0;

}