[코드트리] Intermediate Mid - Shorten Time Technique[Prefix Sum]

Shorten Time Technique

문제 해결 방식의 시간복잡도를 줄이는 기술이다.

Prefix Sum[누적합]

누적합 배열을 만들어서 시간복잡도를 줄인다.

 

 특정 배열이 주어졌을 때, 그 배열을 통해서 배열의 값들에 대해 누적된 합을 '누적합 배열'에 저장한다. '누적합 배열'의 인덱스가 올라갈 때마다, 원래 주어진 특정 배열에서 접근하는 값의 인덱스도 올라간다.

 

Ex) 특정한 배열이 주어졌을 때, 단순하게 0번부터 현재 인덱스까지의 합을 누적합 배열에 넣는다고 가정하자. 그렇다면, 특정 배열의 값이

1

3

7

11

23

이렇게 주어진다면, 누적합 배열은

1

4

11

22

45

이렇게 배열이 구성된다.

 

 누적합 배열[0]=특정 배열[0],누적합 배열[1]=특정 배열[0]+특정 배열[1], 누적합 배열[2] = 특정 배열[0] + 특정 배열[1] + 특정 배열[2], ...

 

정말 단순하게, 누적시킨 값을 원소로 집어넣은 것이 누적합 배열이다! 누적합 배열 만들 때, O(N)의 시간복잡도.

---

필요성 : N개의 원소를 가진 특정 배열의 특정 인덱스부터 또 다른 특정 인덱스까지의 합을 구하고자 한다면, 그 자체만으로도 O(N)이다. 그런데, 이걸 여러 번 반복해야한다면? 총 Q번, 이러한 요구를 들어줘야한다면, 시간복잡도는 O(N*Q)가 걸리게 된다.

효용성 : 하지만, 이걸 사용하면, 먼저 누적합 배열 만들기 O(N), 그리고 Q번 요구를 들어줘야한다면, 누적합 배열을 통해서 요구에 대한 값을 구할 수 있으므로 배열의 값 접근은 O(1)로 총 시간 복잡도는 O(N)+O(Q)가 걸리게 된다.

 

효용성에서 어떻게 저렇게 줄일 수 있는지는 다음의 문제를 통해서 이해해보자.

[아래 문제까지 읽기 힘들다면]

O(Q*N)은 이중 반복문을 사용한다.
Q번 반복해서, 배열에 접근하는데 for문으로 접근하여 배열을 차례 차례 더해주는 반복을 거치기 때문에 O(Q*N)이 걸리고,

 

누적합 배열을 만든 O(N)+O(Q)는 먼저 누적합 배열 만들고{O(N)}, 7번에서 18번까지의 원소들의 합을 구하려면 누적합 배열[18]-누적합 배열[6]을 하면 간단하게 구해진다.이걸 Q번 반복하게 된다.{O(Q)}----> O(N)+O(Q)

 

누적합 배열을 만들면 시간복잡도가 줄어들게 된다.

코드트리 문제

코드트리-정수 n개의 합 2

https://www.codetree.ai/missions/8/problems/sum-of-n-integers-2?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

코드트리 - 정수 n개의 합 문제

 

 

