C/C++

[C언어와 알고리즘] 알고리즘 소개 (7)

OSS 2012-08-17 17:15:45 14249
2011


글: 정재준 (rgbi3307@nate.com ) / 커널연구회(www.kernel.bz)   2011-05-09


연재 차례
1. C언어 소개
2. 형태, 연산자, 표현
3. 제어 흐름
4. 함수와 프로그램 구조
5. 포인터와 배열
6. 구조체
7. 알고리즘 소개
8. 소팅을 통한 알고리즘 분석
9. 스택(Stack) 실습
10. 큐(Queue) 실습
11. 리스트(List) 실습
12. 트리(Tree) 실습
13. 해싱(Hash) 실습
14. 알고리즘 설계 및 분석기법
15. 진보된 알고리즘 소개






알 고리즘(Algorithms)은 잘 정의된 계산적인 절차이며 효율적인 절차를 통하여 입력 값들에서 출력 값들을 산출하는 방법이다. 또한 알고리즘은 입력을 출력으로 변환하는 일련의 계산단위를 기술하는 순서이며 잘 지정된 계산적인 문제를 해결하는 도구라는 관점으로 해석할 수도 있다. 계산적인 문제들은 입력과 출력간의 관계를 제시하고 알고리즘은 이렇게 제시된 입출력간의 관계를 계산적인 절차로 해석하여 적절한 해답을 산출한다.

예를 들어, 입력된 숫자들을 크기 순서대로 정렬하는 문제가 있다고 할 때, 이러한 정렬 문제의 입력과 출력간의 관계를 다음과 같이 기술할 수 있다.

입력 : 숫자 n개가 a1, a2, a3, ..., an 으로 나열됨.
출력 : 숫자 n개가 b1 <= b2 <= b3 ... <= bn 인 관계로 정렬됨.

입력 (n = 8개) : 31, 41, 59, 26, 15, 41, 12, 58
출력 (n = 8개) : 12, 15, 26, 31, 41, 41, 58, 59

정 렬은 컴퓨팅 분야에서 기본적인 필수 동작이며 많은 프로그램에서 정렬을 사용한다. 그동안 훌륭한 정렬 알고리즘들이 개발되어왔으며, 정렬 알고리즘의 효율성 평가는 정렬하고자 하는 대상의 개수와 분포에 따라 달라진다. 또한 메모리나 디스크와 같은 저장 장치의 종류에 의존한다.
각각의 입력에 대해서 올바른 출력 결과가 나온다면 해당 알고리즘은 정확하다고 말할 수 있다. 알고리즘은 영어로 표현할 수도 있고, 컴퓨터 프로그램 혹은 하드웨어 설계로도 기술할 수 있지만, 무엇보다 명확한 기술적인 절차를 통하여 주어진 문제를 해결하도록 표현하는 것이 중요하다.
필자는 C언어 프로그램을 통하여 알고리즘을 표현한다. 또한 데이터 구조(Data Structure)에 대해서도 실습하도록 내용을 구성한다. 데이터 구조는 데이터를 저장소에 보관(구성)하는 방식이며 이것에 접근하는 방법(입력, 수정, 삭제)은 알고리즘으로 기술하므로 데이터 구조와 알고리즘은 서로 밀접하게 연관되어 있다. 앞으로 C언어 코드를 통하여 이들을 상세히 실습해 보도록 하자.

다양한 알고리즘들을 실습하기 전에 선행 학습해야 하는 몇 가지 중요한 C언어 코딩기법들이 있는데, 반복(Loop), 재귀(Recursion), 포인터(Pointer)이다. 이들은 알고리즘을 C언어로 코딩 할 때 필수적으로 등장하는 것이므로 선행학습 하는 것이 필요하다.

