책을보다가 생각지도 못한 방법이 보여서 요약 글을씁니다.
계속 고민했다면 같은 방식으로 풀었을듯
책 제목은 : 알고리즘 문제 해결 전략 1
다이어트 현황 파악
시간에 따라 관찰된 숫자들이 주어질때 M-이동 평균은 마지막 M개의 관찰 값의 평균으로 정의됩니다.
따라서 새로운 관찰값이 나오면 M-이동평균은 새 관찰 값을 포함하도록 바꿉니다.
a = 50.3, 50.6, 50.4, 50, 49.5, 49.3, 50.3, 50.6, 50.4, 50, 49.5, 49.3
m = 3
제 1년간 1달간격 가상의 몸무게 기록입니다.
여기서 3달간격의 평균을 구해봅시다.
a = 몸무게 리스트
m = 평균 기간
a개의 측정치가 주어질때 m달간의 이동편균을 계산하는 프로그램을 어떻케 짜야 할까요 ?
각 위치에서 지난 m개 측정치의 합을 구하고 이를 m으로 나누면 됩니다.
이때 이 코드는 두개의 for문에 의해 지배됩니다.
public List<Double> movingAverage1(List<Double> a, int m){
List<Double> ret = new ArrayList <>();
int n = a.size();
int cnt = 0;
for(int i=m-1;i<n;i++){
double sum = 0d;
for(int j=0;j<m;j++){
sum += a.get(i-j);
cnt++;
}
ret.add(sum/m);
}
System.out.println(cnt); //30
return ret;
}j를 사용하는 반복문은 항상 m번 실행되고 i를 사용하는 반복문은 a-m+1 번 실행되니
전체 반복문은 m x (n-m+1) 번 반복됩니다.
a = 12 이고 m = 3 이니 반복횟수는 당연히 30번입니다.
하지만 이건 선형시간 알고리즘이 아닙니다.
O(n) 을 충족하지못합니다.
또 다른 방법으로는
다시 생각해보면
측정치가 m개는 되어야 이동 평균을 계산할 수 있으니, 태어난 이후 m-1 일부터 이동평균을 계산 할 수 있습니다.
이때 m-1 일의 이동평균과 m일의 이동 평균에 포함되는 숫자들은
0일과 m일의 몸무게를 제외하면 전부 겹친다는것을 알 수 있습니다.
그러면 측정한 몸무게의 합을 일일히 구할것없이 m-1 일에 구했던 몸무게의 합에서 0일째에 측정한 몸무게를 빼고
m일째에 측정한 몸무게를 더하면 어떨까요 ?
이 아이디어를 구현하면 아래코드를 구할수 있습니다.
public List<Double> movingAverage2(List<Double> a, int m){
List<Double> ret = new ArrayList <>();
int n = a.size();
int cnt = 0;
double sum = 0d;
for(int i=0;i<m-1;i++){
sum+=a.get(i);
cnt++;
}
for(int i=m-1;i<n;i++){
sum+=a.get(i);
ret.add(sum/m);
sum-=a.get(i-m+1);
cnt++;
}
System.out.println(cnt); //12
return ret;
}
하나로 묶여서 반복하던 두개의 반복문을 두개로 분리했습니다.
이 알고리즘의 반복문 횟수는
m-1(m-1)+(a-m+1) = a.size() 가 됩니다.
수행시간은 입력값에 정비례하게되었습니다.
입력의 크기에 대비해 걸리는 시간을 그래프로 그려보면 정확히 직선이 유지됩니다.
때문에 이런 알고리즘을 선형시간 알고리즘이라고 부릅니다.
선형시간에 실행되는 알고리즘은 대개 우리가 찾을 수 있는 알고리즘 중 가장 좋은 알고리즘입니다.