#include <iostream>
#include <array>
using namespace std;
//이 문제도 DP를 이용해서 풀어보자.
int dp(int arr[],int N,int K) {
    //arr은 누적합 배열을 넣는다.
    if (N == 0) return 0;
    int dp[N]={0,};

    dp[1] = arr[K];
    //누적합 배열에서 K번째 원소가 연속되는 K개의 배열의 초기값이 DP의 초기값이 된다.
    //0~K까지의 합이 정수 K개의 합이니까.
    int maxSum = dp[0];

    for (int i = 1; i < N-K; ++i) {
        dp[i] = max(dp[i], arr[K+i] - arr[i]);
        // [1][2][3][4][5][6][7][8][9][10] 예를 들어 10,4가 입력으로 들어왔을 때 배열은 이렇고
        // 여기~~~~~~여기 1에서 4까지가 처음 dp[0] 값이고,

        //[2][3][4][5]랑 dp[1]을 비교해서 더 큰 값이 dp[2]이 되고,
        //[3][4][5][6]이랑 dp[2]를 또 비교해서 dp[3] 찾고,
        //...

        //반복하면, [7][8][9][10]까지의 합 까지 확인하면 끝이니까 (10-4=6)번 반복하니까 N-K번
        //배열 원소를 4개 계속 꺼내기 힘드니까 이 함수에서 arr이 누적합 배열을 이용한다.

        //기본개념에서 이용되는 x와 y까지의 합을 구하는 방식을 이용했다.

        // 최대 합을 갱신
        maxSum = max(maxSum, dp[i]);
        
    }

    return maxSum;
}


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

    int arr[N+1];
    //N개의 정수를 받는다.
    for(int input_how=1; input_how<=N;input_how++){
        cin >> arr[input_how];
    }

    int prefix_sum[N+1];
    
    prefix_sum[0] = 0;
    //누적합 배열을 생성한다.
    for(int prefix_times=1; prefix_times<=N;prefix_times++){
        prefix_sum[prefix_times] = prefix_sum[prefix_times-1] + arr[prefix_times];
    }
    
    //dp를 통해 답을 구한다.
    int result = dp(prefix_sum,N,K);
    cout << result << '\n';

    return 0;
}

n개의 원소를 받아 누적합 배열을 만들고, 연속하는 k개의 원소들의 합 중 제일 큰 값을 찾아야 한다. 위에서 DP 사용이라고 하지만, DP 아니다!!(문제 풀 당시 졸려서 저런 걸 썼나보다.)

 

 먼저 함수 dp에는 누적합 배열을 넣고, 배열의 원소 개수 및 얼마나 연속하는지 N,K가 들어가게 된다. K개의 연속되는 원소들의 합은 N-K개가 만들어지게 된다. (이건 직접 배열을 그려보면 바로 알 수 있다.) 그래서 누적합 K+i 번째 인덱스에서 누적합 i 번째를 빼면 딱 K개의 연속되는 원소들의 합이 만들어지게 된다. 이걸 i = 1부터 N-K까지 인덱스 순회하면 된다. (이미 i=0을 구해놨기 때문에)

 

 함수에서는 K개의 원소들의 합의 값을 넣는 dp라는 배열이 만들어진다. 사실 저 배열은 없어도 된다.

 

 그냥 for문은 그대로 두고, dp[i] 대신 temp라는 변수를 넣어서 이전의 합 값과 지금 인덱스의 합 값을 max()로 비교하고 더 큰 값을 temp에 넣고, for문을 진행하면 된다. 그러면 모든 [k개의 연속되는 원소들의 합]을 순회하고 제일 큰 값이 temp에 남게되기 때문이다.

 

메모리를 덜 쓰는 방식이다.(난 dp한다고 저렇게 해버렸나보다. 다시 말하지만 동적계획법:DP 아니다!!)

 

코드트리-정수 n개의 합 3

https://www.codetree.ai/missions/8/problems/sum-of-n-integers-2?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

