내 코드
#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을 미리 구해놓아야 한다.
성찰
- 배열에서 묶음 덧셈을 처리하기 위한 좋은 알고리즘이다.
- 어떻게 이걸 생각하지..라기 보단 새로운걸 알았다고 생각하고 다음번에 꼭 써먹자