한빛출판네트워크

작성: 한동훈(traxacun at unitel.co.kr)

작성일: 2003. 2. 27

분할의 세계

일상 생활에서도 복잡한 문제를 잘게 나누어서 작은 것 부터 해결하라고 이야기한다. 아주 복잡한 문제도 작은 범위로 나누다보면 해결할 수 있는 작은 문제가 된다. 컴퓨터 세계에서도 이러한 방법이 그대로 적용된다. 프로그래밍을 하면서 접하게 되는 많은 문제들이 이 분할의 세계에서 해결된다. 많은 책들에서는 이것을 "분할 정복(Divide and Conquer)"이라고 얘기한다.

문제를 작게 나누어 처리하는 것은 컴퓨터 세계에서 종종 루프를 반복하게 되는 일이며, 이러한 코드들은 대개 재귀 호출의 형태로 나타난다. 재귀 호출은 "빠르고 구현하기 쉽다"라는 장점을 갖고 있는 반면에 재귀의 단계가 깊어질수록 이전 단계에 대한 정보를 계속해서 일정한 저장소 즉, 스택(Stack)에 쌓아두어야한다. 스택이 담을 수 있는 크기를 넘어버리면 컴퓨터세계를 늘 배회하는 "스택 넘침(Stack Overflow)"의 유령을 만나게 된다. 그래서 상용 응용 프로그램을 작성하는 경우에 개발이 끝나고 최적화를 하는 단계에서 재귀를 비재귀로 바꾸게 된다.

"분할 정복"과 "재귀와 비재귀"는 한 형제와 같기 때문에 함께 소개한다.

피보나치 수열