#include <iostream>
#include <array>
using namespace std;
//dp는 사실 dp를 이용한 건 아니라 귀찮아서..
int dp(int arr[][500],int N,int K) {

    //arr은 누적합 배열을 넣는다.
    if (N == 0) return 0;

    //how는 큰 정사각형 N*N 에서 작은 정사각형 K*K 으로 몇 번 순회하는지 횟수를 나타내는 변수.
    int how=N-K+1;

    //ㅁㅁㅁㅁ
    //ㅁㅁㅁㅁ
    //ㅁㅁㅁㅁ
    //ㅁㅁㅁㅁ
    //여기서 N=4,K=2일 경우, 정사각형의 우측 하단 꼭짓점이 움직일 수 있는 부분은 (2,2)~(4,4)를 대각선으로 하는 3*3의 정사각형이다.
    //N=4,K=3일 경우에는 ,2*2의 정사각형으로, N-K+1의 횟수를 반복한다는 걸 알 수 있다.
    int dp[how+1][how+1]={0,};

    dp[0][0] = arr[K][K]-arr[0][K]-arr[K][0]+arr[0][0];
    //얘는 (1,1)에서 (k,k)의 대각선인 정사각형이다. 이게 제일 첫 정사각형으로 얘를 시작으로 계속 순회할 것이다.
    
    //원래는 dx,dy로 움직일까 했는데, 둘 다 정사각형이란 특징, 숫자의 최대 합만 구하니까 단순하게 움직이게 했다.
    
    int maxSum = 0;
    //아래 이중 반복문은 작은 정사각형의 순회좌표를 (k,k)를 기준으로 순회하는 걸 뜻한다.
    for(int i = 0; i < how; ++i) {
        for(int j=0; j<how;j++){
            dp[i][j] = arr[K+i][K+j]-arr[0+i][K+j]-arr[K+i][0+j]+arr[0+i][0+j];
            maxSum = max(maxSum, dp[i][j]);
        }
    }
    return maxSum;
}


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

    int arr[N+1][N+1];
    //N*N개의 정수를 받는다.
    for(int input_col=1; input_col<=N;input_col++){
        for(int input_row=1;input_row<=N;input_row++)
        cin >> arr[input_col][input_row];
    }

    //누적합 배열을 생성한다.
    int prefix_sum[500][500]={0,};

    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= N; j++)
            prefix_sum[i][j] = prefix_sum[i - 1][j] + 
                               prefix_sum[i][j - 1] -
                               prefix_sum[i - 1][j - 1] +
                               arr[i][j];

    //함수 dp를 통해 답을 구한다 dp는 동적계획법이 아니라 이전 코드에서 참고하다가 이름을 고치지 않은 거다.
    int result = dp(prefix_sum,N,K);
    cout << result << '\n';

    return 0;
}

여기도 어김없이 dp가 등장하는데 동적 계획법 아니다!

이번 누적합 배열은 2차원 배열이다. 큰 정사각형의 숫자들에서 작은 정사각형 안에 숫자들의 합이 제일 큰 것을 찾는 것이다.

 

큰 정사각형을 작은 정사각형으로 스캔한다고 생각하면 된다. 그렇게 되면 만들어지게 되는 정사각형의 개수를 알 수 있다.

 

방법 1. 큰 정사각형의 범위를 확인하고, 좌표를 갖는 변수 x,y를 설정, x,y를 바꾸면서 정사각형을 순회한다.

 

방법 2. 특수 경우로 순회하는 좌표의 제한 범위가 이미 주어진 변수(큰 정사각형의 변, 작은 정사각형의 변의 크기)를 통해서 정사각형을 순회하는 것을 제어한다.

 

방법 1이 어렵긴 하지만 보편적, 방법 2는 내가 사용했다. 여기서 정사각형이니까 주석을 보면 알 수 있듯이 풀기 쉽다.

 

누적합을 이용하는데, 방법 2는 정사각형의 우측 아래 꼭지점을 기준으로 순회하기로 했다. 이 순회 좌표는 제일 먼저 얻을 수 있는 작은 정사각형의 좌표 (K,K)를 통해서 (N : 큰 정사각형의 변 크기) N - K+ 1 번 반복하면 모든 정사각형을 확인할 수 있다. 좌표를 움직일 때도 K에서 for문을 통해서 i와 j를 더해주며 움직이면 끝이기 때문에 정사각형 순회가 쉽다.

 

역시 여기서도 dp[][] 배열은 필요 없다. temp 변수 설정해서 max로 비교하면 그만이다. 메모리를 덜 쓰도록 하자.

 

글꼬리

이렇게 누적합 배열(1차원, 2차원)을 이용해서 시간복잡도를 줄이는 방법을 알 수 있게 됐다. 확실히 알고리즘을 배우니까 시간복잡도 같은 것도 신경쓰게 되고 더 효율적인 코드를 짤 수 있게 된 것 같아 좋다.