Prefix Sum: 초급

발행: 3일 전 (2026년 2월 25일 오전 11:18 GMT+9)

8 분 소요

Source: Dev.to

If you’ve ever looked at a coding challenge and felt like you were staring at a brick wall, you aren’t alone. Most of the time, the secret isn’t about being a math genius—it’s about recognising the pattern.

코딩 챌린지를 보고 마치 벽을 바라보는 듯한 느낌을 받은 적이 있다면, 혼자가 아닙니다. 대부분의 경우 비밀은 수학 천재가 되는 것이 아니라 패턴을 인식하는 것입니다.

In this series we break down the most essential coding patterns—from beginner to expert level—keeping things simple, practical, and (hopefully) a little bit fun.

이 시리즈에서는 초급부터 전문가 수준까지 가장 필수적인 코딩 패턴을 간단하고 실용적으로, (가능하면) 조금은 재미있게 풀어봅니다.

Today we’re diving deep into Prefix Sum.

오늘은 **Prefix Sum(누적 합)**에 대해 깊이 파헤쳐 보겠습니다.

Whether you’re preparing for a big interview or just trying to write cleaner, faster code, mastering this pattern is a total game‑changer.

큰 면접을 준비하든, 더 깔끔하고 빠른 코드를 작성하려 하든, 이 패턴을 마스터하는 것은 완전한 게임 체인저입니다.

Let’s strip away the jargon and see how it actually works!

전문 용어를 벗겨내고 실제로 어떻게 작동하는지 살펴봅시다!

Prefix Sum이란?

긴 도로의 시작에 서 있다고 상상해 보세요. 그리고 매 마일마다 그 지점에 묻혀 있는 동전이 몇 개 있는지 알려주는 표지판이 있습니다.

제가 “마일 3과 마일 8 사이에 동전이 몇 개 있나요?” 라고 물으면, 보통은 3에서 8까지 걸어가면서 하나씩 더해야 할 것입니다.

짧은 거리라면 괜찮지만, 도로가 10 000 마일 길고 제가 1 000개의 서로 다른 질문을 한다면 어떨까요? 금방 지칠 겁니다!

Prefix Sum은 배열의 “누적 합”을 미리 계산하는 전처리 기법입니다. 앞서 약간의 작업을 하면, 어떤 “구간 합” 질문도 O(1) 시간에 답할 수 있어 반복적인 덧셈 작업을 간단한 뺄셈으로 바꿀 수 있습니다.

수학적 논리

우리는 새로운 배열(prefix)을 만들고, 그 배열의 각 인덱스 i에 원본 배열 arr의 시작부터 해당 인덱스까지의 모든 요소의 합을 저장합니다.

공식

prefix[i] = arr[0] + arr[1] + … + arr[i]

더 효율적인 재귀식

prefix[i] = prefix[i‑1] + arr[i]   (i > 0인 경우)

간단한 예시

arr = [3, 1, 4, 1, 5]

Index 0: 3
Index 1: 3 + 1 = 4
Index 2: 4 + 4 = 8
Index 3: 8 + 1 = 9
Index 4: 9 + 5 = 14

prefix = [3, 4, 8, 9, 14]

인덱스 2부터 4까지(4, 1, 5)의 합을 구하려면:

result = prefix[4] – prefix[1] = 14 – 4 = 10

왜 이렇게 동작하는가:

prefix[4] = A0 + A1 + A2 + A3 + A4
prefix[1] = A0 + A1
=> prefix[4] – prefix[1] = A2 + A3 + A4

효율성 및 복잡도

시간 복잡도

Without Prefix Sum: 각 구간 쿼리는 **O(N)**의 비용이 들며, 따라서 M개의 쿼리는 **O(M × N)**이 된다.
With Prefix Sum: prefix 배열을 한 번 만드는 데 **O(N)**이 소요되고, 각 쿼리는 **O(1)**이다.

공간 복잡도

일반적으로 크기 N인 추가 배열을 할당하여 **O(N)**의 보조 공간을 사용한다.
원본 배열을 덮어쓰면 **O(1)**의 추가 공간만 필요하게 된다.

빅‑O 표기법에 대한 빠른 복습이 필요하다면, 이전 가이드를 확인하세요 here.

어디에 사용되나요? (응용 분야)

재무 및 영업 분석 – 맞춤 날짜 범위에 대한 즉시 총계.
이미지 처리 – 2‑D Prefix Sum(합계 영역 테이블)은 블러링, 특징 검출 등에서 상수 시간 사각형 합을 가능하게 합니다.
웹 분석 – 시계열 데이터에 대한 누적 방문자 또는 활성 사용자.
데이터베이스 쿼리 최적화 – 범위 스캔 및 집계 쿼리를 가속화합니다.
게임 개발 – 누적 점수, 자원, 또는 2‑D 조명/그림자 계산.

Classic Interview Problems

Range Sum Query – 두 인덱스 사이의 합을 반복적으로 찾는다.
Pivot Index – 왼쪽 요소들의 합과 오른쪽 요소들의 합이 같은 인덱스를 찾는다.
Subarray Sum Equals K – Prefix Sum과 해시 맵을 결합하여 합이 K인 부분 배열의 개수를 센다.
Maximum Subarray (Kadane’s variant) – Prefix Sum을 사용해 최소/최대 prefix 값을 계산한다.

이러한 패턴을 일찍 인식하면 면접에서 시간과 스트레스를 크게 절감할 수 있습니다.

Implementation

이제 이 패턴을 실제로 살펴보겠습니다!

시연을 위해 **C#**을 사용할 예정입니다. 하지만 평소에 Python, Java, JavaScript 등 다른 언어로 코딩한다 하더라도 언어 선택에 얽매이지 마세요. 로직과 기본 패턴은 모든 언어에서 동일하게 적용되며, 차이는 문법뿐입니다. 원하는 언어로 따라 해 보면서 로직을 구현해 보세요.

using System;

public class PrefixSumExample
{
    public static void Main()
    {
        int[] nums = { 3, 1, 4, 1, 5 };

        // Preprocessing: Build the Prefix Sum Array
        int[] prefixSum = BuildPrefixSum(nums);

        // Querying: Get sum of range [index 1 to 3] (values: 1, 4, 1)
        // Expected: 6
        int result = GetRangeSum(prefixSum, 1, 3);

        Console.WriteLine("\nSum of range [1 to 3]: " + result);
    }

    public static int[] BuildPrefixSum(int[] A)
    {
        int n = A.Length;
        int[] P = new int[n];

        // The first element is always the same
        P[0] = A[0];

        for (int i = 1; i  // Incomplete loop shown as in the original source
    }
}

막히더라도 낙담하지 마세요! 목표는 5분 안에 모든 문제를 푸는 것이 아니라 패턴을 인식하는 것입니다. 즐거운 코딩 되세요!

Stay Connected

다음 채널을 팔로우하여 최신 인사이트와 튜토리얼을 받아보세요:

문의 사항, 게임 제안, 질문 등이 있으면 이메일을 통해 언제든지 연락 주세요: . 여러분의 궁금증을 해결해 드리겠습니다!

앞으로도 기사와 개발 팁을 놓치지 마세요!