1. 과제 안내문
이번 과제는 목걸이 문제를 프로그래밍 한다. 목걸이 문제는 목걸이에서 스킵/삭제를 반복하여 최종적으로 남는 구슬을 찾는 문제이다. 목걸이는 1부터 n까지 번호가 부여된 구슬들로 구성되고, 1번부터 스킵과 삭제를 반복하여 마지막까지 남은 구슬의 번호를 찾는다. 다시 말해 1번 구슬은 건너뛰고, 2번 구슬은 삭제되고, 3번 구슬은 건너뛰고, 4번 구슬은 삭제되는 방식으로 구슬이 하나만 남을 때까지 반복된다. 이렇게 반복하여 마지막까지 남은 구슬의 번호를 찾는다. 목걸이 문제를 해결하는 방식은 2 가지 해결책이 있다. 첫째로 1부터 n까지 데이터를 가지는 노드들을 원형 연결 리스트로 만든 목걸이에서 1부터 시작하여 스킵과 삭제를 반복하는 방식으로 시물레이션에 의하여 답을 찾는다. 둘째로 일반규칙을 찾아 순환함수로 답을 찾는다.
Simulation(SkipErase1)
목걸이는 자연스럽게 헤드 노드가 없는 원형 연결 리스트로 표현할 수 있다. 다시 말해 1부터 n 데이터를 가지는 노드들로 원형 연결 리스트를 만든 후에, 1번 데이터를 가지는 노드부터 스킵과 삭제를 하나의 노드가 남을 때까지 계속하여 순환적으로 반복한다.
순환함수(SkipErase2)
일반규칙은 순환함수 수업시간의 강의자료를 참조하면 다음의 일반규칙을 얻을 수 있다.
처음 과제 안내문을 받았을 때 솔직히 이해도 되지 않았다...... 뭘 건너뛰고 뭘 건너뛰는지.... ㅠㅠ 그래서 예시 실행 결과와 같이 비교하면서 문제 해석을 진행하였다.
2. 시행 결과 예시
? 5
삭제 순서: 2 4 1 5
Simulation: 3
Recursion: 3
? 10
삭제 순서: 2 4 6 8 10 3 7 1 9
Simulation: 5
Recursion: 5
? 15
삭제 순서: 2 4 6 8 10 12 14 1 5 9 13 3 11 7
Simulation: 15
Recursion: 15
? 20
삭제 순서: 2 4 6 8 10 12 14 16 18 20 3 7 11 15 19 5 13 1 17
Simulation: 9
Recursion: 9
? 25
삭제 순서: 2 4 6 8 10 12 14 16 18 20 22 24 1 5 9 13 17 21 25 7 15 23 11 3
Simulation: 19
Recursion: 19
? 30
삭제 순서: 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 3 7 11 15 19 23 27 1 9 17 25 5 21 13
Simulation: 29
Recursion: 29
? -1
Bye, ...
숫자들이 삭제되는 순서와 안내문으로 미루어 봤을 때 이번 문제는 시작 노드를 기준으로 스킵과 삭제를 반복하여 마지막 까지 남는 노드를 출력하는 문제라는 것을 알게 되었다. 예를 들어 n = 5라면 다음과 같은 1 ~ 5까지의 원소를 각각 가지는 원형큐가 생성된다.
시작은 1을 가리키고 있으므로 다음 수인 2가 삭제된다.
그렇게 되면 1-> 3-> 4-> 5-> 1 의 형태은 원형 큐가 되며 3을 건너뛰고 4가 삭게, 5를 건너뛰고 1을 삭제 이런식으로 동작을 반복하면 결국 3이 남게 되는데, 최종적으로 남아있는 숫자인 3이 답인 것이다.
여기까지는 좋았으나...... 우리 교수님은 순환함수를 매우 좋아하신다 ㅠㅠ 그래서 반복문으로 결과를 얻는 함수 하나, 순환함수로도 결과를 얻는 함수 하나 이렇게 두개의 함수를 짜야한다......
3. 코드 제작
가장먼저 제작한 코드는 n을 입력받고 1 ~ n을 원소로 가지는 원형큐를 만드는 함수이다. 함수 이름은 Necklase이다.(교수님이 그렇게 하라고 하심 ㅎ)
- 라이브러리, 구조체 정의
#include <stdio.h>
#define N 40
#pragma warning(disable: 4996)
typedef struct node {
int nData;
struct node *link;
} Node, *NodePtr;
사실 C++의 Class를 사용하면 더욱 편리하지만...... 과제의 형식에 맞게 제출해야 하기 떄문에 구조체로 Node를 정의하고 프로그램 내에서 호출하기 편하게 포인터를 사용하였다.
- Necklase 함수 정의
NodePtr Necklase(int n)
{
NodePtr pList = new Node;
NodePtr ptr;
pList->nData = 1;
ptr = pList;
for (int i = 2; i < n + 1; i++) {
NodePtr buff = new Node;
buff->nData = i;
ptr->link = buff;
ptr = buff;
}
ptr->link = pList;
return pList;
}
n의 숫자를 입력받고 반복문으로 수를 Node에 넣어주는 코드이다. 아무리 원형 큐 이지만 결국 마지막 값이 첫 노드를 가리켜야 하기 때문에 첫 노를를 가리키는 포인터인 pList를 정의하였다. (혹시 다른 방법 아시는 분은 알려주세요 ㅠㅠ) 그리고 마지막으로 첫 노드를 가리키는 pList의 값을 반환하는 함수이다.
-SkipEraser1 함수 작성
일단 SkipEraser1함수에서는 값만을 출력하면 안된다. 예시 실행 결과를 보면 알겠지만 삭제되는 순서까지 출력해야 한다. 간단한 순서도를 작성해보자면,
- 한 노드 스킵
- 스킵된 노드의 link와 전 노드의 link연결
- 노드 스킵 후 가리키는 값 출력
- 출력 후 해당 노드 삭제
물론 삭제되는 노드를 가리키는 포인터가 하나 있어야 한다는 생각은 자연스럽게 든다. 굳이 따지자면 삭제와 추가 알고리즘은 원형 리스트와 일단 리스트(끝이 NULL을 가리키는 리스트)는 제어문에서 사용하는 문법이 다른것이지 다른 일반적인 알고리즘은 같다고 생각한다. 쨎든 다음은 내가 작성한 삭제 순서를 출력하고 최종적으로 남아있는 값을 반환하는 SkipEraser1함수이다.
int SkipEraser1(int n)
{
NodePtr Necklase(int n);
NodePtr nList = Necklase(n);
NodePtr del;
printf("%10s:", "삭제 순서");
while (nList != nList->link) {
del = nList->link;
nList = nList->link = del->link;
printf(" %d", del->nData);
delete del;
}
return nList->nData;
}
출력할 때 10자리를 왜 잡는지 궁금해 하시는 분들이 계시겠지만...... 우리 교수님이 깔끔한 출력을 좋아하셔서 그렇게 한거지 딱히 의미는 없다.
-SkipEraser2 함수 작성
굳이 따지자면 이 함수가 가장 어려울 거라고 생각했지만 3분안에 푼 함수이다. 필자의 머리가 너무 좋아서 중단조건과 반환 값을 구한것이었으면 좋겠지만 그냥 답이 나와 있었다. 다음은 과제 안내문 중 일부이다.
일반규칙은 순환함수 수업시간의 강의자료를 참조하면 다음의 일반규칙을 얻을 수 있다.
나는 그냥 이걸 코드로 그대로 만들기만 하면됐다 ㅎㅎ 문제는 우리 교수님이 짧은 코드를 매우 중요하게 생각하신다...... 처음 작성한 코드는 아래와 같다.
int SkipEraser2(int n)
{
if (n == 1) return n;
else if (n % 2 == 1) {
return (2 * SkipEraser2(n / 2) + 1);
}
else {
return (2 * SkipEraser2(n / 2) - 1);
}
}
장담하지만 이런 코드로 과제를 제출했다면 분명히 우리 교수님은 나를 혼내셨을거다......ㅠ 위의 코드는 정말 직관적으로 써내려간 코드이고 이를 조금 간결하게 줄였더니 아래와 같은 코드가 완성되었다.
int SkipEraser2(int n)
{
if (n == 1) return n;
else return (n % 2) ? 2 * SkipEraser2(n / 2) + 1 : 2 * SkipEraser2(n / 2) - 1;
}
살다살다 3항 연산자를 쓸줄이야...... 그래도 코드는 간결하게 나왔으니 만족한다 ^^
-main() 함수와 전체코드
다음은 최종적으로 작성된 코드이다.
#include <stdio.h>
#define N 40
#pragma warning(disable: 4996)
typedef struct node {
int nData;
struct node *link;
} Node, *NodePtr;
void main()
{
while (1) {
printf("? ");
int n;
scanf("%d", &n);
if (n <= 0 || n > N)
break;
int SkipEraser1(int n);
printf("\n%10s: %d\n", "Simulation",SkipEraser1(n));
int SkipEraser2(int n);
printf("%10s: %d\n\n", "Recursion",SkipEraser2(n));
}
printf("\nBye, ...\n\n");
}
int SkipEraser1(int n)
{
NodePtr Necklase(int n);
NodePtr nList = Necklase(n);
NodePtr del;
printf("%10s:", "삭제 순서");
while (nList != nList->link) {
del = nList->link;
nList = nList->link = del->link;
printf(" %d", del->nData);
delete del;
}
return nList->nData;
}
NodePtr Necklase(int n)
{
NodePtr pList = new Node;
NodePtr ptr;
pList->nData = 1;
ptr = pList;
for (int i = 2; i < n + 1; i++) {
NodePtr buff = new Node;
buff->nData = i;
ptr->link = buff;
ptr = buff;
}
ptr->link = pList;
return pList;
}
int SkipEraser2(int n)
{
if (n == 1) return n;
else return (n % 2) ? 2 * SkipEraser2(n / 2) + 1 : 2 * SkipEraser2(n / 2) - 1;
}나름 줄인다고 줄이면서 작성한 코드였지만 ㅎ...... 혹시 더 줄일 방법을 아시는 분은 언제든지 알려주세요 ㅠㅠ
- 실행결과
다음은 실행 결과이다.
4. 결어
코드를 이렇게 한번 더 정리하니 왜 프로그래머를 공부하시는 분들이 블로그를 운영하는지 알게 되었다. 정리가 잘돼 한 번더 공부하는 기분이었다. 고백하자면 사실 이 블로그를 작성하면서 코드를 3줄정도 더 줄였다 ㅎㅎ. 제발 이 블로그만큼은 작심삼일이 되지 않았으면 좋겠다 ㅠㅠ
'대학교 과제 > 자료구조 [ 2 - 1 ]' 카테고리의 다른 글
| [자료구조 과제] - 12주차 수식트리 (후위표기식) (0) | 2020.05.29 |
|---|---|
| [자료구조 과제] - 11주차 완전 이진 트리 (0) | 2020.05.21 |
| 자료구조 10주차 과제 - 이중 원형 연결리스트 (0) | 2020.05.12 |