반복(Loop)
C언어에서 반복을 수행하는 제어문으로 for, while, do가 있다. 이들은 모두 반복을 수행하기 위한 제어변수를 가지고 있으며 제어변수의 초기값, 증감, 종료 판단에 따라 반복회수가 결정된다.
알고리즘에서 반복이 수행되는 회수는 중요한 수치이며, 알고리즘의 수행시간은 반복 회수에 비례하므로 반복 회수를 줄이면 알고리즘의 효율성은 증가한다. 먼저 for문으로 작성된 다음의 C언어 코드를 보자.

위 의 코드에서 바깥쪽 for 반복문의 제어변수 i가 0, 1, 2, 3, ..., n-1까지 증가하면서 n번 반복하는 동안 안쪽 for 반복문의 제어변수 j 또한 0, 1, 2, 3, ..., n-1까지 증가하면서 n번 반복되므로, 반복회수는 바깥쪽 반복문(제어변수 i)의 반복회수에 안쪽 반복문(제어변수 j)의 반복회수를 곱한 값이 된다. 즉, n=8 이라면, ucnt = n * n = 8 * 8 = 64, 반복회수는 64가 된다.

그럼,오른쪽의 C언어 코드를 보자.
코 드에서 바깥쪽 for 반복문의 제어변수 i가 0, 1, 2, 3, ..., n-1까지 n번 반복하는 동안 안쪽 for 반복문의 제어변수 j는 i값으로 초기화 되므로, 안쪽의 반복회수는 n에서 i값을 뺀 만큼 반복된다. 즉, n=8 이라면, 바깥쪽 for문이 8번 반복되는 동안 안쪽 for문은 (8-i)만큼 반복되므로 전체 반복회수는 8번+7번+6번+5번+4번+3번+2번+1번이 된다. 이것은 수학적으로 1에서 8까지의 수를 각각 더한 값이 되므로 ucnt = n(n+1)/2 = 8(8+1)/2 = 36, 반복회수는 36이 된다.

다음으로, 아래의 C언어 코드를 보자.

위 의 코드에서 바깥쪽 for 반복문의 제어변수 i가 0, 1, 2, 3, ..., n-1까지 n번 반복하는 동안 안쪽 for 반복문의 제어변수 j는 1, 2, 4, 8, ..., n까지 2의 급수 만큼 증가한다. 즉, n=8 이라면, 바깥쪽 for문이 8번 반복되는 동안 안쪽 for문은 4번 반복되므로 ucnt = n(lg(n)+1) = 8(3+1) = 8 * 4 = 32, 반복회수는 32가 된다.

다음으로, 아래의 C언어 코드를 보자.


위 의 코드에서 바깥쪽 for 반복문의 제어변수 i가 0, 1, 2, 3, ..., n-1까지 n번 반복하는 동안 안쪽 for 반복문의 제어변수 j는 n, n/2, ..., 8, 4, 2, 1까지 2로 나눈 만큼 감소한다.  즉, n=8 이라면, 바깥쪽 for문이 8번 반복되는 동안 안쪽 for문은 4번 반복되므로 ucnt = n(lg(n)+1) = 8(3+1) = 8 * 4 = 32, 반복회수는 32가 된다.

재귀(Recursion)

재귀(Recursion)도 반복 실행되는 것이다. for문과 같은 루프는 for문 하단에 지정된 블록 안의 명령문을 반복 수행하는 것에 비해서, 재귀는 호출한 함수 내부의 전체 코드를 또 다시 수행한다. 재귀는 호출 조건을 만족하면 해당 함수를 계속 호출한다.

함수를 재호출 할 때마다 이 함수에서 사용되는 내부 변수들은 메모리(스택)에 순서대로 적재되고, 호출한 함수로 다시 복귀하는 주소 또한 관리된다. 재귀는 함수 내부변수들과 복귀주소를 추가적인 메모리로 관리해야 하는 부담이 있지만(이것은 컴파일러가 생성한 내부 코드에서 처리됨), 해당 함수의 코드들을 재사용할 수 있어서 프로그램 코드가 함축적으로 짧아지는 장점이 있으므로 알고리즘에서 많이 사용한다.

 또한, 알고리즘상 동일한 논리를 반복적으로 수행하는 것이 많으므로 재귀를 이해하는 것은 중요하다. 다음의 C언어 코드를 통하여 함수의 재귀호출 실행을 이해해보자.

