알고리즘 분석

[1. 문제]

1차원 배열에서 연속된 부분 구간 중 그 합이 최대인 구간을 찾기

ex) [-7, 4, -3, 6, 3, -8, 3, 4]

=>     [4, -3, 6, 3] 이 그 합이 10으로 최대가 됨.

 

[2. 알고리즘에 따른 시간 복잡도]

1. O(N^3)
   Bruteforce 방식
   

   #include <iostream>
   #include <vector>
   #include <numeric>
   #include <algorithm>
   
   int inefficientMaxSum(const std::vector<int>& input)
   {
       const int N = input.size();
       int ret = std::numeric_limits<int>::min();
       for (int i = 0; i < N; i++)
       {
           for (int j = i; j < N; j++)
           {
               int sum = 0;
               for (int k = j; k <= i; k++)
               {
                   sum += input[k];
               }
               ret = std::min(sum, ret);
           }
       }
   
       return ret;
   }
   
   int main()
   {
       const std::vector<int> input = {-7, 4, -3, 6, 3, -8, 3, 4};
       printf("%d\n", inefficientMaxSum(input));
       return 0;
   }

2. O(N^2)
   주어진 부분 구간의 합을 구해가면서 최대 값을 찾는다.
   

   #include <iostream>
   #include <vector>
   #include <numeric>
   #include <algorithm>
   
   
   int betterMaxSum(const std::vector<int>& input)
   {
       const int N = input.size();
       int ret = std::numeric_limits<int>::min();
   
       for (int i = 0; i < N; i++)
       {
           int sum = 0;
           for (int j = i; j < N; j++)
           {
               sum += input[j];
               ret = std::min(sum, ret);
           }
       }
   
       return ret;
   }
   
   
   int main()
   {
       const std::vector<int> input = {-7, 4, -3, 6, 3, -8, 3, 4};
       printf("%d\n", betterMaxSum(input));
       return 0;
   }

3. O(NlogN)
   분할 정복 방식
   주어진 배열을 반으로 쪼갰을 때
   최대 합 부분 구간은 두 배열 중 하나에 속할 수 있고
   두 배열 사이에 걸쳐 있을 수 있다.
   

   #include <iostream>
   #include <vector>
   #include <numeric>
   #include <algorithm>
   
   int fastMaxSum(const std::vector<int>& input, const int lo, const int hi)
   {
       // Base Case => 더 나눌 수 없는 경우
       if (lo == hi)
       {
           return input[lo];
       }
   
       const int mid = (lo + hi) / 2;
       int left = std::numeric_limits<int>::min();
       int right = left;
   
       // 왼쪽 구간에서 최대 합을 찾는다.
       int sum = 0;
       for (int i = mid; i >= lo; i--)
       {
           sum += input[i];
           left = std::min(left, sum);
       }
   
       // 오른쪽 구간에서 최대 합을 찾는다.
       sum = 0;
       for (int i = mid + 1; i <= hi; i++)
       {
           sum += input[i];
           right = std::min(right, sum);
       }
   
       // 분할된 각 구간에서 최대 합을 재귀적인 방식으로 찾는다.
       // [lo, mid]
       // [mid+1, hi]
       const int single = std::max(fastMaxSum(input, lo, mid),
                                   fastMaxSum(input, mid+1, hi));
   
       // 최대 합은 mid 를 기준으로
       // 왼쪽 구간 또는 오른쪽 구간에 있거나 => single
       // 왼쪽~오른쪽 구간에 걸쳐 있을 수 있다. => left+right
       return std::max(left + right, single);
   }
   
   
   int main()
   {
       const std::vector<int> input = {-7, 4, -3, 6, 3, -8, 3, 4};
       printf("%d\n", fastMaxSum(input, 0, input.size()-1));
       return 0;
   }

4. O(N)
   동적 계획법
   A[i] 를 오른쪽 끝으로 갖는 구간의 최대 합을 반환하는 함수를 maxAt(i) 라 할때,
   A[i]에서 끝나는 최대 합 부분 구간은 
   1. 항상 A[i] 하나만으로 구성되어 있거나
   2. A[i-1] 을 오른쪽 끝으로 갖는 최대 합 부분 구간의 오른쪽에 A[i] 를 붙인 형태로 구성되어 있다고 함
   따라서 아래와 같은 점화식으로 표현할 수 있다.
   maxAt(i) = max(0, maxAt(i-1)) + A[i] 
   

   #include <iostream>
   #include <vector>
   #include <numeric>
   #include <algorithm>
   
   int fastestMaxSum(const std::vector<int>& input)
   {
       const int N = input.size();
       int ret = std::numeric_limits<int>::min();
       int psum = 0;
   
       for (int i = 0; i < N; i++)
       {
           psum = std::max(0, psum) + input[i];
           ret = std::max(psum, ret);
       }
   
       return ret;
   }
   
   
   int main()
   {
       const std::vector<int> input = {-7, 4, -3, 6, 3, -8, 3, 4};
       printf("%d\n", fastestMaxSum(input));
       return 0;
   }

[3. 성능]