알고리즘 디자인 기법

 

알고리즘 디자인 기법

 

 

  이 칼럼에서는 어떤 작은 문제에 대한 네 가지의 다른 알고리즘을 공부할텐데, 각각을 디자인하는 데 사용한 기법을 중심으로 전개한다. 일부 알고리즘은 약간 복잡하지만, 그럴만한 이유가 있다. 첫 번째 프로그램은 크기가 100,000 인 문제를 15 일 걸려 풀지만, 마지막 프로그램은 같은 문제를 5 ms 만에 푼다.

 

 

 

 1. 문제 및 간단한 알고리즘

 

  이 문제는 1 차원 패턴 인식을 구현하는 중에 생긴 것이다. 자세한 배경은 나중에 설명하겠다. 입력은 n 개의 부동소수점 수로 이루어진 벡터 x 이고, 출력은 입력된 벡터에 대한 연속적인 부분벡터 각각의 합 중 최대값이다(이를 최대합이라 한다). 예를 들어 입력벡터가 다음과 같이 10 개의 요소를 가지고 있다면,

 

 

프로그램은 x[2..6]의 합. 즉, 187 을 출력해야 한다. 모든 요소가 양수라면 문제는 간단해진다. 입력벡터의 합 자체가 그대로 답이 된다. 그러나 요소 중 일부가 음수라면 문제가 복잡해진다. 음수를 만났을 때, 그 다음에 있는 양수가 합을 보상하고도 남을 것이라 기대하며 그 음수를 포함시켜야 할까? 문제를 완전하게 정의하기 위해, 모든 요소가 음수일 때의 최대합 부분벡터는 빈 벡터이고 그 합은 0 이라 하자.

  이 문제를 푸는 손쉬운 방법은 0 ≤ i ≤ j ≤ n 을 만족하는 정수 i , j 의 모든 쌍에 대해 x[i..j]의 합을 계산하고, 그 중 최대값을 구하는 것이다(알고리즘 1). 이에 대한 가상코드는 다음과 같다.

 

 

                  maxsofar = 0

                  for i = [0 , n)

                       for j = [i , n)

                               sum = 0

                               for k = [i , j]

                                       sum += x[k]

                               /*  sum is sum of x[i..j]  */

                               maxofar = max(maxofar, sum)

 

 

이 코드는 짧고, 명백하며, 이해하기 쉽다. 그러나 불행하게도 너무 느리다. 예를 들어 내 컴퓨터에서는 n 이 10,000 일 때 약 22 분이 걸리고, n 이 100,000 일 때 15 일이 걸린다. 시간 측정에 대한 내용은 5 절에서 볼 것이다.

  위에서 제시한 소요시간은 하나의 예일 뿐이고, O 표기법을 사용하면 알고리즘의 효율성에 대한 다른 종류의 느낌을 얻을 수 있다. 가장 바깥쪽의 루프는 정확히 n 번 실행되고, 중간의 루프는 바깥 루프가 반복될 때마다 최대 n 번씩 실행된다. 이 둘을 곱하면, 중간의 루프가 O(n²) 번 실행됨을 알 수 있다. 중간 루프 내에 포함되는 가장 안쪽 루프는 결코 n 번 이상 실행되지 않으므로, 비용(cost)은 O(n) 이다. 안쪽 루프의 비용과 그 실행 횟수를 곱하면 프로그램 전체의 비용이 n³ 에 비례함을 알 수 있다. 즉 O(n³) 알고리즘이다.

  위의 예에서 O 표기법 분석의 장 · 단점을 알 수 있다. 주된 단점은 특정 입력에 대해 소요되는 구체적인 시간은 알 수 없다는 것이다. 단지 단계의 횟수가 O(n³) 라는 사실을 알게 될 뿐이다. 이런 단점은 이 기법의 두 가지 장점에 의해 상쇄되기도 한다. O 표기법 분석은 일반적으로 쉽게 할 수 있고(위에서와 같이), 봉투 뒷면에 간단하게 끄적거리는 계산으로 얻는 근사적인 실행시간만으로도 주어진 상황에 어떤 프로그램이 적당한지를 충분히 결정할 수 있다.

  이어지는 몇 개의 절에서는 프로그램의 효율성에 대한 척도로써 근사적인 실행시간만을 사용한다. 이 점이 미씸쩍다면, 이런 분석이 문제에 대해 많은 정보를 준다는 점을 증명하는 5 절을 미리 봐도 좋다. 계속 읽어나가기 전에 더 빠른 알고리즘을 생각해보라.

 

 

 

 2. O(n²) 알고리즘 두 가지

 

  대부분의 프로그래머들은 알고리즘 1 에 대해 같은 반응을 보일 것이다. "훨씬 더 빠르게 만들 수 있는 분명한 방법이 있다." 사실 그런 방법은 두 가지이다. 어떤 프로그래머에게 한 가지 방법이 명백하다면, 다른 방법은 그렇지 않은 것이 보통이다. 두 알고리즘은 모두 n² 에 비례한다(입력의 크기 n 에 대하여 O(n²) 번의 단계를 거친다). 그리고 x[i..j] 의 합을 구하기 위해 j - j + 1 번의 덧셈을 하는 알고리즘 1 과는 달리, 이 두 알고리즘은 일정한 횟수의 단계만으로 합을 구함으로써 실행시간을 줄인다. 그러나 각 알고리즘이 일정한 시간 내에 합을 계산하기 위해 사용하는 방법은 전혀 다르다.

  첫 번째 O(n²) 알고리즘은 x[i, j] 의 합이 바로 전에 계산했던 합(즉, x[i..j - 1]의 합)과 밀접한 관계가 있다는 점에 착안하여 간단히 합을 구한다. 이런 관계를 이용하여 다음과 같은 알고리즘 2 를 만들 수 있다.

 

 

                  maxsofar = 0

                  for i = [0, n)

                       sum = 0

                       for j = [i, n)

                             sum += x[j]

                             /*  sum is sum of x[i..j]  */

                             maxsofar = max(maxsofar, sum)

 

 

