[알고리즘 트레이닝] 3장 - 알고리즘의 효율성 추정하기, 최대 부분 배열 합

알고리즘의 효율성 추정하기

• 주어진 문제의 입력 크기를 통해서 그 문제를 풀기에 적합한 알고리즘의 시간복잡도를 추정해볼 수 있습니다.

예를 들어, n이 10 이하였다면, O(n!) 복잡도를 가지는 알고리즘으로 구현해도 괜찮다는 의미입니다.

이 방법은 알고리즘을 설계할 때 도움이 될 수 있습니다. 이 기준보다 비효율적인 알고리즘을 배제하고 생각할 수 있기 때문입니다.

최대 부분 배열 합(maximum subarray sum) 문제 - 시간복잡도 개선하기

배열에 수 n개가 들어있을 때, 배열에서 연속해 있는 값들을 선택해서 그 합이 최대가 될 경우를 구하는 문제입니다.

위 그림에서는 2,4,-3,5,2를 선택했을 때 부분 배열의 최대 합이 됩니다.

• O(n^3) 시간 풀이

가장 직관적인 방법은 가능한 모든 부분 배열을 하나씩 살펴 보고, 그 부분 배열의 합을 구한 후, 최대 합을 관리해 나가는 것입니다.

1
2
3
4
5
6
7
8
9
10
11

int best = 0;
for (int a = 0; a < n; a++){
	for(int b = a; b < n; b++){
		int sum = 0;
		for(int k = a; k <= b; k++){
			sum += array[k];
		}
		best = max(best, sum);
	}
}
cout << best << "\n";

즉, {-1}, {-1, 2}, … , {-1, 2, 4, -3, 5, 2, -5, 2} 까지 본 다음 / {2}, {2, 4}, … , {2, 4, -3, 5, 2, -5 2} 까지 본 다음 / {4}, {4, -3} , … {4, -3, 5, 2, -5, 2} 까지 본 다음 / … / {-5}, {-5, 2} / {2}

이렇게 모든 부분 배열을 반복문으로 다 살펴보는 것입니다.

하지만 for문이 3중으로 중첩되어 있어서 시간복잡도 측면에서는 그렇게 효율적이지는 않습니다.

입력의 크기가 작았다면 이 코드로도 문제가 없겠지만, 입력의 크기가 많아질수록 실행 시간은 n^3 형태로 증가하게 됩니다.

• O(n^2) 시간 풀이

위의 O(n^3) 알고리즘에서 반복문을 하나 줄이면 O(n^2) 알고리즘을 만들 수 있습니다.

1
2
3
4
5
6
7
8
9

int best = 0;
for (int a = 0; a < n; a++){    
	int sum = 0;
	for(int b = a; b < n; b
		sum += array[b];	
		best = max(best, sum);
	}
}
cout << best << "\n";

부분 배열의 오른쪽 끝을 이동해 가면서 그 합도 같이 계산하는 것입니다.

• O(n) 시간 풀이

이 문제는 백준에도 연속합(1912번) 문제로 존재합니다. (바로가기)

들어가 보시면 알겠지만 정수 n이 100,000개까지 주어질 수 있습니다.

맨 위 표에서 살펴보았듯이 입력의 크기가 10만개 정도면 O(n^2)으로 풀면 비효율적임을 알 수 있습니다.

(입력의 크기 - 5천개 이하일 때만 O(n^2) 정도가 괜찮으므로)

즉, 이 문제는 O(log n)이나 O(n) 중에 하나로 풀어야 한다는 의미가 됩니다.

이 문제는 부분 문제를 생각하는 dp 로 접근하여 O(n) 풀이를 할 수 있습니다.

• 위치 k에서 끝나면서 합이 최대인 부분 배열을 구하는 부분 문제는 단 2가지입니다.
  • 부분 배열이 위치 k의 원소 하나만일 때
  • 위치 k-1에서 끝나는 부분 배열에, 위치 k의 원소를 덧붙여 부분 배열을 만들 때

두 번째의 경우, 부분 배열 중에서 합이 최대인 것을 구하려 하는 것이므로, 위치 k-1에서 끝나는 부분 배열도 합이 최대인 부분 배열이어야 합니다.

따라서 배열을 왼쪽에서 오른쪽으로 살펴보면서, 각 위치에서 끝나는 최대 부분 배열 합을 계산해 내면 이 문제를 O(n)으로 풀 수 있게 됩니다.

1
2
3
4
5
6

int best = array[0], sum = 0;
for (int k = 0; k < n; k++){
	sum = max(array[k], sum + array[k]);
	best = max(best, sum);
}
cout << best << "\n";

• k=0일 때 : sum 에는 array[0]의 값이 들어가고, best에도 array[0]의 값이 유지된다.
• k=1일 때 : sum 에는 array[1] 과 ((array[0]) + array[1]) 의 값 중에 더 큰 값이 들어가야 한다.
• 그런데, array[1] 단독 값인 2가 array[0] (위치 k-1까지의 합)+ array[1] (위치 k의 원소) = -1 + 2 = 1 보다 크므로, 이전에 array[0] = -1부터 더한 부분 배열은 버려진다.
• 즉, array[1] = 2부터 다시 부분 배열의 첫 시작을 하게 되는 것이다.

이렇게 sum에는 “위치 k-1까지의 합 + 위치 k의 원소” 혹은 “위치 k 원소 하나의 값” 둘 중 더 큰 것이 들어가게 됩니다.

sum에 둘 중 하나의 값을 선택하기 전, sum + array[k]에서의 sum에는 자연스레 위치 k-1까지의 합이 들어가 있게 됩니다.

모든 원소를 적어도 한 번씩은 살펴보아야 하므로, 이 O(n) 알고리즘이 가장 최적화된 풀이입니다.