"

수업 목표

본 수업은 알고리즘의 시간 및 공간 복잡도를 정밀하게 측정하고 분석하는 능력을 함양하며, 비효율적인 코드를 획기적으로 개선하는 최적화 패러다임을 이해하는 것을 목표로 합니다. - 동일한 문제를 해결하는 다양한 알고리즘의 복잡도를 $O(N^3)$부터 $O(N)$까지 점진적으로 개선하며 성능 변화를 관찰합니다. - 카데인 알고리즘(Kadane's Algorithm)의 동적 계획법(DP)적 동작 원리를 이해하고 구현합니다. - 최대 연속 부분배열 합 문제에서 파생되는 "최대 부분합 수열의 개수" 카운팅 문제를 누적합(Prefix Sum)의 수학적 성질을 이용해 $O(N)$ 시간에 최적 설계합니다.

학습 동기부여

알고리즘 문제 해결에서 시간 복잡도 개선은 단순히 코드가 '조금 더 빨라지는 것'을 의미하지 않습니다. 데이터의 크기 $N$이 $200,000$인 실전 환경에서 $O(N^2)$ 알고리즘은 약 400억 번의 연산이 필요하여 실행에 수분이 소요되지만, $O(N)$ 알고리즘은 단 0.01초 만에 완료됩니다. 이는 프로그램의 작동 여부를 가르는 결정적 척도입니다. 실전에서 마주하는 최대 연속 부분배열 합 문제를 통해, 이론으로만 보았던 복잡도의 강력함을 직접 체감하고, 기발한 논리 변경(Prefix Sum 최솟값 추적 및 Kadane DP)을 활용해 자원의 한계를 돌파하는 하이엔드 최적화 기법을 온전히 자신의 것으로 습득하십시오.

도입 스토리

대형 마트의 1년 간 일별 매출 장부에서 가장 연속적으로 장사가 잘 되었던 '황금 매출 기간'을 찾아내어 보고해야 하는 과제를 맡았다고 가정해 봅시다. 가장 원시적인 방식은 모든 가능한 시작일과 종료일을 짝지어 그 사이의 매출을 매번 다 더해보는 것입니다. 이 방식은 일수가 늘어날 때마다 연산량이 3승에 비례해서 증가하므로($O(N^3)$) 컴퓨터를 마비시키게 됩니다. 하지만 똑똑한 점원은 '오늘까지의 누적 매출 합이 마이너스로 떨어져 손해가 나는 순간'에 즉시 이전까지의 기록을 버리고, 다음 날부터 새로운 구간을 시작하는 기발한 전략을 씁니다. 단 한 번 슥 훑어보는 것($O(N)$)으로 정답을 찾아내는 이 똑똑한 방식이 바로 카데인 알고리즘입니다. 본 수업에서는 이러한 발상의 전환이 만들어내는 획기적인 시간 단축 프로세스를 탐구합니다.

1. 파이썬 실제 코드 실행 시간 측정

실제 코드의 효율성을 검증하기 위해서는 이론적인 Big-O 분석 외에도 실행 시간을 직접 측정할 필요가 있습니다. 파이썬에서는 time 모듈의 perf_counter()를 사용하여 높은 정밀도로 실행 속도를 측정합니다.

import time

# 측정 시작
start_time = time.perf_counter()

# 실행을 측정할 알고리즘 로직 수행
# ...

# 측정 종료 및 출력
end_time = time.perf_counter()
print(f"실행 시간: {end_time - start_time:.6f} 초")

2. 최대 부분배열 합의 4가지 접근법과 복잡도 비교

"CP-Python 4.4절"에서 설명하듯, 이 문제는 시간 복잡도 개선 과정을 보여주는 가장 교과서적인 사례입니다.
배열 $a$의 연속된 부분합 $a[i] + \dots + a[j]$를 극대화하는 다양한 기법들을 비교해 봅시다.

가. 3중 루프 브루트 포스 ($O(N^3)$)

모든 가능한 시작 인덱스 $i$와 끝 인덱 $j$의 쌍에 대해, $i$부터 $j$까지 루프를 돌며 합을 구합니다.

max_sum = -float('inf')
for i in range(n):
    for j in range(i, n):
        curr_sum = 0
        for k in range(i, j + 1):
            curr_sum += a[k]
        max_sum = max(max_sum, curr_sum)

나. 2중 루프 누적합 최적화 ($O(N^2)$)

안쪽 루프에서 매번 값을 다시 더하지 않고, $j$가 증가할 때 기존 누적 합에 새로운 원소를 더해 나갑니다.

max_sum = -float('inf')
for i in range(n):
    curr_sum = 0
    for j in range(i, n):
        curr_sum += a[j]
        max_sum = max(max_sum, curr_sum)

다. 분할 정복법 ($O(N \log N)$)

배열을 반으로 쪼갠 뒤 왼쪽의 최대합, 오른쪽의 최대합, 그리고 경계를 걸쳐 있는 최대합 중 가장 큰 것을 선택합니다.
병합 정렬과 유사한 구조로 재귀가 동작하여 $O(N \log N)$이 걸립니다.

라. 카데인 알고리즘 ($O(N)$)

각 위치 $i$에서 끝나는 최대 부분합 `local_max`는 바로 직전 위치 $i-1$에서 끝난 최대 부분합에 현재 값을 더한 값(`local_max + a[i]`)과, 현재 값 단독(`a[i]`) 중 더 큰 값입니다.

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

3. 최적 연속 부분합의 개수 세기 ($O(N)$)

8011번: 최대 부분합 수열 문제에서는 연속 부분합의 최댓값뿐만 아니라, 그 최댓값을 달성하는 부분배열의 총 개수도 함께 구해야 합니다. 이를 카데인 알고리즘의 변수들로 직접 세는 것은 다소 복잡하지만, 누적합(Prefix Sum)의 수학적 성질을 이용하면 매우 명료하게 $O(N)$ 시간에 해결할 수 있습니다.
배열 $a$의 누적합 배열을 $S$라고 정의합시다. ($S[i] = a[0] + \dots + a[i]$ 이며, 경계조건 $S[-1] = 0$)
$i$번째 원소에서 끝나는 임의의 부분배열의 합은 $S[i] - S[j-1]$ ($j \le i$) 로 표현됩니다. 이 값이 최대가 되려면 $S[j-1]$이 최소여야 합니다.
따라서 배열을 순회하며 지금까지 등장한 누적합 $S$의 최솟값 `min_val`과 그 최솟값이 등장한 횟수 `min_count`를 항상 기록해 둡니다. - $i$ 지점에서의 최대 부분합 후보는 `S[i] - min_val`입니다. - 이 후보가 전역 최대 부분합 `max_sum`보다 크다면 `max_sum`을 갱신하고, 개수 `max_count`를 `min_count`로 완전히 대체합니다. - 만약 이 후보가 현재 `max_sum`과 일치한다면 기존 `max_count`에 `min_count`를 누적하여 더해 줍니다. - 그 후 $S[i]$가 현재 `min_val`보다 작다면 `min_val`을 $S[i]$로 갱신하고 `min_count`를 1로 설정하며, $S[i]$가 `min_val`과 같다면 `min_count`를 1 증가시킵니다.

# 8011번 핵심 최적화 알고리즘
min_val = 0
min_count = 1
curr_s = 0
max_sum = -float('inf')
max_count = 0

for val in a:
    curr_s += val
    ans_ending_here = curr_s - min_val
    if ans_ending_here > max_sum:
        max_sum = ans_ending_here
        max_count = min_count
    elif ans_ending_here == max_sum:
        max_count += min_count
        
    if curr_s < min_val:
        min_val = curr_s
        min_count = 1
    elif curr_s == min_val:
        min_count += 1

자주 하는 실수 & 오류 예방

- 음수만으로 이루어진 배열의 초기값 오류: 배열의 모든 원소가 음수인 경우(예: `[-5, -2, -8]`), 최대 연속 부분합은 `-2`입니다. 하지만 최대합 변수의 초기값을 `0`으로 설정하고 카데인을 수행하면 결과가 `0`으로 출력되는 심각한 오답을 유발합니다. 항상 누적 최댓값의 초기값은 배열의 첫 번째 원소 `a[0]` 또는 `-float('inf')`로 초기화해야 합니다. - Prefix Sum 최솟값 갱신 타이밍 문제: 누적합 $S[i]$로 `min_val`을 갱신하는 코드는 현재 지점의 부분합 `S[i] - min_val`을 계산하고 최대값 판정을 마친 뒤에 실행되어야 합니다. 최솟값 갱신이 먼저 일어나면 $S[i] - S[i]$가 계산되어 구간의 크기가 0인 빈 부분배열(합 0)이 강제 포함되는 논리 오류가 발생합니다. - 파이썬 정수 오버플로: C++과 Java에서는 대용량 부분합 연산 시 32비트 정수형(`int`)의 범위를 넘어서 `long long`을 써야 하지만, 파이썬은 언어 차원에서 가용 메모리가 허용하는 한 오버플로 없이 자동으로 무한대 정수 연산을 보장하므로 오버플로에 대해 안전합니다.

핵심 정리

알고리즘 설계	시간 복잡도	공간 복잡도	실행 한계 ($N$의 한계)	핵심 특징 및 평가
3중 루프 브루트 포스	$O(N^3)$	$O(1)$	$N \le 500$	가장 원시적인 형태, 중복 구간 합 연산으로 극심한 비효율
2중 루프 누적합 최적화	$O(N^2)$	$O(1)$	$N \le 5,000$	구간 합 재사용으로 연산 1단계 단축, 여전히 대용량 부적합
분할 정복 (Divide & Conquer)	$O(N \log N)$	$O(\log N)$	$N \le 100,000$	문제를 절반씩 나누어 경계 구간 처리, 재귀 스택 공간 필요
카데인 / 누적합 최솟값 추적	$O(N)$	$O(1)$	$N \le 10,000,000$	동적 계획법 및 누적합 성질 활용, 최적의 선형 시간 돌파