교차항의 합을 누적합으로 풀어내 O(N²)을 O(N)으로 계산하기

zephyr·2026년 8월 24일

1. 개요

오늘 학교에서 갑자기 문득 든 생각이다.

어떠한 수열의 제곱의 합은 계산하기 빡세니까, 수열의 합의 제곱으로 바꾸어 계산하는 법이 없을까?

노트에 즉시 식을 써내려갔다.

2. 5개 항으로 유도해보기

$(x_1+x_2+x_3+x_4+x_5)^2=(x_1+x_2+x_3+x_4+x_5)(x_1+x_2+x_3+x_4+x_5)$
$=x_1x_1+x_2x_2+x_3x_3+x_4x_4+x_5x_5+2(x_1x_2+x_1x_3+x_1x_4+x_1x_5+x_2x_3+x_2x_4+x_2x_5+x_3x_4+x_3x_5+x_4x_5)\\$
$2(x_1x_2+x_1x_3+x_1x_4+x_1x_5+x_2x_3+x_2x_4+x_2x_5+x_3x_4+x_3x_5+x_4x_5)$
$=2\{x_1(x_2+x_3+x_4+x_5)+x_2(x_3+x_4+x_5)+x_3(x_4+x_5)+x_4(x_5)\}$

아 제곱의 합을 합의 제곱의 형태로 고치려면, 교차항의 합을 써야하구나. 어라? 이거 누적합이잖아.

$S_1 = x_1$
$S_2 = S_1 + x_2$
$S_3 = S_2 + x_3\\\vdots$
$S_5 = S_4+x_5\\$
$2\{x_1(x_2+x_3+x_4+x_5)+x_2(x_3+x_4+x_5)+x_3(x_4+x_5)+x_4(x_5)\}$
$=2\{x_1(S_5-S_1)+x_2(S_5-S_2)+x_3(S_5-S_3)+x_4(S_5-S_4)\}$
$=2\sum\limits_{k=1}^{4}{x_k(S_5-S_k)}$

이제 수식을 정리하여 완성해볼까?

$(x_1^2+x_2^2+x_3^2+x_4^2+x_5^2)=(x_1+x_2+x_3+x_4+x_5)^2-2\sum\limits_{k=1}^{4}{x_k(S_5-S_k)}$

3. 일반화

$X=(x_k)_{k=1}^n\quad n=|X|\\$
$S_n = S_{n-1}+x_n$
$\sum\limits_{k=1}^n{x_k^2}=(\sum\limits_{k=1}^n{x_k})^2-2\sum\limits_{k=1}^{n-1}{x_k(S_n-S_k)}$

4. 증명

$S_n-S_k=\sum\limits_{i=1}^{n}{x_i}-\sum\limits_{i=1}^{k}{x_i}=\sum\limits_{i=k+1}^{n}{x_i}\\$
$\sum\limits_{k=1}^{n-1}{x_k(S_n-S_k)}=\sum\limits_{k=1}^{n-1}{x_k\cdot\sum\limits_{i=k+1}^{n}{x_i}}=\sum\limits_{1\le k<i\le n}{x_kx_i}\\$
$\sum\limits_{k=1}^{n}{x_k^2}=(\sum\limits_{k=1}^{n}{x_k})^2-2\sum\limits_{1\le k<i\le n}{x_kx_i}$
$=(\sum\limits_{k=1}^{n}{x_k})^2-2\sum\limits_{k=1}^{n-1}{x_k(S_n-S_k)}\quad\text{Q.E.D.}$

5. 코드 구현 및 검증

파이썬

X = list(map(int, input().split(" "))); n = len(X)
S = [0] * n; S[0] = X[0]
for i in range(1, n): S[i] = S[i-1] + X[i]

a = sum(x**2 for x in X)
b = (S[n-1] ** 2) - (2 * sum( X[k] * (S[n-1] - S[k]) for k in range(n-1)))

print(f"original : {a}")
print(f"zephyr's method : {b}")

