[C++] 온도의 최대값

내 코드

#include <iostream>
#include <vector>

using namespace std;
int main() {
    int N,K,i,j,sum = 0,max = -2147000000;
    int d[100000];
    scanf("%d %d", &N, &K);
    
    for(i = 0; i < N; i++){
        scanf("%d",&d[i]);
    }
  
    for(i = 0; i < N-K; i++ ){
        for(j = i; j < K+i; j++){
            sum += d[j];
        }
        if(sum > max) {
            max = sum;
            sum = 0;
        }
    }
    
    printf("%d",max);
    return 0;
}

• 1초라는 제한이 있었기 때문에 위 코드를 작성하기 전부터 잘못된 방식임을 알았다.
• 위 코드대로하면 worst case가 $N^2$으로 10만 x 10만이라서 100억 = 100초 정도이기 때문이다.
• 또한 배열을 10만정도 할당하고 있는 것은 메모리 낭비라는 것도 알고 있었다.(vector를 활용하자는 생각까지 도달하였다.)
• 하지만, 문제의 순열에 대한 규칙성을 찾지 못하여 답을 유추해내지 못하였다.

효율적인 답

#include <iostream>
#include <vector>

using namespace std;
int main() {
    int N,K,i,sum = 0,max = -2147000000;
    
    scanf("%d %d", &N, &K);
    
    vector<int> d(N);
    for(i = 0; i < N; i++){
        scanf("%d",&d[i]);
    }
    
    for(i = 0; i < K; i++){
        sum += d[i];
    }
    
    max = sum;
    
    for(i = K; i < N; i++){
        sum = sum + (d[i] - d[i-K]);
        if(sum > max) max = sum;
    }
    
    printf("%d",max);
    return 0;
}

• big O natation이 N만큼으로 매우 효율적으로 바뀌었다.
• 규칙성이라기보단 배열의 묶음 계산을 보다 효율적으로 처리하는 방법이 제시되었다.

• i가 2번 인덱스인 4를 가리키고 있다고 가정하자.
• -2와 4를 더한 값은, 3와 -2를 더한 값에서 3을 빼버리고 4를 더하면 된다.(신박한 재미있는 방법이지만 큰 효율을 가진다.. 재밌다)
• 공식으로 따지면 sum = sum - d[i-K] + d[i]이다.
• i-K때문에 인덱스가 0,1인 경우에는 에러가 뜰 수 있기 때문에
• K번째 인덱스까지는 SUM을 미리 구해놓아야 한다.

성찰

• 배열에서 묶음 덧셈을 처리하기 위한 좋은 알고리즘이다.
• 어떻게 이걸 생각하지..라기 보단 새로운걸 알았다고 생각하고 다음번에 꼭 써먹자