첫 번째 루프 안에 있는 구문들은 n 번 실행되고, 두 번째 루프는 바깥의 루프가 반복될 때마다 최대 n 번씩 실행된다. 따라서 전체의 실행시간은 O(n²) 이다.

 

  두 번째 O(n²) 알고리즘은 안쪽 루프에서 바깥 쪽의 루프가 실행되기 전에 미리 생성해놓은 데이터 구조를 이용하여 합을 계산한다. cumarr 의 i 번째 요소는 x[0..i] 의 요소들의 누적 합계로써, cumarr[j] - cumarr[i - 1] 을 계산하면 x[i..j] 의 합을 구할 수 있다. 이와 같은 알고리즘 2b 에 대한 코드는 다음과 같다.

 

 

                  cumarr[-1] = 0

                  for i = [0, n)

                        cumarr[i] = cumarr[i - 1] + x[i]

                  maxsofar = 0

                  for i = [0, n)

                        for j = [i, n)

                               sum = cumarr[j] - cumarr[i - 1]

                               /*  sum is sum of x[i..j]  */

                              maxsofar = max(maxsofar, sum)

 

 

이 코드의 O 표기법 분석은 알고리즘 2 와 동일하므로 O(n²) 시간이 걸린다.

 

  지금까지 본 알고리즘들은 부분벡터의 시작 위치와 종료위치에 대해 가능한 모든 쌍을 조사하여 각 부분벡터의 합을 구하는 것이었다. 부분벡터의 개수가 O(n²) 이므로, 그 합을 구해보는 알고리즘은 최소 O(n²) 시간이 걸릴 수밖에 없다. 이러한 문제점을 피하고 더 빠른 알고리즘을 생각해낼 수 있겠는가?

 

 

 

 3. 나누어 푸는 알고리즘

 

  O(n log n) 알고리즘은 복잡하다. 세부적인 내용이 어렵다면, 그냥 다음 절로 넘어가도 별 상관이 없을 것이다. 이 알고리즘은 다음과 같이 나누어 푸는(divide-and-conquere) 기법을 기반으로 한다.

 

크기가 n 인 문제를 풀 때, 크기가 약 n / 2 인 두 개의 하위 문제를 재귀적으로 푼 후, 각각의 해를 결합하면 전체 문제의 해를 얻게 된다.

이 경우, 원래 문제는 크기가 n 인 벡터를 다루므로, 그것을 두 부분으로 나누는 가장 자연스러운 방법은 거의 같은 크기를 가지는 두 벡터로 나누는 것이다. 이 두 벡터를 a, b 라 하자.

 

 

 

 

