이동 평균 구하기

알고리즘 문제 해결 전략 책을 알고리즘 스터디용 책으로 정하고 읽기 시작한지 꽤 지났지만, 이제야 첫 포스팅을 진행한다. 나의 게으름에 다시 한 번 감탄?하며 비교적 초반부에 나오는 이동 평균에 대해 정리해보자.

책에서는 C++를 이용해서 코딩하지만, 앞으로 스터디를 위해 사용하기로 한 언어가 JAVA이기 때문에 코드는 JAVA로 작성되었으며, 책의 내용을 나름대로 재구성하여 작성하였다.

먼저, 이동 평균에 대해서 알아보자.

평균이라 함은 총합을 갯 수만큼 나눠주면 된다는 아주 단순한? 내용이다. 사실 이동 평균도 우리가 아는 그 평균이라는 것에 크게 벗어나지 않는다. 다만, 여러 값 들의 시간에 따른 변화(흐름)라는 것에 중점을 두었다고 생각하면 되겠다.

책의 내용을 빌리자면, “시간에 따라 관찰된 숫자들이 주어질 때 M-이동 평균은 마지막 M개의 관찰 값의 평균으로 정의된다. 따라서 새 관찰 값이 나오면 M-이동 평균은 새 관찰 값을 포함하도록 바뀌게된다.” 역시 글로만 봐서는 영 감이 잡히지 않는다.

예를 들어보자.

성재는 술을 좋아한다.(이거 진짜다..) 때문에, 소주를 자주 마신다. 하지만, 가끔은 왜인지 모르게 맥주가 땡길 때가 있다. 소맥도 좋다.

성재는 문득, 자신의 캔맥 소비량에 대한 이동 평균이 궁금해졌다. 때문에, 한 달 동안의 캔맥 소비량에 대한 이동 평균을 구해보기로 했다. 우선 성재의 음주 그래프를 살펴보자. 그렇다. 평일 주말 가리지 않고 맥주를 자주 마셔대는 것을 확인할 수 있다. 물론, 4캔 이상 먹진 않고 안 먹는 날도 있다. (간이 열일 하고 있을 것을 짐작할 수 있다.)

그렇다면 ,여기서 N일 (30일) 동안의 측정치가 주어질 때 M일 (5일 간격) 간의 이동 평균을 계산해보자.

우선, 각 위치에서 지난 M개 측정치의 합을 구하고, 이를 다시 M으로 나누면 된다. (여기서, 기존의 구한 평균의 첫 번째 값을 제외하고 새로운 값을 포함하여 평균을 구하는게 포인트!)

30일간 음주 이동 평균

이동 평균 코드를 살펴보자.

//A배열의 값을 받아와서, M구간 당 이동평균을 구한다.
List<Double>getMovingAverage(int[]A, int M){
  //이동 평균 값을 담을 리스트 친구 선언.
   List<Double>result = new ArrayList<Double>();
   //평균을 구할 값들의 총 수.
   int N = A.length;
   //이동 평균을 구하기 위해 각 구간당 합계를 담을 친구 선언.
   double partialSum = 0;

   //0번째 인덱스(값)부터 M-1인덱스(값)까지의 값을 합한다.
   for(int i = 0; i< M-1; ++i){
     //0~3번 째의 값들에 합을 구해놓는다.
      partialSum += A[i];
   }
   //4번째 인덱스(값)부터 시작해서 전체 배열(값)의 크기까지 반복한다.
   for(int i = M-1; i < N; ++i){
     //각 구간당 합계 구하기.
      partialSum += A[i];
      //합계를 M으로 나눠서(평균) 결과 값에 순서대로 할당.
      result.add(partialSum/M);
      //합계에서 기존의 첫 번째 빼주기.
      partialSum -= A[i-M+1];
   }
   //결과 값 반환.
   return result;
}

위 코드와 그림을 보면 알 수 있듯이, 평균 값을 구하는 인덱스의 조절을 통해 값을 구해낼 수 있다. 위 그림은 이동 평균의 계산을 그림으로 도식화한 것이다.

위 이동 평균 그래프를 보면, 임의의 값을 선정해서 랜덤으로 값을 주었기 때문에 중구난방의 값으로 나타나지만, 만약 실제 데이터를 가지고 그래프를 구했다면, 실제 성재의 캔맥 소비량 그래프를 보고 성재가 요새 힘든지 안 힘든지, 우울한지 안 우울한지 판단할 수 있는 중요한 지표로 활용? 될 수 있다.

조금 번외이지만, 오늘 점심 메뉴로 뭘 먹을지 골라주는 간단한 프로그램 코드도 살펴보자.

//점심 메뉴 정하기 랜덤 값을 돌릴 size를 받아온다.
String getMenu(int size) {
      //점심 메뉴 배열 선언
      String[]menu = {"라면", "순대국", "역전", "식당", "중식", "부찌", "닭볶음탕", "칼국수"};
      //각각의 메뉴의 카운트를 계산할 배열 선언
      int[]count = new int[menu.length];
      //size만큼 반복
      for(int i = 0; i < size; ++i) {
         ++count[new Random().nextInt(8)];//0~7까지의 랜덤 숫자를 받아와서 카운트의 각 인덱스 값을 더해준다.
      }
      int major = 0;//가장 많이 나온 카운트를 구하기 위한 친구 선언.
      //카운트 배열의 크기만큼 반복
      for(int i = 0; i < count.length; ++i) {
         //가장 많이 나온 인덱스를 구하기 위한 조건문.
         if(count[i] > count[major]) {
            major = i; //최대 값이 변경되었을 경우, 인덱스 변경
         }
      }
      return menu[major]; //제일 많이 나온 인덱스의 값을 반환.
 }

위 알고리즘은 선형 시간(linear time)의 수행 시간을 갖는 알고리즘이다. 주어진 입력 값에 대해 최소한 한 번씩 계산을 수행해야 하기 때문이다.

이동 평균을 잘 활용하면 여자친구의 다이어트 수치나 게으름쟁이의 아침 기상 시간 평균 등의 여러 수치 값에 대한 시계열 분석이 가능할 것으로 보이므로 잘 숙지해 두는 걸로~

• 오타나 잘못된 부분을 지적해주시면 감사히 생각하고 수정토록 하겠습니다 :)
• 참고문헌
  구종만, 알고리즘 문제 해결 전략. pp.94~pp.97.