1.2 Maximum Range Sum (2)

앞에서 사용한 알고리즘의 Time Complexity는 $O(n^3)$이었다. 이것을 줄이기 위해서는 불필요한 연산을 줄이는 것이 가장 먼저 할 수 있는 방법이다. 일단 앞의 알고리즘을 이용해서 작성한 소스코드를 다시 살펴보도록 하자.

int getMaximumRange1(int *arr, int size){
	int max = INT_MIN;
	for(int i=0; i<size; i++){
		for(int j=i; j<size; j++){
			int sum = 0;
			for(int k=i; k<=j; k++)
				sum += arr[k];
			if(max < sum)
				max = sum;
		}
	}
	return max;
}

이 소스코드의 4~10번째 줄을 보면 구간 [i, j]에서의 Range Sum을 계산하기 이전에 구간 [i, j-1]에서의 Range Sum을 다 계산을 했는데, 그것을 버리고 처음부터 다시 계산하고 있다. 즉 이 부분에서 비효율적인 일을 계속 하고 있기 때문에 계산을 하는데 너무 오래 걸린다는 것이다. 즉 구간 [i, j]에서의 Range Sum을 계산할 때 앞에서 계산한 구간 [i, j-1]에서의 Range Sum을 구해서 거기에 arr[j] 값을 더하는 방법으로 고치면 된다는 것을 알 수 있다. 이것을 고려해서 소스코드를 고치면 아래와 같다.

int getMaximumRange2(int *arr, int size){
	int max = INT_MIN;
	for(int i=0; i<size; i++){
		int sum = 0;
		for(int j=i; j<size; j++){
			sum += arr[j];
			if(max < sum)
				max = sum;
		}
	}
	return max;
}

앞선 코드에서는 for loop이 3개가 존재했는데, 소스코드를 수정하고 나니 for loop이 2개로 바뀌었다. 이것만 보더라도 확실히 속도상의 이득을 봤다고 할 수 있다. 그러면 Time Complexity를 직접 계산하면 $\sum_{i=0}^{i=n-1}\sum_{j=i}^{j=n-1}1 = O(n^2)$이 되어서 이 알고리즘은 $O(n^2)$ 알고리즘이라고 할 수 있다.

이것을 통해서 불필요한 연산을 줄이는 것만으로도 충분히 알고리즘의 수행시간을 향상시킬 수 있다는 사실을 알 수 있었다. 즉, 불필요한 연산은 최대한 하지 않도록 해서 알고리즘을 설계하는 것이 중요하다.

물론 이 Maximum Range Sum 문제에서 $O(n^2)$보다 더 빠른 알고리즘이 존재하자만, 그 내용을 다루기 위해서는 약간의 지식이 필요하기 때문에 그 내용을 다룬 후에 다시 돌아와서 좀 더 나은 알고리즘에 대해서 살펴보도록 하겠다.

Time Complexity를 계산할 때 약간의 편법이라고 한다면, for loop이 1개가 있으면 $O(n)$이고, for loop이 k개가 중첩된 경우에는 $O(n^k)$라고 생각해도 된다. 다만 이 경우에는 for loop에서 index가 변수의 1차항으로 표현이 되어야 한다는 제약 조건이 있다. 그리고 이러한 편법이 통하지 않는 문제도 있기 때문에, $\sum$을 이용해서 계산을 하는 것이 정확한 방법으로 구하는 것이며, 빠른 시간에 알고리즘의 Time Complexity의 경향성을 알아야 한다면 위의 편법을 이용해서 계산해보도록 한다. 물론 for loop에서의 index가 변수의 1차항으로 표현이 되어 있다면 항상 이 조건을 만족하는데, 그 이유는 $O(f(n))$의 의미상 모든 $n$에 대해서 $f(n)<g(n)$이면 $O(f(n))\leq O(g(n))$이 성립하기 때문이다. 즉, Big-O가 상계를 의미하기 때문에 더 큰 값으로 잡더라도 항상 성립하기 때문이다.