다음에는 a 와 b 에 대하여 각각 최대합을 가지는 부분벡터를 재귀적으로 찾는다. 그 부분벡터를 각각 ma와 mb라 하자.

 

 

 

 

  전체 벡터에서 최대합을 가지는 부분벡터는 ma나 mb중의 하나이기 때문에, 이렇게 하면 문제를 다 푼 것이라 생각하기 쉽다. 이것은 거의 맞다. 그러나 실제로 최대합을 가지는 부분벡터는 a 나 b 에 완전히 포함될 수도 있지만, a 와 b 의 경계에 걸쳐 있을 수도 있다. 이와 같이 경계에 걸치면서 최대합을 가지는 벡터를 mc라고 하자.

 

 

 

 

따라서 나누어 푸는 알고리즘은 ma와 mb를 재귀적으로 구하고, 다른 어떤 방법으로 mc를 구하여, 셋 중에서 최대값을 리턴한다.

  이 정도의 설명만으로도 코드를 작성하기에 충분하다. 이제 남은 것은 작은 벡터들을 다루는 방법과 mc를 구하는 방법이다. 앞의 문제는 쉽다. 한 개의 요소를 가진 벡터의 최대합은 그 벡터에 속한 바로 그 값이다(만약 음수라면 0 이 최대값이다). 그리고 빈 벡터의 최대합은 0 이라고 정의했다. mc를 계산할 때 mc의 왼쪽 부분은 a 와 b 의 경계에서 시작하여 a 쪽으로 뻗어나가는 부분벡터들 중에서 합이 최대가 되는 벡터이고, mc의 오른쪽 부분도 마찬가지 방법으로 구할 수 있다. 위의 사실을 종합하여, 다음과 같이 알고리즘 3 에 대한 코드를 작성할 수 있다.

 

 

                  float maxsum3(l, u)

                       if (l> i)  /* zero elements  */

                            return 0

                       if (l== 0)  /* one element  */

                            return max(0, x[l])

                  m = (l+ u) / 2

                  /*  fine max crossing toleft  */

                 lmax = sum = 0

                  for (i = m; i >=l; i--)

                            sum += x[i]

                           lmax = max(lmax, sum)

                  /*  find max crossing to right  */

                  rmax = sum = 0

                  for i = (m, u]

                            sum += x[i]

                            rmax = max(rmax, sum)

 

                  return max(lmax + rma, maxsum3(l, m), maxsum3(m + 1, u) )

 

 

알고리즘 3 은 다음과 같이 호출된다.

 

                  answer = maxsum3(0, n - 1)

 

 

  이 코드는 미묘하고 틀리기도 쉽지만, O(n log n) 시간에 문제를 풀어낸다. 이 사실은 몇 가지 방법으로 증명할 수 있다. 우선 알고리즘이 O(n) 의 작업을 O(n log n) 단계의 재귀로 처리한다는 사실로 간단하게 보일 수 있다. 귀납적 정의를 사용하면 좀더 정확한 증명을 할 수 있다. T(n) 을 크기가 n 인 문제를 푸는데 드는 시간이라 하면, 다음의 관계가 성립한다.

 

 

                  T(1) = O(1)

                  T(n) = 2T(n / 2) + O(n)

 

 

 

 

 4. 스캐닝(scanning) 알고리즘

 

  이제 배열에 적용되는 가장 간단한 종류의 알고리즘을 사용할 것이다. 이 알고리즘은 배열의 맨 왼쪽에서(요소 x[0]) 시작하여 오른쪽 끝까지(요소 x[n-1]) 읽어가면서, 그때까지의 최대합을 가지는 부분벡터를 보관한다. 초기의 최대합은 0 이다. 만약 x[0..i - 1] 에 대해 문제를 풀었다면, 이것을 어떻게 확장하여 x[i] 를 포함하도록 할 수 있을까? 앞의 나누어 푸는 알고리즘과 비슷한 추론을 해보자. 처음 i 개의 요소 중에서 최대합을 가지는 부분벡터는 처음 i - 1 개의 요소 내에 포함되거나(이를 maxsofar 에 저장할 것이다), 위치 i 에서 끝날 것이다(이는 maxendinghere 에 저장할 것이다).

 

 

