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

2. 반복 알고리즘

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

 

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

 

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

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

    sum:= 0

    반복(index:=start->end)

        sum := sum+index

    반환 sum

 

위 알고리즘은 반복할 때마다 index값이 start에서 end까지 순차적으로 증가하죠. 이처럼 반복문을 수행할 때마다 변하는 성질을 루프 변성이라 말합니다.

 

그리고 sum은 반복문을 몇 번 수행하든지 언제나 start에서 현재 index까지의 합계를 갖죠. 이처럼 반복문의 루프를 몇 번 수행하더라도 변하지 않는 성질을 루프 불변성이라 불러요.

 

위 알고리즘은 루프 변성에 의해 index값이 end까지 변하고 루프 불변성에 의해 반복문을 모두 수행하고 나면 sum에는 start에서 end까지의 합을 갖습니다. 이처럼 반복 알고리즘에서는 루프 변성과 루프 불변성을 이용하여 알고리즘이 타당(correct)함을 증명할 수 있어요.

 

이처럼 문제를 해결할 수 있다는 것을 증명하였으면 코드로 표현할 준비가 끝나다고 볼 수 있어요. 물론 자주 프로그래밍을 하다 보면 이와 같이 증명하지 않고 바로 구현할 수도 있겠죠. 그리고 개발 도구의 디버깅 기능을 사용하여 논리적 버그를 잡을 수도 있어요. 자신이 작성할 문제의 알고리즘이 타당하다는 것을 증명하고 구현하는 습관할 수 있다면 좋을 거예요. 물론 구현하고 난 이후라도 자신이 작성한 코드가 타당함을 증명하는 것도 아무 것도 하지 않는 것보다는 좋은 습관이겠죠.

 

이 책에서는 C++로 알고리즘을 코드로 표현할 거예요. 여러분께서는 눈으로 보고 머리로 이해하는 것에 만족하지 마세요. 컴퓨터 프로그래밍은 컴퓨터와 대화하는 작업이며 이를 통해 발생하는 다양한 에러를 파악하고 이를 수정하면서 경험적 노하우를 얻는 것이 매우 중요합니다.

 

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

int GetSumAToB(int start,int end);

 

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

 

테스트를 할 때 assert 함수나 try catch, throw를 사용하여 빠르게 확인하는 습관을 가지세요.

 

assert 함수는 입력 인자의 표현이 거짓이면 프로세스가 멈추고 어느 소스 파일의 몇 번째 라인에서 문제가 있는지 알려줍니다.

 

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

GetSumAtoB 함수의 테스트 로직은 다음처럼 작성할게요.

int main()

{

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

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

    cout<<"GetSumAToB 테스트성공"<<endl;

    return 0;

}

 

이제 GetSumAToB를 구현하세요. 만약 논리적 버그가 있다면 앞에 그림처럼 오류 창이 뜰 거예요.

int GetSumAToB(int start,int end)

{   

    int sum = 0; //sum:= 0

    for(int index = start;index<=end;++index) //반복(index:start->end)

    {

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

    }

    return sum;//반환sum

}

 

▷코드

#include <assert.h>

#include <iostream>

using namespace std;

int GetSumAToB(int start,int end);

int main()

{

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

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

    cout<<"GetSumAToB 테스트성공"<<endl;

    return 0;

}

int GetSumAToB(int start,int end)

{   

    int sum = 0; //sum:= 0

    for(int index = start;index<=end;++index) //반복(index:start->end)

    {

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

    }

    return sum;//반환sum

}