ASPP - 4.3.이동평균선

개요

• 이동평균선?
  • 몸무게, 가격, GDP 등 시간에 따라 이동하며 변화하는 값들에 대해
  • 그 중 현재를 기준으로 M개의 관찰 값의 평균을 구한다

중첩 반복

• M=3일 경우, M-1부터 시작하여 M만큼의 평균을 구하며 시간에 따라 이동한다

M-3	M-2	M-1	M	M+1	M+2	…	N
0	1	2
	1	2	3
		2	3	4
			3	4	5		N

/**
  * 이동 평균선 구하기
  * - 이동 평균이란? 시간에 따라 변화하는 값들의 평균
  * - M-이동 평균? 마지막 M개의 평균.
  * */
public double[] first(double[] A, int M) {
    int N = A.length;
    double[] answer = new double[N];

    /* A[i]까지의 이동 평균 구하기 */
    for (int i = M - 1; i < N; i++) {
        double partialSum = 0;
        /* 각 위치(i)에서 지난 M개의 평균 구하기. 현재 기준으로 M-1만큼 돌아간다. */
        for (int j = 0; j < M; j++) { // j는 현재(i)를 기준으로 인덱스를 상대적으로 줄여나가기 위한 변수다
            partialSum += A[i - j]; // 현재(=i)-0, 현재(i)-1, ..., 현재(i)-(M-1)
        }
        answer[i] = partialSum / M;
    }

    return answer;
}

선형 시간 알고리즘

• 위의 표를 다시 보면, 중복되는 값들이 있다. [1,2], [2,3], [3,4] 등은 계속 중복되는 숫자들이다. 이 중복을 해결할 수 있다면 굳이 중첩 반복문을 돌 필요가 없다.

M-3	M-2	M-1	M	M+1	M+2	…	N
0	1	2
	1	2	3
		2	3	4
			3	4	5		N

• M=3일 때, 마치 포인터를 이동시키듯이 연산을 통해 필요한 부분합의 범위를 이동시킨다
  • 1:
    • partialSum = (A[0] + A[1])
    • (partialSum + A[2]) / M
    • partialSum - A[0]
    • A[1] + A[2]이 남는다
  • 2:
    • partialSum = (A[1] + A[2])
    • (partialSum + A[3]) / M
    • partialSum - A[1]
    • A[2] + A[3]이 남는다

public double[] second(double[] A, int M) {
    int N = A.length;
    double[] answer = new double[N];
    double partialSum = 0;
    /* 미리 중복되는 M-2까지의 합을 구해 둔다 */
    for (int i = 0; i < M - 1; i++) { // M-1 인덱스가 현재(i)며, 현재는 아래 반복문에서 더한다
        partialSum += A[i]; // M=3? A[0], A[1]
    }

    for (int i = M - 1; i < N; i++) {
        partialSum += A[i]; // 현재를 더한다
        answer[i] = partialSum / M;
        partialSum -= A[i - (M - 1)]; // 다음을 위해 현재(i)의 이동 평균선 구하는 첫 시작 부분을 제거한다
    }

    return answer;
}

• 그러면 중첩 반복문을 쓰지 않고 연산만으로 선형시간 알고리즘 구현이 가능하다

생각

• 이동평균선의 개념을 생각했을 때는 중첩 반복문 방식으로 짜기 쉽다.
  • N개의 요소들이 있을 때 각 요소를 기준으로 마지막(이전) M개만큼의 평균을 구하는 것이기 때문이다.
  • M개만큼의 평균을 구한다고 생각했을 때 일반적으로 M개를 더해서 M으로 나눈다고 생각하기 쉽다.
  • 평균이란 단어를 너무 협소하게 생각하는 거 같다. M개를 다 더해서 M으로 나누는 것이 평균이지만, 매번 M개를 다 더하는 과정이 필수는 아니다. 어쨌든 다 더해진 M개를 M으로 나누는 것이 평균이다.
• 괜히 범위 지정을 잘못해서 계산이 잘못되지 않을까 우려 되기도 하지만, 이는 점화식을 만드는 능력이 부족해서 그런 거 같다. 가급적 점화식을 만들어서 알고리즘을 짜는 연습을 하자.