알고리즘 3 과 같은 코드를 사용하여 maxendinghere 를 처음부터 다시 계산하다면 또 다른 O(n²) 알고리즘이 된다. 이 문제점은 알고리즘 2 의 기반이 되는 기법을 사용하여 피할 수 있다. 처음부터 다시 계산하는 대신에, 위치 i - 1 에서 끝나는 최대합을 가지는 부분벡터를 이용한다. 이렇게 하여 다음과 같은 알고리즘 4 를 만들 수 있다.

 

 

                  maxsofar = 0

                  maxendinghere = 0

                  for i = [0, n)

                          /* invariant : maxendinghere and maxsofar are accurate for x[0..i - 1] */

                          maxendinghere = max(maxendinghere + x[i], 0)

                          maxsofar = max(maxsofar, maxendinghere)

 

 

  이 프로그램을 이해하기 위한 핵심은 maxendinghere 이다. 루프 내의 첫번째 대입문이 실행되기 전에는 maxendinghere 에 위치 i - 1 에서 끝나는 최대합을 가지는 부분벡터의 합이 저장되어 있다. 대입문이 실행되면 위치 i 에서 끝나는 최대합을 가지는 부분벡터의 합이 저장된다. x[i] 가 양수라면 이 대입문은 값을 x[i] 만큼 증가시킨다. 만약 음수라면 0 이 된다(이 경우에는 위치 i 에서 끝나는 최대합을 가지는 부분벡터가 빈 벡터이므로). 코드가 이해하기는 어렵지만, 대신에 짧고 빠르다. 이 프로그램의 실행시간은 O(n) 이며, 따라서 이를 선형적 알고리즘이라고 할 수 있다.

 

 

 

 5. 무엇이 중요한가?

 

  지금까지는 O 표기법을 사용하여 대략의 실행시간을 간단히 추측했지만, 이제는 프로그램의 실제 실행시간을 측정하여 정리할 차례다. 나는 앞의 네 가지 주요 알고리즘을 C 로 구현하고 400 MHz 펜티엄 II 에서 실행시켜 그 시간을 측정했다. 그리고 측정한 실행시간에 약간의 추정을 더하여 다음과 같은 표를 만들었다.(알고리즘 2b 의 실행시간은 알고리즘 2 에 비해 10% 정도 밖에 차이나지 않아 포함시키지 않았다.)

 

 

 

 

 

이 표를 통해 몇 가지를 알 수 있다. 가장 중요한 점은 알고리즘 디자인에 따라 실행시간이 크게 달라진다는 것이다. 이는 위의 표 중간부분에서 확실히 알 수 있다. 마지막 두 행은 문제 크기와 실행시간 사이의 관계를 보여준다.

  또 하나 중요한 점은 선형 알고리즘과 O(n²), O(n³) 알고리즘을 서로 비교할 때 상수요소는 별로 중요하지 않다는 것이다. 이 점을 확실히 하기 위해, 나는 되도록 상수요소의 차이가 많이 나는 환경에서 두 알고리즘을 실험했다. 상수요소를 크게 만들기 위해 알고리즘 4 를 Radio Shack TRS-80 Model III(2.03 MHz 로 동작하는 Z-80 프로세서가 장착된 1980 년대의 퍼스널 컴퓨터)에서 실행시켰다. 안그래도 느린 시스템을 더 느리게 하기 위해, (컴파일된 코드보다 10 배에서 100 배 정도 느린) 인터프리터 방식의 Basic 을 사용했다. 이와 비교하기 위해 533MHz 로 동작하는 Alpha 21164 에서 알고리즘 1 을 실행 시켰다. 나는 애초에 기대했던 차이를 얻었다. O(n³) 알고리즘의 실행시간은 0.5 n³ns 로 측정되었고, 선형 알고리즘은 19,500,000 n ns 였다(즉, 1 초에 50 개의 요소를 처리한다). 다음 표는 이들 수식이 문제의 크기에 따라 어떤 결과를 나타내는지 보인다.

 

 

 