위 의 코드는 loop05 함수의 내부변수인 n를 하나씩 감소시키면서 (n > 0) 조건을 만족하면 loop05 함수를 재귀적으로 호출한다. 즉, n = 8이 loop05 함수에 전달되면 내부변수 n은 8, 7, 6, ... , 2, 1까지 하나씩 감소되면서 8번 loop05 함수를 재귀호출한다.  n의 값이 0이 될 때 재귀 호출은 종료되면서 호출된 위치로 반복하여 복귀된다. 따라서 반복회수를 계산하는 ucnt 변수의 값은 8이 된다.

그럼, 아래의 C언어 코드를 보자.

좌 측 하단의 코드는 loop06 함수의 내부변수인 n를 하나씩 감소시키면서 (n > 0) 조건을 만족하면 loop06 함수를 각각 2번씩 재귀 호출한다.  즉, n = 8이 loop06 함수에 전달되면 내부변수 n은 8, 7, 6, ... , 2, 1까지 하나씩 감소하면서 loop06 함수를 각각 2번씩 호출하므로 반복회수는 2의 급수 형태로 증가한다. 따라서 반복회수 ucnt = 2의 8승 - 1 = 256 - 1 = 255가 된다.

다음으로, 아래의 C언어 코드를 보자.

위 의 코드는 loop07 함수의 내부변수인 n를 2로 나누어 감소시키면서 (n > 0) 조건을 만족하면 loop07 함수를 각각 2번씩 재귀 호출한다.  즉, n = 8이 loop07 함수에 전달되면 내부변수 n은 8, 4, 2, 1 (4번)으로 감소하면서 loop07 함수를 각각 2번씩 호출하므로 반복회수는 2의 급수 형태로 증가한다.  따라서 반복회수 ucnt = 2의 4승 - 1 = 16 - 1 = 15가 된다.

지금까지 알아본 반복과 재귀함수의 반복회수를 테이블로 정리하면 다음과 같다.

위 의 테이블에서 비용순위는 반복회수가 작은 것에서 큰 순서대로 정했다. 알고리즘에서 반복회수는 실행시간과 밀접하게 연관된다. 반복회수가 작으면 실행시간이 적게 걸려서 알고리즘의 효율성이 좋아지고, 반복회수가 크면 실행시간이 오래 걸려서 알고리즘의 효율성은 나빠진다. 즉, 반복회수와 실행시간(알고리즘 효율성)은 비례관계에 있다. 따라서 위의 테이블에서 비용순위는 알고리즘 효율성이 좋은 순서라고 볼 수 있다. 자세히 분석해 보면 반복(Loop)에서는 루프의 제어변수 증감 크기에 따라서 반복회수가 많은 영향을 받고, 재귀(Recursion)에서는 호출하는 회수가 중요한 요소이다. 특히, 재귀는 호출하는 회수(호출 깊이)에 따라서 각각 반복되는 개수가 기하 급수적으로 증가한다. 그러므로 재귀호출은 알고리즘에서 아주 중요한 부분을 차지한다.

알고리즘에서 재귀호출은 코드의 함축성을 높여서 코드길이를 짧게 해줄 수 있으나 재귀호출의 회수(호출 깊이)가 커지면 알고리즘의 실행 시간(비용)이 기하급수적으로 증가한다. 재귀호출의 이러한 양면성 때문에 이것의 특징을 잘 살려서 활용하는 것은 무엇보다 중요하다.

