C언어 수열 만들기 - ceon-eo suyeol mandeulgi

세 번째로 다루어볼 문제는, '개미 수열의 출력' 입니다.

개미 수열의 정확한 명칭은 '읽고 말하기 수열' 입니다. 이 수열이 유명해지게 된 계기는 베르나르 베르베르의 소설 '개미'에서 소개되면서 유명해졌다고 합니다.

이 수열을 간단히 설명하면, 전 항에서 같은 숫자들이 연속으로 몇번 이어지는지를 나타낸 수열인데, 1항부터 6항까지는 다음과 같습니다.

1항 : 1
2항 : 11
3항 : 12
4항 : 1121
5항 : 122111
6항 : 112213

규칙을 좀 아시겠나요? 잘 보시면, 수열의 초항은 숫자 1입니다.
2항의 숫자 '11' 의 의미는 '이전 항에 1이 1개가 연속해서 등장했다' 라는 뜻입니다.
그렇다면 3항의 숫자 '12'의 의미는 '이전 항에 1이 2개가 연속해서 등장했다' 라는 얘기겠죠.
4항의 숫자 '1121'은, '이전 항의 앞에서부터 시작해서, 1이 1개 연속해서 등장했고 이어서 2가 1개 연속적으로 등장했다' 라는 의미를 가진 숫자가 되겠습니다.
5항도 마찬가지입니다. '1이 2개, 2가 1개, 1이 1개로 차례대로 연속적으로 등장했다' 를 나타냅니다.

이제 규칙이 이해되셨나요? 개미 수열의 규칙대로라면 7항은 '12221131'이 될 겁니다.

이제 실제로 개미수열을 출력하는 C언어 코드를 짜봅시다.

숫자의 개수를 카운팅하기 쉽게 하고, 큰 숫자를 쉽게 표현할 수 있게 하기 위해서 배열을 사용합니다. 배열은 이전 항과, 이전 항으로 만들어 낼 새로운 항을 각각 표현할 2개의 배열을 사용합니다.
사실 알고리즘은 그렇게 어렵지 않습니다. 숫자가 바뀔때까지 동일한 숫자의 개수를 카운팅하고, 숫자가 바뀌면 카운트를 1로 만든 후 새로 카운트를 시작하면 되니까요.

아래는 개미 수열의 C언어 소스 코드입니다.

/* Ant array - made by MagmaTart*/ #include <stdio.h> int main(void) { int p_array[1000] = { 0, }; //이전 항 배열, 모두 0으로 초기화 int n_array[1000] = { 0, }; //다음 항 배열, 모두 0으로 초기화 int n; //몇 개의 수열을 출력할것인지 입력받는 변수 int prev_index; //이전 항 배열의 인덱스 int next_index; //다음 항 배열의 인덱스 int num; //현재 개수를 카운팅중인 숫자 저장 int count; //현재 카운팅중인 숫자의 개수 저장 scanf("%d", &n); for (int k = 1; k <= n; k++) { next_index = 0; //구현의 편의를 위함. 1번 항 '1' 은 그대로 출력한다. if (k == 1) { p_array[0] = 1; printf("1 : 1\n"); } else { prev_index = 0; while (p_array[prev_index] > 0) { count = 1; num = p_array[prev_index]; //같은 숫자의 개수를 센다 while (p_array[++prev_index] == num) count++; //다음 항 수열에 입력 n_array[next_index++] = num; n_array[next_index++] = count; } //수열의 다음 항 출력 printf("%d : ", k); for (int i = 0; i < next_index; i++) { printf("%d", n_array[i]); } printf("\n"); //수열 저장 배열 초기화 for (int i = 0; i < next_index; i++) { p_array[i] = n_array[i]; n_array[i] = 0; } } } }

정수 n을 입력하면, 개미 수열이 제 n항까지 출력됩니다.