Maximum subarray sum <5 kyu> - 1

문제링크

문제

The maximum sum subarray problem consists in finding the maximum sum of a contiguous subsequence in an array or list of integers:
maxSequence([-2, 1, -3, 4, -1, 2, 1, -5, 4]) // should be 6: [4, -1, 2, 1]
Easy case is when the list is made up of only positive numbers and the maximum sum is the sum of the whole array. If the list is made up of only negative numbers, return 0 instead.

Empty list is considered to have zero greatest sum. Note that the empty list or array is also a valid sublist/subarray.

🚩 문제해석
이 문제는 이름이 붙어 있는 유명한 문제이다. 최대 부분 배열 문제 라고 한다. Kadane's Algorithm 이라고도 한다. 연속된 부분 배열 중에서 요소의 총 합이 가장 큰 배열을 구하고 그 총 합을 리턴하는 문제이다. 배열의 연속된 부분은 1개부터 최대 전체 배열까지 될 수 있다. 전체 배열이 양수인 경우에는 요소의 최대 합을 가질 수 있는 배열은 무조건 전체 배열을 다 더한 값이 최대 부분 배열이 된다. 또 모두 음수인 배열은 0을 리턴하고 빈 배열인 경우에도 0을 리턴한다.

문제접근

먼저 어떻게 분류를 해서 부분 배열의 합을 비교할 것인지를 정해야 했다. 분류의 기준을 부분 배열이 몇개의 요소를 가지고 있는지에 따라서 분류하기로 하였다. 그리고 또 빈 배열과 모두 음수인 경우는 어떻게 구분해줘야 하는지를 생각했다. 그래서 some()이라는 메소드를 통해서 구분하기로 하였다.

• some()
  • every()와 반대되는 성격을 지닌 메소드이다. 두가지 메소드를 비교해보자
  • syntax : arr.every(callback); / arr.some(callback);
  • 콜백함수는 판별함수로서 true나 false를 리턴한다.
  • every() 는 판별함수가 모두 true가 나오면 최종 리턴값으로 true를 리턴한다. 중간에 false가 나오게 되면 더 이상 배열을 순회하지않고 종료시키면서 최종값을 false를 리턴한다. 반대로 some() 은 판별함수에서 true가 나오면 그 순간 순회를 종료하고 최종값으로 true를 리턴한다. 모두 false가 나오면 최종 리턴값으로 false를 리턴한다.
  • 빈 배열인 경우 every() 는 결과값으로 true를, some() 은 결과값으로 false를 리턴한다.

var maxSequence = function(arr){
     const positive = arr.some(function(ele){
                               return ele > 0;
                      });
     //negative false => all negative or empty array 
     //         true  => 어딘가 양수가 존재함
     if(positive){
       let max = arr[0];
       let cnt = 1;		//연속된 요소의 개수
       while(cnt <= arr.length){
         for(let j = 0; j <arr.length - cnt + 1; j++){
           const tmp = arr.slice(j,j+cnt).reduce(function(a,v){return a+v},0);
           if(max < tmp) max = tmp;
         }
         cnt++;
       }//while
       return max;
     }///if
     else{
      return 0;
     }
}

위의 코드는 처음 작성했을 때의 코드이다. 변수 cnt는 위에서 언급한대로 부분배열의 개수이다. 부분배열을 slice()를 통해서 구한 다음에 그 배열 요소의 총 합을 reduce()로 구하여 비교한다. some() 메소드를 사용한 것은 모두 음수인 배열 혹은 빈 배열을 구분하기 위해서 사용하였다. 그런데 사실 이렇게 구분을 할 필요가 없었다. 조금만 생각해보면 총 합의 초기 값(변수 max)을 0으로 주면 조건을 나눌 필요가 없어진다. 빈 배열인 경우 while문 안으로 들어갈 수 없기 때문에 초기값인 0이 리턴된다. 또한 모두 음수인 경우에는 어떠한 합을 더해서 0보다 큰 값은 나올 수 없기 때문에 결과값은 0이 리턴된다. 그렇게 리팩토링한 결과는 아래와 같은 코드가 된다.

var maxSequence = function(arr){
  let max = 0, cnt = 1;
  while(cnt <= arr.length){
    for(let j = 0; j <arr.length - cnt + 1; j++){
      const tmp = arr.slice(j,j+cnt).reduce(function(a,v){return a+v},0);
      if(max < tmp) max = tmp;
    }
    cnt++;
  }//while
  return max;
}

위 풀이는 빅오표기법으로 O(n^2)을 따른다. while문과 for문으로 인해서 이중for문과 같은 형태를 만들기 때문에 최악의 경우 n^2을 갖게 된다. 하지만 좀 더 보면 for문 안에서 slice()를 하여서 배열을 복사하는 과정에서도 내부적으로 순회를 하게 된다. 또한 reduce()는 그 복사한 배열을 다시 돌면서 총 합을 구한다. 이렇게만 봐도 도대체 몇번의 순환을 하는 것인가? 물론 저렇게 풀어도 답은 나왔고 주어진 샘플테스트는 통과하였음에도 뭔가 찜찜하다.

결론

알고리즘에 대해서 조금씩 공부하면서 느낀 것이 있다. 처음엔 보통 이중for문, 심지어는 삼중for문까지도 구현하면서 결과값 구현에 초점을 두었다. 하지만 점차적으로 이중for문만 나와도 아 '이거 다른 방법이 있을 것 같은데?' 라는 생각에 효율성에 중점을 둔 풀이를 더 생각하게 되었다. 특히 이 문제는 유명한 문제였기에 나의 풀이보다 좀 더 효율적이고 좋은 풀이들이 있을 거라 확신이 들었다. 찾아본 결과, 풀이 방법이 총 4가지 정도 존재했다. 첫번째는 O(n^3)으로 푸는 방법, 두번째는 O(n^2)으로 푸는 방법, 세번째는 분할정복 + 재귀를 사용해서 접근하는 방법, 마지막은 이 문제의 원래 의도(?)인 동적프로그래밍(Dynamic Programming, DP)으로 푸는 방법이다. 그리고 나중에 보니 문제 밑에 태그 자체에 Dynamic Programming 이라고도 달려 있었다. 그래서 이 포스팅에서 위의 4가지 예제를 다 다루기에는 너무 길어질 것 같아서 다음 편 포스팅에 4가지 풀이(특히 DP)와 Best Soution에 대해서 언급하고자 한다.

ps. DP는 몇번 봐서는 '이 문제를 DP로 푸는거야?? ' 라는 생각을 할 정도로 나같은 초보자가 접근하기에는 어려운 테마인 것 같다.