누적합(Prefix Sum)

井·2025년 2월 3일

2차원누적합 DP Prefix sum TwoPointer python slidingwindow 누적합 다이나믹프로그래밍 슬라이딩윈도우 알고리즘 투포인터

알고리즘

목록 보기

3/4

📌 누적합(Prefix Sum)

배열 또는 리스트 등에서 일정 구간의 합을 빠르게 계산하기 위한 DP 형태의 방법

배열의 합을 구하는 문제에서, 배열의 원소 개수 N, 케이스 개수 M이 있을 경우, 시간 초과가 나는 경우가 대부분. 따라서 미리 저장해 둬서, O(1)로 시간을 줄임.

📕 시간 복잡도 분석

전처리 : 배열 A의 길이가 n일 때, 전체 원소를 한 번씩 순회하며 누적합을 구하므로 O(n)
구간 합 쿼리 처리: 합 쿼리는 상수 시간을 가짐

📕 누적합 알고리즘의 활용

📗 2차원 누적합

기본 공식

P[i][j]=P[i−1][j]+P[i][j−1]−P[i−1][j−1]+A[i][j]

🔖예시

def prefix_sum_2d(A):
  """
  2차원 배열 A에 대해
  P[i][j] = (0,0)부터 (i,j)까지 부분합을 저장한 2차원 누적합 배열 P를 계산해 반환
  """
  n = len(A)         # 행(row) 수
  m = len(A[0])      # 열(column) 수
  P = [[0]*(m+1) for _ in range(n+1)]  
  # (n+1) x (m+1) 크기로 잡아 경계 문제 회피 (1-based index 활용)

  for i in range(1, n+1):
      for j in range(1, m+1):
          P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + A[i-1][j-1]

  return P

def range_sum_2d(P, r1, c1, r2, c2):
  """
  누적합 배열 P를 이용해 A[r1:r2+1, c1:c2+1] 부분합을 O(1)에 구한다.
  여기서 P는 1-based, (r1, c1), (r2, c2)는 0-based로 가정.
  """
  # 인덱스 보정: 실제 P에서의 좌표는 +1 되어야 함
  R1, C1, R2, C2 = r1+1, c1+1, r2+1, c2+1

  return P[R2][C2] - P[R2][C1-1] - P[R1-1][C2] + P[R1-1][C1-1]

# 사용 예시
  A = [
      [1, 2, 3],
      [4, 5, 6],
      [7, 8, 9]
  ]
P = prefix_sum_2d(A)
# (0,0) ~ (1,1) 즉, [[1,2],[4,5]] = 1+2+4+5 = 12
print(range_sum_2d(P, 0, 0, 1, 1))  # 12 출력

활용 : 이미지 처리 및 다차원 확장

📗 투 포인터(Two Pointer)

정의 및 기본 아이디어

투 포인터는 연속 부분 배열(슬라이싱된 구간)의 문제를 해결할 때 매우 자주 사용하는 기법

인덱스 2개(보통 left, right)를 쓰면서 조건에 따라 이동시켜가며, 구간 합(또는 다른 통계량)을 갱신

🔖예시

def min_subarray_len(target, nums):
    """
    예: nums의 연속된 부분합이 target 이상이 되는 부분 배열 중
        최소 길이를 구해 반환. 
        (만약 없으면 0)
    """
    n = len(nums)
    left = 0
    current_sum = 0
    min_len = float('inf')

    for right in range(n):
        current_sum += nums[right]
        # 현재 구간합이 목표 이상이면 left를 이동하면서 구간을 축소
        while current_sum >= target:
            min_len = min(min_len, right - left + 1)
            current_sum -= nums[left]
            left += 1

    return 0 if min_len == float('inf') else min_len

# 사용 예시
nums = [2, 3, 1, 2, 4, 3]
target = 7
print(min_subarray_len(target, nums))  # 결과: 2 (부분 배열 [4,3])

📗 슬라이딩 윈도우(Sliding Window)

정의 및 기본 아이디어

배열(또는 리스트)에서 연속된 부분 배열(subarray)을 간단히 “윈도우(window)”라고 부르며, 이 창(윈도우)을 좌우(또는 양방향)로 슬라이딩(이동)시키면서 필요한 값을 계산하는 알고리즘 기법

인덱스 2개(보통 left, right)를 쓰면서 조건에 따라 이동시켜가며, 구간 합(또는 다른 통계량)을 갱신

🔖예시

def min_subarray_len(target, nums):
    n = len(nums)
    left = 0
    current_sum = 0
    min_length = float('inf')

    for right in range(n):
        current_sum += nums[right]

        # 현재 구간 합이 target 이상인 동안, left를 이동시켜 가능한 한 구간을 축소
        while current_sum >= target:
            min_length = min(min_length, right - left + 1)
            current_sum -= nums[left]
            left += 1

    return 0 if min_length == float('inf') else min_length

# 테스트
nums = [2, 3, 1, 2, 4, 3]
target = 7
print(min_subarray_len(target, nums))  # 2 ([4,3])