C++

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int N;
    cin >> N;

    vector<int> X(N);
    for (int i = 0; i < N; i++)
        cin >> X[i];

    vector<int> S(N); S[0] = X[0];
    for (int i = 1; i < N; i++)
        S[i] = S[i - 1] + X[i];

    int a = 0, b = 0;
    for (int i = 0; i < N; i++)
        a += X[i] * X[i];
    
    b = S[N - 1] * S[N - 1];
    for (int k = 0; k < N - 1; k++)
        b -= 2 * X[k] * (S[N-1] - S[k]);

    cout << "original :" << a << endl;
    cout << "zephyr's method :" << b;
}

$\\[0.5em]$

6. 마치며

학교에서 문득 든 생각으로 시작해서, 단순 수식 전개부터 누적합을 이용한 일반화 및 수학적 증명까지 완성해 보았다. 알고리즘 공부를 하며 배웠던 누적합이 여기서 쓰일 줄은 몰랐다. 내가 스스로 고민하여 도출해낸 첫 공식이라 뿌듯하다!

zephyr

All About CSE

2개의 댓글

asterunee

2026년 8월 24일

전체적으로 이 글은 작은 사례를 직접 관찰한 뒤 규칙을 찾아 일반화하고, 그 일반화가 실제로 성립하는지를 계산과 코드로 확인하는 흐름이 분명하다는 점에서 탐구 과정 자체는 잘 드러난다. 특히 여러 항 사이에서 반복되는 곱의 구조를 발견하고 이를 누적합의 형태로 정리하려고 한 발상은 단순 계산을 그대로 수행하는 데서 멈추지 않고 식의 내부 구조를 재해석하려 했다는 점에서 의미가 있다. 다만 글의 핵심 주장과 실제로 개선되는 계산 대상이 정확히 일치하지 않는다는 점은 반드시 수정해야 한다. 제곱한 값들의 합 자체는 각 원소를 한 번씩 확인하면서 바로 계산할 수 있으므로 처음부터 선형 시간에 구할 수 있다. 따라서 이 값을 다른 항등식으로 변형하여 다시 계산하는 것은 본질적인 시간복잡도 개선이라고 볼 수 없다. 실제로 계산량이 크게 줄어드는 대상은 서로 다른 두 원소를 선택하여 곱한 값들을 모두 더하는 부분이다. 이 값을 가장 직접적인 방식으로 계산하면 가능한 모든 두 원소의 조합을 확인해야 하므로 원소 수가 증가할수록 계산량이 제곱에 비례하여 증가하지만, 글에서 도출한 누적합 구조를 이용하면 각 원소를 한 번씩 처리하는 방식으로 바꿀 수 있다. 따라서 글의 중심을 제곱합 계산의 개선이라고 설명하기보다는 모든 두 원소의 곱의 합을 반복적인 쌍 탐색 없이 계산하는 방법을 발견했다고 정리하는 편이 논리적으로 훨씬 정확하다. 이 차이를 명확히 하지 않으면 독자는 원래부터 선형 시간에 계산 가능한 문제를 불필요하게 복잡한 수식으로 바꾸어 놓고 이를 최적화라고 주장하는 것으로 받아들일 수 있다. 수학적 서술 방식에서도 몇 가지 엄밀성이 부족하다. 글에서는 원소들을 집합처럼 표기하고 있지만 실제 전개에서는 첫 번째 원소, 두 번째 원소와 같이 순서가 사용되고 특정 위치까지의 합을 계속 참조하고 있으므로 집합이 아니라 순서를 가진 수열로 다루는 것이 정확하다. 집합은 기본적으로 원소의 순서를 구분하지 않는 개념이므로 누적합과 같이 위치에 의존하는 연산을 설명할 때는 적절한 객체가 아니다. 누적합 역시 마지막 값과 이전 값의 관계만 제시하는 것보다 처음부터 몇 번째 원소까지의 합을 나타내는 하나의 명확한 정의를 두는 것이 좋다. 그렇게 하면 이후 등장하는 각 차이가 어느 구간의 합을 의미하는지가 자연스럽게 따라오며 증명 과정에서 별도의 직관적 설명에 의존할 필요가 줄어든다. 현재 글의 증명은 구체적인 항들을 길게 펼친 뒤 패턴을 확인하고 이를 일반적인 형태로 옮기는 방식인데, 발견 과정으로서는 자연스럽지만 최종 글의 증명으로는 중복이 많다. 핵심은 전체 합을 제곱했을 때 각 원소의 제곱뿐 아니라 서로 다른 두 원소의 곱이 두 번씩 등장한다는 사실이고, 이후에는 특정 원소를 기준으로 자신보다 뒤에 있는 모든 원소와의 곱을 묶으면 누적합의 차이로 표현할 수 있다는 구조다. 이 두 사실만 명확하게 설명하면 훨씬 짧으면서도 논리 구조는 오히려 더 선명해진다. 좋은 수학적 설명은 계산 과정을 많이 보여주는 것이 아니라 각 변형이 왜 가능한지와 각 항이 무엇을 세고 있는지를 독자가 한 번에 파악할 수 있도록 구성하는 것이 중요하다. 구현 측면에서도 현재 방식은 단순한 제곱합 계산보다 오히려 중간 계산값의 크기를 크게 만들 수 있다는 문제가 있다. 원래 계산하려는 최종 결과가 정수형 범위 안에 충분히 들어가더라도 전체 합을 먼저 계산하고 그것을 다시 곱하는 과정에서는 훨씬 큰 값이 발생할 수 있다. 따라서 최종 답의 범위만 보고 자료형을 선택하면 안 되며, 계산 과정에서 등장하는 가장 큰 중간값까지 분석하여 자료형을 결정해야 한다. 이는 단순히 정수형을 더 큰 자료형으로 교체하면 끝나는 문제가 아니라, 식을 다른 형태로 변형했을 때 연산 범위가 어떻게 달라지는지까지 검토해야 한다는 의미다. 특히 입력값의 절댓값과 원소 개수에 대한 제한이 주어졌다면 전체 합이 가질 수 있는 최대 크기, 두 값의 곱이 가질 수 있는 최대 크기, 이러한 값들이 누적될 때의 최대 범위를 각각 상한으로 계산하여 안전성을 증명하는 것이 바람직하다. 현재 코드에서는 이러한 분석 없이 기본 정수형을 사용하고 있어 특정 입력에서는 논리적으로 올바른 알고리즘이더라도 구현 결과가 잘못될 가능성이 있다. 메모리 사용 역시 더 개선할 수 있다. 모든 누적합을 배열에 저장하지 않고 지금까지 등장한 원소들의 합 하나만 유지하면 새로운 원소가 들어올 때 그 원소와 이전 모든 원소 사이의 곱의 총합을 한 번에 계산할 수 있다. 이후 현재 원소를 누적합에 더하면 다음 단계에서도 동일한 연산을 반복할 수 있다. 이 방식은 전체 누적합 배열을 저장할 필요가 없으므로 추가 메모리를 상수 수준으로 줄일 수 있고, 전체 입력을 미리 알고 있어야 할 필요도 없다. 즉 원소가 하나씩 주어지는 상황에서도 즉시 결과를 갱신할 수 있으며, 이런 성질은 단순한 공간 최적화를 넘어 알고리즘이 온라인 방식으로 동작할 수 있음을 의미한다. 현재 글에서 사용하는 방식은 전체 합을 먼저 알아야 뒤쪽 원소들의 합을 계산할 수 있기 때문에 입력 전체를 알고 있다는 전제가 들어가지만, 이전 원소들의 합을 유지하는 방향으로 관점을 바꾸면 미래의 입력에 대한 정보가 전혀 필요하지 않는다. 이 차이를 설명하면 글의 알고리즘적 깊이가 크게 높아진다. Python 구현에서 중간 결과를 굳이 리스트로 변환한 뒤 합을 구하는 부분도 제거하는 것이 좋다. 필요한 것은 각 항을 차례대로 생성하여 합산하는 것이므로 모든 값을 메모리에 저장할 이유가 없다. 이처럼 코드에서도 수학적으로 줄인 계산량과 실제 메모리 사용량이 일치하도록 구성해야 한다. 또한 입력을 특정 개수의 공백에 의존하여 분리하기보다 공백 문자를 일반적으로 처리하는 방식을 사용하는 것이 더 견고하다. 글의 마지막에서 스스로 고민하여 공식을 도출했다는 표현은 탐구의 동기를 보여주는 데에는 좋지만, 독자에게 해당 관계 자체가 새로운 수학적 결과라는 인상을 주지 않도록 표현을 조정하는 것이 필요하다. 중요한 가치는 이 관계가 기존에 존재하는지 여부가 아니라, 주어진 계산 구조를 스스로 분석하여 이미 널리 알려진 대수적 구조와 동일한 결과에 독립적으로 도달하고 그것을 실제 알고리즘으로 변환했다는 데 있다. 새로운 정리를 발견했다는 식의 표현보다 기존의 일반적인 항등식과 같은 구조를 직접 유도했으며 이를 누적합을 이용한 계산 방식으로 연결했다고 서술하는 편이 더 정확하고 신뢰도도 높다. 또한 글이 탐구 기록인지 알고리즘 해설인지 성격을 더 명확하게 정할 필요가 있다. 탐구 기록이라면 처음 작은 사례를 전개하고 시행착오를 보여주는 현재 방식이 충분히 의미 있지만, 알고리즘 해설이라면 발견 과정은 짧게 줄이고 문제 정의, 단순한 방법의 계산량, 구조적 변형, 개선된 방법의 계산량, 메모리 사용량, 정수 범위 분석, 구현 순서의 형태로 재구성하는 것이 훨씬 효과적이다. 특히 개선 전과 개선 후의 계산량을 주장할 때는 단순히 반복문의 개수만 보고 판단하지 말고 실제로 무엇을 계산하는 알고리즘인지 동일한 문제를 기준으로 비교해야 한다. 현재 글의 가장 큰 논리적 약점도 바로 이 부분으로, 원래 제곱합을 계산하는 단순한 방법과 서로 다른 원소 쌍의 곱을 계산하는 중간 과정을 혼합하여 비교하고 있기 때문에 복잡도 개선의 대상이 흐려진다. 이 부분만 정확히 정리해도 글의 완성도가 상당히 높아진다. 종합하면 이 글의 강점은 구체적인 계산에서 규칙을 발견하고 일반화한 뒤 코드로 확인하는 탐구 능력과, 반복되는 두 원소의 곱을 누적합이라는 계산 구조로 변환한 발상에 있다. 반면 가장 큰 약점은 최적화하고 있는 대상의 정의가 불명확하다는 점, 순서를 가진 수열을 집합처럼 다루는 표기상의 문제, 증명의 핵심 구조에 비해 전개가 길다는 점, 중간 계산값에 대한 범위 분석이 없다는 점, 누적합 배열 없이도 계산할 수 있다는 사실과 온라인 처리 가능성을 고려하지 않았다는 점이다. 이러한 부분을 수정한다면 단순한 식 변형 기록을 넘어 하나의 계산식을 어떻게 다른 관점으로 재구성하여 시간과 공간의 관점에서 효율적인 알고리즘으로 바꿀 수 있는지를 보여주는 훨씬 완성도 높은 글이 될 수 있다.

p.s.
언젠가 많이 성장한 zephyr 이 댓글을 다시 보게 된다면 얼마나 성장했는지를 알 수 있을것이다. 원래, PS든 수학이든 만들어진 길과 누군가의 발자취를 따라가는것이 아니다. 내가 발자취를 남기고, 길을 편하게 개척하는 과정이다. 하지만, 발자취가 완성되고 편한 길이 개척된 순간 나 자신은 그 위치에 없을 것이다. 새로운 험한 길을 '탐구'라는 하나의 원동력을 등에 업은 채로 개척하고있을것이니까.
-2026.08.25, PS/수학 후배 중 zephyr를 첫번째로 아끼는 asterunee형이-

1개의 답글