상수요소가 3 천 2 백만 배나 차이가 나기 때문에 O(n³) 알고리즘이 더 빠르게 출발하지만, 선형 알고리즘이 따라잡게 되어 있었다. 문제 크기가 대략 5,800 이면 두 알고리즘의 속도가 같아지는데, 실행시간이 둘 다 2 분보다 약간 적다.

 

 

 

 6. 원리

 

  이 문제의 배경 이야기를 살펴보면 알고리즘 디자인 기법에 대한 중요한 정보를 얻을 수 있다. 이 문제는 Brown 대학의 Ulf Grenander 가 직면한 패턴 맞추기(pattern-matching) 문제에서 파생되었다. 2 차원 형태를 푸는 데는 너무 많은 시간이 필요했으므로, Grenander 는 문제를 1 차원으로 축소하여 구조에 대한 통찰을 얻고자 했다.

  Grenander 는 알고리즘 1 의 실행시간을 측정한 결과, 너무 느리다고 판단하여 알고리즘 2 를 고안했다. 그는 1977 년에 Michael Shamos 에게 이 문제를 설명했고, Shamos 는 하룻밤 사이에 알고리즘 3 을 디자인했다. 그 후 Shamos 가 나에게 그 문제를 알려주었을 때, 우리는 Shamos 의 알고리즘이 가능한 최상의 해법일 것이라 생각했다. 연구원들은 몇몇 비슷한 문제들 역시 n log n 에 비례하는 시간이 필요하다는 것을 보였다. 며칠 후에 Shamos 는 Carnegie Mellon 세미나에서 이 문제와 그 배경을 설명했고, 여기에 참석했던 통계학자인 Jay Kadane 은 1 분만에 알고리즘 4 의 윤곽을 잡았다. 우리는 이보다 더 빠른 알고리즘은 없다는 것을 알고 있다. 이 문제에 대한 모든 정확한 알고리즘은 O(n) 시간이 필요하다.

  1 차원 문제가 완벽하게 해결되었음에도 불구하고, Grenander 가 원래 풀려했던 2 차원 문제는 제시된지 20 년이 지나도록 해결되지 않고 있다. 알려진 모든 알고리즘에 들어가는 계산 비용 때문에 Grenander 는 패턴 맞추기 문제에 대한 이런 식의 접근방법을 포기해야 했다.

  이 이야기를 통해 우리는 알고리즘 디자인에 있어 중요한 기법들을 배울 수 있다.

 

 

  재계산을 피하기 위한 상태 저장

 

  이것은 동적 프로그래밍(dynamic programming)의 간단한 형태로서 알고리즘 2 와 4 에서 사용되었다. 결과를 저장하기 위해 메모리를 사용함으로써 다시 계산하기 위해 시간을 소모하지 않아도 된다.

 

 

  정보를 사전처리하여 데이터 구조에 보관

 

  알고리즘 2b 에서 사용된 cumarr 구조는 부분벡터의 합을 빠르게 계산할 수 있도록 한다.

 

 

 나누어 푸는 알고리즘

 

  알고리즘 3 은 간단한 형태의 나누어 푸는 방법을 사용한다. 알고리즘 디자인에 대한 교재에는 더 고급의 형태가 설명되어 있다.

 

 

 스캐닝 알고리즘

 

  배열에 대한 문제는 종종 " x[0..i - 1] 에 대한 답을 어떻게 x[0..i] 에 대한 답으로 확장할 수 있을까? " 라는 물음에 의해 풀린다. 알고리즘 4 에서는 이전의 답과 함께 새로운 답을 계산하기 위한 몇몇 보조 데이터를 저장한다.

 

 

 누적

 

  알고리즘 2b 에서는 x 의 처음 i 개의 요소에 대한 합을 i 번째 자리에 가지고 있는 누적 테이블을 사용한다. 이런 테이블은 범위를 다루는 경우에 흔히 사용된다. 예를 들어, 비즈니스 애널리스트는 10 월까지의 연간 판매량에서 2 월까지의 연간 판매량을 뺌으로써 3 월에서 10 월까지의 판매량을 알 수 있다.

 

 

  하한

 

  알고리즘 디자이너는 자신의 알고리즘이 가능한 것들 중에서 최상이라고 생각될 때에만 편안하게 잠들 수 있다. 이를 보장하려면, 그 문제에 대한 하한(lower bound)을 보여야 한다.

 

 

 

 

 

* 본 `알고리즘 디자인 기법`은 Programming Pearls, 2nd Edition[2003, Jon Bentley]의 칼럼 8 의  내용이며, 국내의 번역서 `생각하는 프로그래밍[2003.2.15 윤성준,조상민]`을 참고하여 부분 발췌하였습니다.