다음의 그래프는 입력 자료수 n과 알고리즘 효율성(실행시간)간의 상관관계를 표현한 것이다.

 재귀호출의 특성을 잘 활용한 예제로 최대공약수를 계산하는 코드와 피보나치 수열을 출력하는 예제가 있다. 아래에서 이들의 프로그램 코드를 통하여 실습해 보기 바란다.

 
위의 코드가 실행되는 과정을 그림으로 설명하면,

포인터(Pointer)

컴 퓨터 메모리는 일련번호가 매겨진 주소로 관리된다. 메모리에 접근하기 위해서 이러한 주소를 사용하는데, 포인터는 메모리 주소를 보관하고 있는 변수이다. 따라서, C언어는 포인터 변수에 보관되어 있는 주소를 통하여 메모리에 접근하며 메모리에 있는 데이터들을 효율적으로 관리하기 위해서는 적절한 포인터 변수를 사용해야 한다.

C언어는 변수, 함수, 구조체와 같은 자료들을 포인터에 담아서 관리할 수 있다. 특히, 함수는 전역적인 자료형의 일종으로 포인터를 통하여 변수처럼 전달 및 호출할 수 있다. 이러한 특징을 활용하면 프로그램 코드를 좀더 효율적으로 작성할 수 있다.

다음의 C언어 코드를 통하여 함수 포인터를 실습해보자.

위 의 C언어 코드는 함수의 파라미터로 2개의 값을 전달 받아서 2개중 큰 값을 출력하는 것이다. 이것을 판단하는 함수가 void* larger (void* ptr1, void* ptr2, int (*pfn_compare)(void*, void*)) 이다. 여기서 3번째 파라미터인 int (*pfn_compare)(void*, void*) 는 함수 포인터 이다. 이러한 함수 포인터를 사용하는 이유는 여러 개의 함수를 쉽게 호출하기 위함이다. 2개의 값을 비교할 때, 비교 대상의 자료형이 정수형이나 실수형일 수 있다. 정수형 값을 비교하는 함수(compare_int )와 실수형 값을 비교하는 함수(compare_float)를 각각 작성하고 이것을 larger 함수의 매개변수인 함수 포인터로 전달하면, 입력 자료형이 정수형인지 실수형인지 판단하는 if 문 없이도 함수 포인터를 통하여 호출할 수 있는 장점이 있다.

맺음말
필자는 이번 연재에서 C언어로 알고리즘을 이해하기 위해서 필수적으로 선행 학습해야 하는 반복(Loop), 재귀(Recursion), 포인터(Pointer)에 대해서 기술했다. 이것들은 알고리즘을 효율적으로 코딩 하기 위해서 필요한 핵심 요소들 이므로 잘 익혀 두도록 하자. 다음 연재부터 알고리즘들이 본격적으로 기술되니 독자 여러분들의 꾸준한 관심 있기를 바란다.


필 / 자 / 소 / 개

(정 재준) 필자는 학창시절 마이크로프로세서 제어 기술을 배웠고, 10여년동안 쌓아온 IT관련 개발 경험을 바탕으로 “오라클실무활용SQL튜닝(혜지원)” 책을 집필하고, “월간임베디드월드” 잡지에 다수의 글을 기고하였다.  서울대병원 전산실에서 데이터베이스 관련 일을 하면서 학창시절부터 꾸준히 해온 리눅스 연구도 계속하고 있다.  특히, 스탠포드대학교의 John L. Hennessy 교수의 저서 “Computer Organization and Design” 책을 읽고 깊은 감명을 받았으며, 컴퓨터구조와 자료구조 및 알고리즘 효율성 연구를 통한 기술서적 집필에 노력하고 있다.  또한, 온라인 상에서 커널연구회 (http://www.kernel.bz/ )라는 웹사이트를 운영하며 관련기술들을 공유하고 있다.


※ 본 내용은 (주)테크월드(http://www.embeddedworld.co.kr)의 저작권 동의에 의해 공유되고 있습니다.
Copyright ⓒ
Techworld, Inc. 무단전재 및 재배포 금지

맨 위로
맨 위로