C++로 데이터 세트의 최빈값(Mode) 찾기: 알고리즘과 예제 코드

최빈값(Mode)이란 자료 집합에서 가장 자주 나타나는 값을 뜻합니다. 이 글에서는 C++를 이용해 데이터 세트에서 최빈값을 찾는 프로그램을 소개합니다. 핵심 아이디어는 연결 리스트(linked list)에 각 숫자를 오름차순으로 삽입하되, 중복된 값이 들어올 경우 새로운 노드를 추가하지 않고 등장 횟수만 증가시키는 것입니다. 이렇게 하면 정렬과 빈도 계산이 동시에 이루어집니다.

알고리즘

시작
    집합(set)에 데이터를 삽입하기 위한 insertinset() 함수를 정의한다.
    새 노드(newnode)와 임시 노드 t를 생성한다.
    newnode를 사용해 연결 리스트에 노드를 삽입한다.
    만약 head가 NULL이라면
        새 노드를 head로 지정하고 카운트(cnt)를 1 증가시킨다.
    삽입 과정에서 삽입 정렬(insertion sort)을 수행하여 데이터를 정렬한다.
    만약 newnode->data가 집합에 이미 존재하는 요소와 같다면
        해당 노드의 카운트만 증가시킨다.
종료

예제 코드

#include <iostream>
using namespace std;
struct set // 변수 선언을 위해 정의한 set 구조체
{
   int data;
   int cnt;
   set *n;
};
set* insertinset(set *head, int n) {
   set *newnode = new set; // set 구조체의 변수를 사용하기 위한 노드 생성
   set *t = new set;
   newnode->data = n;
   newnode->cnt = 0;
   newnode->n = NULL;
   if(head == NULL) { // head가 비어 있는 경우
      head = newnode;
      head->cnt++;
      return head;
   } else {
      t = head;
      if(newnode->data < head->data) { // 새 값이 head보다 작으면 맨 앞에 삽입
         newnode->n = head;
         head = newnode;
         newnode->cnt++;
         return head;
      } else if(newnode->data == head->data) { // head와 같은 값이면 카운트만 증가
         head->cnt++;
         return head;
      }
      while(t->n != NULL) { // 적절한 위치를 찾아 삽입 정렬 수행
         if(newnode->data == (t->n)->data) { // 중복 값이면 카운트만 증가
            (t->n)->cnt++;
            return head;
         }
         if(newnode->data < (t->n)->data)
            break;
         t = t->n;
      }
      newnode->n = t->n;
      t->n = newnode;
      newnode->cnt++;
      return head;
   }
}
int main() {
   int n, i, num, max = 0, c;
   set *head = new set;
   head = NULL;
   cout<<"\nEnter the number of data element to be sorted: ";
   cin>>n;
   for(i = 0; i < n; i++) {
      cout<<"Enter element "<<i+1<<": ";
      cin>>num;
      head = insertinset(head, num); // 함수 호출
   }
   cout<<"\nSorted Distinct Data ";
   while(head != NULL) // head가 NULL이 아닐 때까지 반복
   {
      if(max < head->cnt) { // 최대 등장 횟수와 해당 값을 갱신
         c = head->data;
         max = head->cnt;
      }
      cout<<"->"<<head->data<<"("<<head->cnt<<")"; // 각 값의 등장 횟수 출력
      head = head->n;
   }
   cout<<"\nThe Mode of given data set is "<<c<<" and occurred "<<max<<" times.";
   return 0;
}

실행 결과

Enter the number of data element to be sorted: 10
Enter element 1: 1
Enter element 2: 2
Enter element 3: 0
Enter element 4: 2
Enter element 5: 3
Enter element 6: 7
Enter element 7: 6
Enter element 8: 2
Enter element 9: 1
Enter element 10: 1
Sorted Distinct Data ->0(1)->1(3)->2(3)->3(1)->6(1)->7(1)
The Mode of given data set is 1 and occurred 3 times.

결과 해석

프로그램은 입력받은 데이터를 정렬된 고유 값 목록으로 변환하고, 각 값 옆의 괄호 안에 등장 횟수를 함께 출력합니다. 예를 들어 ->1(3)은 값 1이 세 번 나타났다는 의미입니다. 이 예제에서는 1과 2가 모두 세 번씩 나타나지만, 코드는 오름차순 탐색 중 먼저 조건을 만족하는 1을 최빈값으로 선택합니다. 따라서 주어진 데이터 세트의 최빈값은 1이며, 총 3회 등장했습니다.