<프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략> 이동 평균 계산하기
알고리즘 문제 해결 전략
프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략, 구종만 지음, 인사이트, ISBN 978-89-6626-054-6 새 소식 책 소개 <알고리즘 문제 해결 전략>은 새로운 알고리즘 책입니다. 종이에 적힌 의사코드를 외우며 알고리즘을 배우는 대신, 해당 알고리즘을 적용해 푸는 프로그래밍 문제들을 직접 풀어보며 알고리즘 설계 기법과 자료 구조에 대해 배울 수 있도록 구성되어 있습니다. 풀이 과정은 독자가 글쓴이의 머릿속에서 일어난 문제 해결 과정을 최대한
book.algospot.com
책의 94쪽부터 나오는 이동평균 계산하기. 여러 개의 관찰 값에 대해서 M-이동평균을 마지막 M개 값의 평균으로 정의할 때, 모든 M이동 평균을 계산하는 프로그램을 작성해보자.
'너무 쉬워서 하품이 나올 것 같은 기분을 꾹 참고 키보드에 손을 올려 봅시다..' 라고 본문에 나와 있다. 새삼 내 실력이 얼마나 바닥을 기고 있는지 되새겨 주는 문장이다. 음...
코드는 다음과 같다. vector는 한번도 사용해 본적 없었는데, 이거 풀면서 처음 써보게 되었다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
#include <vector>
#include <iostream>
using namespace std;
vector<double> movingAverage(const vector<double>& A, int M){
vector<double> ret;
int N=A.size();
for(int i=M-1; i<A.size(); i++){
double sum=0;
for(int j=0; j<M; j++)
sum += A[i-j];
ret.push_back(sum/M);
}
return ret;
}
int main(void){
vector<double> MyScore={89,80,67,65,64,61,60,59,52,54,67};
vector<double> AvgScore=movingAverage(MyScore, 3);
for(int i=0; i<AvgScore.size(); i++){
cout<<AvgScore[i]<<endl;
}
}
|
그리고 다음장에서 이 코드의 단점을 지적한다. 7번 라인( for(int i=M-1; i<A.size(); i++){ ) 에서 코드가 N-M+1번, 9번 라인 ( for(int j=0; j<M; j++) )에서 코드가 M번 돌아가니 총 N*M-M^2+M번 반복문을 거치게 된다.
i-1번째 실행과 i번째 실행에서 sum의 차이는 가장 앞의 원소와 가장 끝의 원소의 차이이다. 이점을 이용해 좀 더 효율적으로 코드를 작성 할 수 있다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
#include <vector>
#include <iostream>
using namespace std;
vector<double> movingAvg(const vector<double>& A, int M){
vector<double> ret;
double sum=0;
for(int i=0; i<M; i++){
sum += A[i];
}
ret.push_back(sum);
for(int i=M; i<A.size(); i++){
ret.push_back((ret[i-M]+A[i]-A[i-M])/3);
}
return ret;
}
int main(void){
vector<double> MyScore={89,80,67,65,64,61,60,59,52,54,67};
vector<double> AvgScore=movingAvg(MyScore, 3);
for(int i=0; i<AvgScore.size(); i++){
cout<<AvgScore[i]<<endl;
}
}
|
이게 내가 짠 코드. 그리고 책에 나와 있는 모범 답안은
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#include <vector>
#include <iostream>
using namespace std;
vector<double> movingAvg(const vector<double>& A, int M){
vector<double> ret;
int N=A.size();
double partialSum = 0;
for(int i=0; i<M-1; i++)
partialSum += A[i];
for(int i=M-1; i<A.size(); i++){
partialSum += A[i];
ret.push_back(partialSum/M);
partialSum -= A[i-M+1];
}
return ret;
}
int main(void){
vector<double> MyScore={89,80,67,65,64,61,60,59,52,54,67};
vector<double> AvgScore=movingAvg(MyScore, 3);
for(int i=0; i<AvgScore.size(); i++){
cout<<AvgScore[i]<<endl;
}
}
|
난 ret의 첫번째 항을 만들고 나중에 조작했고, 모범 답안은 그냥 모두 생성할 수 있는 알고리즘을 만들었다. 안 좋은 코드와 좋은 코드의 예시라고 해도 좋을 정도로 차이난다. 그만큼 사소한 곳에서 고쳐야 할 부분이 보인다.
아무튼. 두 번째 코드는 반복문의 수행 횟수가 N번으로, 위의 코드와 효율성 면에서 큰 차이가 난다. 이런 알고리즘은 수행 시간이 N에 정비례하고, 입력의 크기에 따라 걸리는 시간을 그래프로 그려 보면 직선이 된다. 이를 선형 시간(linear time) 알고리즘이라고 부른다.