Algorithm. Scanning(스캐닝) algorithm

algospot의 MAXSUM 문제:
scanning algorithm을 사용해야 함. scanning algorithm은 기본 concept는
--> '최대값 계산 시, 음수가 포함된다면 잘라내기'
라고 요약할 수 있겠다.

먼저 내가 작성한 source를 보자

package com.yongk.algospot.MAXSUM;

import java.util.Scanner;

public class MAXSUM {
 public static void main(String[] args) {
  Scanner sc = new Scanner(System.in);
  int T = Integer.parseInt(sc.nextLine());
  while(T-- > 0) {
   int N = sc.nextInt();
   sc.nextLine();
   int[] input = new int[N];
   String[] temp = sc.nextLine().split(" ");
   for (int i = 0; i < N; i++) {
    input[i] = Integer.parseInt(temp[i]);
   }
   System.out.println(getMaximumSetFast(input));
  }
  sc.close();
 }
 private static int getMaximumSetFast(int[] input) { //scanning algorithm
  int max = 0;
  int from = 0;
  for (int i = 0; i < input.length; i++) {
   from = Math.max(from + input[i], 0);
   max = Math.max(max, from);
  }
  return max;
 }
 private static int getMaximumSetSlow(int[] input) { //처음 생각한 O(n^2)의 저속한 algorithm
  int[] sum = new int[input.length];
  sum[0] = input[0];
  int max = 0;
  for (int i = 1; i < input.length; i++) {
   sum[i] = sum[i - 1] + input[i];
   max = Math.max(max, sum[i]);
  }
  
  for (int i = 0; i < sum.length; i++) {
   for (int j = i; j < sum.length; j++) {
    max = Math.max(max, sum[j] - sum[i]);
   }
  }
  return max;
 }
}

- 처음 생각한 것이 getMaximumSetSlow()인데 나름 짱구를 굴려 미리 계산한 값으로 중복 계산을 줄이자는 생각이었지만 미개한 생각이었다.
- getMaximumSetFast()가 scanning algorithm. input[0]에서부터 더해가다가 그 값이 0보다 작아지면 당연히 거기까진 더할 필요가 없다. 왜냐하면 거기서부터 더하는건 0보다 크기 때문.
- 덕분에 scanning algorithm은 O(n)의 속도이다.
- 사람도 이렇게 생각하지 않을까?

덧1, python으로 같은 것을 구현하면

import sys 
def getMaximumSetFast(input):
        maxVal = 0 
        fromVal = 0 
        for i in input:
                fromVal = max(fromVal + i, 0)
                maxVal = max(fromVal, maxVal)
        return maxVal

rl = lambda: sys.stdin.readline()
T = int(rl())
for i in range(T):
        rl()
        input = [int(j) for j in rl().split()] 
        print(getMaximumSetFast(input))

덧2. 그리고 java.util.Scanner()는 느리다..대따 느리다 ㅠㅠ 가급적이면 nextInt()보다는 nextLine()을 parseInt()할 것! 처음엔 다음과 같이 작성했었는데..참담한 속도였다. 적어도 5배 이상 느림.

  while(T-- > 0) {
   int N = sc.nextInt();
   int[] input = new int[N];
   for (int i = 0; i < N; i++) {
    input[i] = sc.nextInt(); //slow!!!
   }
   System.out.println(getMaximumSetFast(input));
  }