코딩 테스트 공부 - 구간 합

코딩 테스트를 공부할 때 미리 자신만의 스니펫을 구성해두는 것을 추천한다.

 

간단한 코딩테스트의 경우 쉽게 문제를 풀 수 있지만, 난이도가 높은 문제일수록 쉬운 알고리즘들을 미리 스니펫을 구성해둔 상태로 진행하는 것이 시간을 단축 시킬 수 있다.

 

이번 포스팅에는 특정 구간에 대한 값의 합을 구하고 싶을 때, 사용되는 구간 합 스니펫을 구현해보았다.

시간 복잡도는 $ O(n) $ 이다.

 

배열 A 가 존재할 때, 배열 A의 인덱스까지의 누적 합을 배열 S 로 표현한 것은 다음과 같다.

S[i] = S[i-1] + A[i]

#include<iostream>
#include <vector>

int main() {
    vector<int> A;
    vector<int> S;

    A.push_back(1);
    A.push_back(2);
    A.push_back(3);
    A.push_back(4);
    A.push_back(5);
    A.push_back(6);
    A.push_back(7);
    A.push_back(30);

    // 벡터 S에 벡터 A의 누적 합을 저장
    for (int i = 0; i < A.size(); i++) {
        if (i == 0)
        S.push_back(A.at(i));
        else
        S.push_back(S.at(i - 1) + A.at(i));
    }

    // 벡터 A 출력
    for (int i = 0; i < A.size(); i++) {
        cout << A.at(i) << " ";
    }

    cout << endl;

    // 벡터 S 출력
    for (int i = 0; i < S.size(); i++) {
        cout << S.at(i) << " ";
    }

    return 0;
}

 

배열 S 에서 인덱스 i 부터 j 까지의 구간 합을 구하고 싶다면 다음과 같이 나타낼 수 있다.

구간 합 = S[j] - S[i-1]

    // 구간 합
    int start = 3;
    int end = 7;
    cout << endl;
    cout << S.at(end) - S.at(start - 1) << endl;

 

앞으로 이러한 간단한 알고리즘부터 스니펫을 적어놓으려고 한다.