재귀와 비재귀를 설명할 때 반드시 등장하는 예제로는 피보나치 수열, 하노이 탑, 팩토리얼, 승수(Power) 문제가 있으며, 이 중에서 설명하기 간결하다는 이유로 피보나치 수열을 소개한다.(또 다른 문제는 일일이 C# 소스 코드를 작성할 여력이 없는 이유도 있다.)

피보나치 수열은 다음과 같은 수열이다.

0 1 1 2 3 5 8 13 21 34 55 ...

피보나치 수열의 정의는 다음과 같다.

소스 코드는 재귀 버전과 비재귀 버전 두 가지가 있으며 의미있는 비교를 하기 위한 코드를 추가한 탓에 다소 산만해 보일 수 있다.

그림2. 피보나치 수열 재귀 버전

그림3. 피보나치 수열 비재귀버전

두 버전 모두 사용법은 동일하다.

fibo.exe 0

fibo.exe 1

fibo.exe 5

fibo.exe 700

위와 같은 형태를 사용하여 n 번째 원소의 값을 구할 수 있으며 각각의 실행시간이 출력되기 때문에 유용한 비교가 될 것이다. 각 프로그램의 첫번째 실행은 IL 코드에서 원시(native) 코드로 컴파일되는 시간이 있으므로 두번째 실행부터 시간을 비교하면 구현에 따라 시간 차이가 얼마나 벌어질 수 있는지 알 수 있을 것이다. 정확한 시간 측정을 원하는 내 주위 사람들 중에는 DateTime 클래스에서 틱(Tick) 카운트를 구하는 것도 많은 시간이 걸리기 때문에 이러한 시간을 고려해서 알고리즘을 개선해야 한다고 하지만 그 차이가 미미하기 때문에 무시하고 있다.(내 주위에는 실제로 이 시간도 고려해서 알고리즘을 개선해서 시간을 측정하는 분들이 있긴 있다.)

P-III 800Mhz에서 40번째 원소를 구하는데 재귀 버전은 143306064 틱이지만 비재귀 버전은 0 틱으로 출력이 된다.(보다 정확한 시간 측정을 위해서 코드를 개선할 필요가 있군...) - 40번째 원소의 값이 재귀와 비재귀 모두 동일한 값인지 비교하기 바란다.

50번째 원소 이후의 값을 구하는데 있어서는 비재귀 버전은 곧 바로 답을 구하지만 비재귀 버전은 30초를 기다려도 답이 없다는 것을 알게될 것이다.

재귀 버전이 갖는 문제점은 다음과 같다.

즉, 2의 49승에 해당하는 계산을 수행해야만 결과를 알 수 있게 되며, f(50)에서 내려가는 f(49)와 f(48)은 다시 f(50)으로 돌아가기 위한 정보를 알고 있어야 하기 때문에 메모리 낭비도 크다는 것을 알 수 있다.

이분 검색(Binary Search)

이분 검색은 정렬된 데이터에서 원하는 데이터를 찾기 위해 구간을 항상 두 부분으로 나눈다. 분할 정복의 큰 특징은 문제를 작게 나누어도 처리하는 연산은 거의 같다는 것이다.

이분 검색 알고리즘은 다음과 같이 구현한다.

1. 첫 구간과 끝 구간의 중간에 있는 데이터를 구한다.

2. 데이터와 찾으려는 값을 비교해서 같으면 검색이 끝난다.

3. 중간값 > 찾으려는 값: 왼쪽 구간을 선택하여 1로 돌아간다.

4. 중간값 < 찾으려는 값: 오른쪽 구간을 선택하여 1로 돌아간다.

이분 검색은 데이터를 순서대로 비교하는 "순차 검색(Sequential Search)"와 달리 구간을 둘로 나누어 해결하는 것만으로도 알고리즘 수행시간이 비약적으로 개선된다는 것을 보여준다. 순차 검색이 데이터 수에 따른 수행시간이 O(N)이라면 이분 검색의 수행시간은 O(logN)의 수행시간을 갖는다.

이분 검색은 독자가 직접 작성해 보기 바라며, 대부분의 코드가 그러하듯이 한 번의 루프마다 최소한 두 번의 비교를 수행하는 코드가 될 것이다.

여기에 소개하는 코드는 루프마다 한 번의 비교를 수행하도록 개선한 변형된 버전이다. 자신이 직접 구현한 것과 비교하는 것이 더 좋을 것이다.

그림5. BinarySearch 클래스

그림6. Tester 클래스

배열로 선언된 array에는 Sort() 메서드가 있으므로 정렬된 형태로 데이터를 추가할 필요는 없다. Random 클래스를 사용하여 임의의 데이터를 생성한 다음에 수행시간을 비교해보는 것도 좋을 것이다. 검색값으로 배열의 마지막 값인 104를 넣은 것은 알고리즘의 특성상 구간의 첫번째와 마지막에 있는 값을 검색하는 데에 가장 많은 수행시간이 걸리기 때문이다.

이분 검색을 자신의 프로그램에 사용하려 한다면 데이터 분포가 고르지 않은 경우도 대비해야하며, 범용적으로 사용할 수 있도록 개선할 필요가 있다. 대리자(delegate)를 사용하는 것도 좋은 방법이며 닷넷 프레임워크의 IComparable, IComparer 인터페이스를 구현하는 것도 고려해야할 것이다.

닷넷 프레임워크에서 사용하는 모든 배열은 System.Array 클래스를 상속하고 있으며, 이 클래스에는 Sort() 메서드와 함께 BinarySearch() 메서드가 제공된다. 크기를 바꿀 수 있는 배열은 System.ArrayList 클래스를 상속하고 있으며, 이 클래스에도 BinarySearch() 메서드가 제공된다.

이분 검색은 이미 정렬된 데이터에서 데이터를 검색하는 데 가장 좋은 알고리즘이며, 여기에도 "분할 정복"이 적용되어 있다.

정렬에서 분할 정복이 사용되는 예로는 병합 정렬(Merge Sort)과 퀵 정렬(Quick Sort)을 들 수 있다. 대부분의 정렬 알고리즘이 메모리 내부에서 수행되는데 메모리에 모두 저장하기에는 큰 데이터가 디스크에 저장되어 있는 경우에 병합 정렬을 사용한다. - 정렬할 데이터를 메모리에 두느냐, 디스크에 두느냐에 따라 내부 정렬(Internal Sort)과 외부 정렬(External Sort)로 구분하기도 한다. - 병합 정렬은 10M의 큰 데이터가 있다면 이것을 1M씩 10개로 나누어 정렬한 결과를 10개의 데이터로 저장하고, 다시 하나로 합치면서 정렬된 상태를 유지한다. 퀵 정렬은 하나의 기준 값을 중심으로 구간을 작게 나누어 정렬하며 모든 재귀가 끝났을 때는 전체가 정렬된 상태가 된다. 퀵 정렬은 가장 널리 사용되고 있으며 닷넷 프레임워크의 Sort() 메서드 구현에도 사용되었다.

행렬 연산에도 분할 정복이 쓰인다. 3D 환경의 프로그래밍은 많은 행렬 연산을 요구하며 행렬 연산의 알고리즘 수행시간은 행렬의 특성상 매우 높다. N * N 행렬을 2 * 2 행렬까지 잘게 나누어 계산하고 적절히 더하고 빼는 것으로 수행시간을 개선시킬 수 있다. 관심있는 분들은 Volkner Strassen의 행렬 곱셈에 대해서 찾아보기 바란다.

재귀에서 비재귀로의 탈출

중첩되지 않은 재귀에서 비재귀로의 변환은 비교적 쉽지만, 중첩된 구조를 갖는 재귀에서 비재귀로 바꾸는 것은 어렵다. 하드 디스크내에 특정 파일을 검색하는 검색 프로그램의 경우 중첩된 구조를 갖는 재귀로 구현된 경우가 대부분이지만 방대한 하드 디스크 내를 검색하는 데에는 적합하지 않다. 파일 검색 프로그램을 비재귀로 바꿔보는 것이 비재귀 변환에 대한 좋은 출발점이 될 것이다.

중첩된 재귀를 비재귀로 바꾸는 것은 알고리즘을 이해하고 비재귀로 새롭게 작성하게 되며, 많은 프로그래머들이 공통적으로 이용하는 방법은 탐색 단계동안 데이터를 유지하기 위해 스택과 같은 자료구조를 추가로 사용하는 것이다. 구조안에 두 개의 재귀호출이 있는 경우에 어느 부분에서 처리를 하느냐에 따라서 비재귀로 작성하는 방법이 달라지게 된다. 파일 검색 프로그램에 대한 소스는 인터넷에 많이 있으며 대부분 재귀 호출로 되어 있다. 여러분의 마음에 드는 소스를 골라서 비재귀로 바꿔보기 바란다. 프로그래밍 경험이 있는 분들은 보통 1일, 처음 알고리즘을 접하는 분들은 2-3일 정도의 시간이 걸리는 것을 보았다.( 과제아닌 과제? )

마치며

새로 배운 사람들은 새로운 용어를 쓰게 되고, 이전에 배운 사람들은 이전에 배운 용어를 쓰게 된다. 용어는 익숙해지기 나름이라 생각하지만 자꾸 쓰던 용어에 정이가는 것도 사실인 것 같다. "재귀와 비재귀"는 다른 말로 "반복과 비반복"과 같은 용어로도 소개된다.

대부분의 알고리즘 책에 소개된 알고리즘이나 실제로 프로그래밍을 하면서 부딪치게 되는 문제들 중에 분할 정복을 사용하게 되는 경우가 많으며, 프로그래머로의 시작이 재귀를 비재귀로 바꾸는 일이라는 것을 알게 될 것이다.

C# 버전으로 많은 알고리즘을 작성하여 소개했으면 좋겠으나 대부분의 경우 다른 언어로 작성된 코드를 이해하고 C#으로 작성할 수 있을 것이다. 필자도 뛰어난 실력을 갖고 있는 사람이 아니니 일상 속에서 모든 알고리즘을 구현하여 소개하는 것은 힘든 일이다. 게다가 기존의 C/C++, Pascal의 스타일을 벗어나 C#과 .NET에 맞는 제대로 된 코드를 소개하고 싶은 나 자신의 욕심을 생각해보면 많은 코드를 소개하기는 어려울 듯하다.( 전업 저자라거나 테크니컬 라이터가 직업이라면 가능한 일이겠지만... )

디자인 패턴만 계속 소개하는 것도 지루한 듯하여 이런 저런 주제들을 섞어가며 계속해서 올라가는 형태가 될 것이다.

내용은 가볍게 썼지만 독자가 알고리즘에 대해서 모르거나 구현해 보고 싶다면 다양한 자료를 책과 인터넷에서 뒤적이며 많은 시간을 들여야할 것이다. 독자가 구현한 코드를 다른 사람들과 공유하고 싶다면 필자의 이메일 주소로 소스 코드를 보내주기 바란다.

참고자료

알고리즘과 자료구조는 각 도서 판매 사이트에 가면 많은 책들이 여러분을 기다리고 있다. 그 중에서 독자에게 쉬운 책 또는 맞는 책을 골라보기 바란다. 다양한 알고리즘을 접하는 데 흥미가 있다면 Algorithms in C++, Addison Wesley를 찾아보기 바라고, 깊이있는 해석과 구현을 맛보고자 한다면 The Art Of Programming Volume 1, 2, 3를 보기 바란다. 이 외의 다른 책들은 자신의 필요에 따라 선택할 문제다.