학교에서 문제풀이를 하다가
'개미수열' 이 나왔습니다.
유명학 소설작가 베르나르베르베르의 '개미' 라는 소설에서 나온 수열인데요
한번 규칙을 맞춰볼까요
1
1 1
1 2
1 1 2 1
1 2 2 1 1 1
1 1 2 2 1 3
1 2 2 2 1 1 3 1
1 1 2 3 1 2 3 1 1 1
...
...
이렇게해서 무한대로 증가를 합니다
규칙이 뭔지 5분동안만 생각 해보시는게 도움이 될 것 같습니다.
저도 프로그래밍을 잘 알진 못하지만 생각하는 힘을 기르게 되더라고요 (저는뉴비입니다 뉴비)
제가 개미수열을 풀지를 못해서 3일정도를 이 문제만 가지고 고민했습니다.
감이 잡힐듯하면서도 잘 안풀리더라구요
그래서 솔직히 구글링하면 다나오는데 답을 볼까 했지만 자존심이 허락치 않았습니다
저 혼자힘으로 해보고 싶은 욕심도 생기고요
[ 개미수열 풀이 ]
개미수열의 규칙은 이렇습니다
처음에 1이라는 숫자가나옵니다
1
-> 1이 한개입니다 그래서 다음줄엔 1이 1개라는 답을 씁니다.
1 1
-> 1이 두개입니다. 그래서 다음줄엔 1이 2개라는 답을 씁니다.
1 2
-> 1이 한개, 2가 한개 입니다. 다음줄엔 1이 1개 2가 1개 라는 답을 씁니다.
규칙 찾으셨나요?
이런식으로 개미수열이 진행되는데요
이걸 짜보면 되는겁니다 ㅎ
언어는 상관없습니다. 다만 저는 C++ 기준으로 하겠습니다.
저는 이문제를 이런식으로 접근했습니다.
첫번째 행이 문제,
두번째 행이 첫번째 문제에 대한 답
두번째 행이 문제,
세번째 행이 두번째 문제에 대한 답
알고리즘을 짜면서 사실 행도 중요하지만 저의 포인트는
' 답이 다시 문제가 된다 ' 입니다. 배열은 두개를 사용합니다 '문제'배열, '답'배열
#1 개미수열은 무한대로 진행하기때문에 자신이 출력하고싶은 행 까지만 출력하도록 해야 했습니다.
첫번째 while문 -> 입력한 수 만큼의 행 출력
#2 개미수열은 '문제'가 되는 배열에서 다음숫자가 이전숫자와 같다면, 개수를 증가시켜줍니다. 포인트는 배열이 카운트 된 만큼 다음 열이 땡겨진다는겁니다
두번째 while문 -> '문제'가 되는 배열의 끝을 알리는 역할
세번째 while문 -> 첫번째 요소와 두번째요소의 숫자가 같다면 count를 up시켜주는 역할
[0] [1] [2] [3] [4] [5] [6] [7] (문제가되는 배열)
1 1 2 1
[0] [1] [2] [3] [4] [5] [6] [7] (답이 되는 배열)
? ? ? ...
이러한 배열이 있다고 한다면
다음 배열은
1 2 2 1 1 1 이됩니다.
여기서 1이 두개입니다 그다음은 2 가나오는데
1 이 두개 -> count = 2;
'답' 배열 [0] 에 '문제'배열 [0] 의 숫자
'답' 배열 [1] 에 '문제' 배열 [0] 에대한 count
'답' 배열 [2] 에 '문제'배열 [2] 의 숫자
'답' 배열 [3] 에 '문제'배열 [2] 에 대한 count
'답' 배열 [4] 에 '문제'배열 [3] 의 숫자
'답' 배열 [5] 에 '문제'배열 [3] 에 대한 count
그럼 두개의 열씩 쪼개지게됩니다
[짝수] 에는 숫자
[홀수] 에는 count
int even = 0;
int odd = 1;
로 선언과 초기화를 했습니다.
그리고 '문제'배열에 대한 답배열을 초기화할때
even += 2;
odd += 2;
를 하여 순서대로 들어가게 하였습니다.
물론 0은 짝수가아니지만 지금은 그렇게 보는게 편할것같습니다.
배열을 두칸 씩 끊어서 본 이유는
int jump; 라는 변수를 하나 선언해서
jump += count; 를해준 뒤에
'문제'배열의 읽는 상태가 변경될 때마다
변경된 시점부터 다시 읽게 했습니다.
긴 설명이었습니다.
코드를 보겠습니다.
#include <iostream>
int main() {
int array[25] = {0,}; // '문제'가되는 배열 끊기지않는 선에서 적당히 length를 정함, 그리고 0으로 초기화
int newArray[25] = {0,}; // '답' 이 되는 배열
int inputNum; // 사용자 입력값, (행)
int count; // 요소의 개수
int jump; // 변화되는시점부터 읽기위한 변수
int i; // for
int even, odd; // even은 짝수, odd는 홀수
int index; // 배열의 index값
int line = 1;
array[0] = 1; // 개미수열의 처음은 무조건 1부터 시작하기에 고정시킴
std::cin >> inputNum;
printf("%4d", array[0]);
std::cout << std::endl;
while(line < inputNum){ // 입력한 값만큼 행을 출력
jump = 0;
even = 0;
odd = 1; // 행을 하나 출력하면 탐색에 필요한 변수들을 초기화를 해줌
while(array[jump] != 0){ // 탐색하려는 배열의 끝이 0이면 while문을 벗어남
count = 1; // 기본개수는 1개
index = 0;
while(array[index + jump] == array[index + jump + 1] && array[index + jump + 1] != 0){ // index + jump를 하는 이유는 변경되는 시점부터 읽어야하기 때문
count++;
index++;
}
if(array[jump] != array[jump + 1]){ //변경되는 시점의 요소와 , 변경시점요소 + 1의 요소가 같지 않다면, ex) 1 2 1 3 이라면 개수는 전부 1개
count = 1;
}
newArray[even] = array[jump]; //'답' 배열에 차곡차곡 쌓음,
newArray[odd] = count;
jump += count;
even += 2;
odd += 2;
}
for(i = 0; i < sizeof(array) / sizeof(int) - 1; i++){ // i = 0부터 array의 길이 - 1 까지
array[i] = newArray[i]; // '답' 이 다시 '문제' 가 되기 때문에 바꿔준다.
}
for(i = 0; i < sizeof(array) / sizeof(int) - 1; i++){
if(array[i] == 0) // array[i] == 0 이면 출력을 하지않음
break;
printf("%4d", array[i]);
}
std::cout << std::endl;
line++;
}
return 0;
}
<실행화면>
다른 블로그에 더 좋은 코드들이 많겠지만,
저만의 풀이법이었습니다.
[ 주의할점 ]
'답'이 되는 배열을 다시 '문제' 배열에 복사를 할 때에
array = newArray;
이런식으로 하게되면,
배열은 주솟값이므로
array의 주소 0x0000
newArray의 주소 0x0099
다시
array = newArray;의 과정을 보도록합시다.
<과정>
array = newArray;
array = 0x0099;
array = 0x0099;
newArray = 0x0099;
0x0000 는 array, newArray 어떤배열도 가리켜지지않아 사라지게됩니다.
또한 array, newArray는 같은 배열을 가리키게 되는것이죠
배열을 대입할땐 각 요소별로 각각 대입해줘야합니다
for(int i = 0; i < sizeof(array) / sizeof(int) - 1; i++){
array[i] = newArray[i];
}
이런식으로 요소별로 접근을 해야합니다.
알게 된점 : 배열은 요소별로 대입하자.
지적은 감사히 받겠습니다!
'알고리즘' 카테고리의 다른 글
| [알고리즘] 버블정렬 (Bubble Sort) (0) | 2018.01.09 |
|---|