인사이트에서 번역 출간하여 개발자들에게 좋은 평가를 받고 있는 책인 "생각하는 프로그래밍"을 시간이 날 때마다 짬짬이 보고 있습니다. 주된 내용은 이미 학부때 배운 것들이지만, 10여년의 시간이 지난 지금 다시 읽어보면 감회가 새롭답니다. 덕분에 알고리즘 관련 책들을 다시 뒤적이게 됩니다.
이 책에는 프로그래밍과 관련된 다양한 내용들이 나옵니다. 총 3부에 걸쳐 15개의 컬럼을 다루고 있는데요, 오늘 다룰 내용은 8번째에 소개되고 있는 "알고리즘 디자인 기법"입니다. 자세한 내용은 책을 참고하시기 바라며, 여기서는 해당 내용을 실제로 구현해보도록 하겠습니다.
풀고자 하는 문제는 다음과 같습니다.
"입력은 n개의 부동소수점 수로 이루어진 벡터 x이고, 출력은 입력된 벡터에 대한 연속적인 부분 벡터 각각의 합 중 최대값이다.(이를 최대합이라 한다)."
즉, 연속된 숫자의 합이 최대가 되는 부분을 찾는 문제입니다. 여기서는 문제를 간단히 하기 위해 정수만을 다루도록 합니다. 책에서는 모두 5가지의 알고리즘을 소개하고 있습니다. O(n^3) 에서부터 O(n)에 이르는 다양한 해법이지요. 자료구조(DS)나 알고리즘을 배우신 적이 있으시다면 O 표기법에 대해 잘 아시리라 믿습니다. 결론적으로 O(n)으로도 문제를 풀수 있고, 프로그램도 무척이나 간단합니다.
책에 나와 있는 코드는 아래와 같습니다.
maxsofar = 0
maxendinghere = 0
for i=[0,n)
maxendinghere = max(maxendinghere + x[i], 0 )
maxsofar = max( maxsofar, maxendinghere)
무척이나 간단하죠? 그리고 실제로도 너무나 잘 동작한답니다. 이를 C 코드로 바꾸는 것은 식은 죽 먹기보다 쉬울 것입니다.
그런데, 위의 코드는 단지 최대합만을 표시해줍니다. 어디서부터 어디까지를 더해서 나온 값이라는 부분이 없죠. 그래서 조금 바꾸어보았습니다.
for(i=0;i<ARRAY_LENGTH;i++)
{
/*
maxendinghere = max( maxendinghere + x[i], 0);
maxsofar = max(maxsofar, maxendinghere);
*/
if( maxendinghere + x[i] > 0 )
{
maxendinghere = maxendinghere + x[i];
end_here = i;
} else
{
maxendinghere = 0;
start_here = i+1;
}
if( maxsofar < maxendinghere )
{
maxsofar = maxendinghere;
start_sofar = start_here;
end_sofar = end_here;
}
}
위의 코드에서 start_sofar, end_sorfar에 최대합을 이루는 부분의 시작과 끝 값이 들어가게 됩니다.
책에 보면 다음과 같은 10개의 연속값이 있습니다.
31, -41, 59, 26, -53, 58, 97, -93, -23, 84
이에 대해 위의 코드를 적용해서 수행해보면 아래와 같이 나오네요.
Max : 187
From 2 To 6
59 26 -53 58 97
배열 인덱스 2에서부터 6까지를 더하면 187이 나오며, 이 값은 책에 있는 값과 동일합니다.
프로그램을 테스트할 때 사용했던 값들을 좀더 표시해보면,
#define ARRAY_LENGTH 20
int x[ARRAY_LENGTH] = {
-1, 9, 20, -50, 60,
10, 23, 4, -10, 5,
-2, -30, 15, 25, 80,
65, -90, 150, 80, 4
};
에 대해
Max : 389
From 4 To 19
60 10 23 4 -10 5 -2 -30 15 25 80 65 -90 150 80 4
의 결과가 나옵니다.
댓글을 달아 주세요
i-- => n--
2009/06/18 22:37