<보기>의 최대 구간합 문제를 재귀 전략을 활용하여 해결하는… | [7급 서울시 알고리즘] 26년 1회차 기출문제 상세 페이지

1[7급 서울시 알고리즘] 26년 1회차
<보기>의 최대 구간합 문제를 재귀 전략을 활용하여 해결하는 방법 중, 계산량을 최소화하여 올바른 값을 구하는 방법으로 가장 옳은 것은?
<보기>
[최대 구간합 문제]
Input: 크기가 n인 정수 배열 A (시작 인덱스는 0)
Output: 배열 A의 부분 배열 구간합 중 최댓값
예시) 크기가 3인 정수 배열
-12-3
의 Output는 2이다.
* 부분 배열 A[i..j]( 0≤i≤j<n) 구간합: 연속한 부분 배열에 포함된 모든 원소의 합, 즉 A[i]+A[i+1]+…+A[j]를 의미한다.
* 재귀 전략: 배열 A를 전반부 A[0..m−1]과 후반부 A[m..n−1]로 나누어 해결한다. (m = ⌊n/2⌋\lfloor n/2 \rfloor ) (단, n=1이면, A[0]을 반환한다.)
1
전반부의 최대 구간합 a와 후반부의 최대 구간합 b를 재귀적으로 구하고, max(a, b)를 취한다.
2
전반부의 최대 구간합 a와 후반부의 최대 구간합 b를 재귀적으로 구하고, max(a, b, a+b)를 취한다.
3
전반부의 최대 구간합 a와 후반부의 최대 구간합 b를 재귀적으로 구하고, 시작 위치가 전반부에 있고 끝 위치가 후반부에 있는 모든 부분 배열의 구간합을 각각 계산하여 그중 최댓값 c를 구한 후, max(a, b, c)를 취한다.
4
전반부의 최대 구간합 a와 후반부의 최대 구간합 b를 재귀적으로 구하고, 전반부에서 A[m-1]을 마지막 원소로 하는 부분 배열의 최대 구간합 c와 후반부에서 A[m]을 첫 원소로 하는 부분 배열의 최대 구간합 d를 각각 구한 후, max(a, b, c+d)를 취한다.
해설

올바르면서 계산량이 가장 적은 방법은 경계를 가로지르는 최대합을 c+d로 구하는 분할 정복이다.

최대 구간은 전반부 안, 후반부 안, 또는 경계를 가로지르는 경우 중 하나다. 가로지르는 구간은 A[m−1]에서 끝나는 왼쪽 부분과 A[m]에서 시작하는 오른쪽 부분의 합이므로, 각각을 선형 시간에 최대화해 더하면 된다.

점화식이 T(n)=2T(n/2)+O(n)T(n)=2T(n/2)+O(n)이 되어 O(nlog⁡n)O(n\log n)이다.

  • max(a, b): 경계를 가로지르는 구간을 고려하지 않아 틀린 값이 나올 수 있다.
  • max(a, b, a+b): a와 b의 구간이 붙어 있지 않을 수 있어 a+b는 실제 구간합이 아니다.
  • 가로지르는 모든 부분 배열을 계산: 값은 올바르지만 단계마다 O(n2)O(n^2)이 들어 계산량이 크다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 서울시 알고리즘] 26년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 서울시 알고리즘 기출문제 암기장 전체 보기