수업 목표 및 핵심 역량

- 정밀한 코드 실행 시간 측정법을 배웁니다. - 최대 부분배열 합 문제를 해결하는 기법들의 Big-O를 비교합니다. - 카데인 알고리즘과 누적합 최적화 기법을 완벽히 이해합니다. - 8011번, 8011번 실습 문제를 고속 선형 코드로 풀이합니다.

파이썬 실행 시간 정밀 측정

`time` 모듈의 `perf_counter`를 활용하여 알고리즘 실행 속도를 정밀 측정합니다.

import time

start_t = time.perf_counter()
# 알고리즘 실행
end_t = time.perf_counter()
print(f"시간: {end_t - start_t:.6f} 초")

- 시간 초과(TLE) 예상 지점 및 비효율 구간 파악에 필수적으로 사용됩니다.

최대 부분배열 합 복잡도 비교

- **$O(N^3)$ 브루트 포스**: 3중 루프를 통한 단순 무식한 합 구하기 - **$O(N^2)$ 누적합**: 2중 루프를 돌며 직전 합에 다음 원소만 누적 더하기 - **$O(N \log N)$ 분할 정복**: 왼쪽, 오른쪽, 경계 결쳐진 최대합 병합 탐색 - **$O(N)$ 카데인 알고리즘**: - `dp[i] = max(a[i], dp[i-1] + a[i])` - $N=200,000$ 데이터에서 단 0.01초 만에 실행이 완료됩니다.

카데인 알고리즘 최적 구현

- 공간 복잡도를 $O(1)$로 최적화한 카데인 알고리즘 구현 코드입니다.

max_so_far = a[0]
curr_max = a[0]
for i in range(1, len(a)):
    curr_max = max(a[i], curr_max + a[i])
    if curr_max > max_so_far:
        max_so_far = curr_max

- 모든 원소가 음수인 경우 초기값으로 `0`을 주면 안 되며, 반드시 `a[0]`로 시작해야 합니다.

누적합 최솟값 추적 및 개수 세기 ($O(N)$)

부분배열 합의 수식 관계: `SubarraySum = S[i] - S[j-1]` (단, $S$는 누적합) - $S[j-1]$이 최솟값일 때 $S[i] - S[j-1]$이 최대가 된다는 원리를 활용합니다. - 루프를 돌며 최솟값 `min_val`과 등장 횟수 `min_count`를 동시 관리합니다. - `curr_s - min_val`이 최대합과 같으면 `max_count`에 `min_count`를 추가로 누적합니다.

자주 하는 실수 요약

- **음수 전용 배열 처리**: 최대 부분합 초기값을 `0`으로 주는 오류 해결 - **최솟값 갱신 타이밍**: `min_val` 갱신을 최대합 판정 **이후에** 수행 - **자료형 크기**: 파이썬은 오버플로 걱정이 없으나 타 언어(C++/Java) 변환 시에는 64비트 정수형(`long long`) 선언 필수