학교에서 과제로
C언어로 쉽게 풀어 쓴 자료구조 172페이지 10번 문제를 풀게 되었다.
네이버 블로그에서 피보나치 수를 구현한 것과
음수의 피보나치 수를 구상하고 구현하는 부분에 대해
설명을 해보았다.
https://blog.naver.com/aprkal12/222771967511
블챌 2주차) [자료구조] 큐를 이용한 피보나치 수 구현
이번주는 저번달에 과제겸 시험공부겸 풀었던 문제를 정리해서 복습하려고한다. 큐를 이용한 피보나치 수 ...
blog.naver.com
여기에선 코드의 구현에 대해 좀 더 다뤄보려고한다.
먼저 전체 코드는 다음과 같다.
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// 큐를 이용한 피보나치 수
typedef struct que { // 큐노드 정의
int data;
struct que* link;
}que;
typedef struct queuepointer { // 큐를 가리킬 head와 rear포인터 정의
struct que* head, * rear;
}qp;
void init(qp* p); // head, rear초기화 해주는 init함수
void set(qp* p); // 피보나치 함수의 초기값 설정
bool is_empty(qp* p); // 큐가 비어있는지 검사
que* create(int data); // 새로운 노드 생성
void enque(qp* p, que* newn); // rear뒤에 새로운 노드 삽입
que* deque(qp* p); // head가 가리키는 노드 삭제
void fibo(qp* p, int n); // 피보나치 함수 구현
int main(void) {
qp mq; // 큐 포인터 구조체 선언
int n = 0; // 사용자로부터 어떤수의 피보나치수를 구할 건지 입력받음
printf("피보나치 수 입력 : ");
scanf("%d", &n); // 사용자로부터 수를 입력받아 n에 저장
init(&mq); // mq구조체 초기화
set(&mq); // 피보나치 초기값 f(0) = 0, f(1) = 1 설정
fibo(&mq, n); // 피보나치수 구현부
return 0;
}
void init(qp* p) { // head와 rear정의
p->head = NULL;
p->rear = NULL;
}
void set(qp* p) { // 초기값 f(0) = 0, f(1), f(-1) = 1 설정
enque(p, create(0));
enque(p, create(1));
}
bool is_empty(qp* p) { // 큐의 공백검사
return (p->head == NULL);
}
que* create(int data) { // 연산한 데이터를 매개변수로 새로운 노드 생성 후 리턴
que* nq = (que*)malloc(sizeof(que));
if (nq == NULL) { printf("큐노드 생성 실패\n"); return NULL; }
nq->data = data;
nq->link = NULL;
return nq;
}
void enque(qp* p, que* newn) { // rear뒤에 새로운 노드를 삽입한다.
if (is_empty(p)) { // 만약 큐가 공백이면
p->head = newn;
p->rear = newn; // head와 rear모두 새로운 노드를 가리키게한다.
}
else { // 큐가 공백이 아니면
p->rear->link = newn;
p->rear = newn; // rear뒤에 새로운 노드를 삽입하고, rear가 가리키는 값을 newn으로 변경
}
}
que* deque(qp* p) { // head가 가리키는 값을 삭제
que* popn = NULL; // 삭제할 노드를 가리킬 popn 선언
if (is_empty(p)) { // 큐가 공백이면
printf("삭제할 큐노드가 없습니다.\n");
return NULL; // 삭제할 큐가 없음
}
else { // 큐가 공백이 아니면
popn = p->head; // head가 가리키는 값을 popn가 가리키게 하고
p->head = p->head->link;// head를 head다음 노드를 가리키게 한 다음
return popn; // 기존의 head가 가리키는 값이었던 popn이 가리키는 값을 리턴한다.
}
}
void fibo(qp* p, int n) { // 피보나치 함수의 구현
int i = 0; // 카운팅용 정수
if (n == 0) { // f(0) = 0이므로 따로 연산없이 head가 가리키는 0출력
printf("fibo(%d) = %d\n", n, p->head->data);
}
else if (n > 0) { // 양수부분 피보나치
for (i = 2; i <= n; i++) { // f(1) = 1 이므로 반복문 수행없이 바로 출력하면 된다.
enque(p, create(deque(p)->data + p->rear->data));
} // 전전항(deque(p)->data) + 전항(p->rear->data)를 인수로 create함수를 호출하여 새로운 노드를 생성하고
// enque로 rear뒤에 삽입한다.
printf("fibo(%d) = %d\n", n, p->rear->data);
}
else { // 음수부분 피보나치
for (i = -2; i >= n; i--) { // 마찬가지로 f(-1) = 1이므로 반복문 수행x
enque(p, create(deque(p)->data + (-1 * (p->rear->data))));
}// 양수부분과 마찬가지로 전항, 전전항의 덧셈으로 새로운 노드를 생성하여 더한다.
// 하지만 음수부분에서의 점화식은 f(n-2) = f(n) - f(n-1) 이므로 p->rear->data에 -1를 곱해준다.
printf("fibo(%d) = %d\n", n, p->rear->data);
}
}
main함수를 보면
사용자로부터 피보나치 수를 구할 n을 입력받고,
init 함수를 이용해 큐를 가리킬 큐포인터를 초기화 해주고,
set 함수를 이용해 피보나치 수 초기값 f(0) = 0, f(1) = 1을 설정한다.
그리고 fibo함수를 이용해 주 연산이 이루어진다.
아래는 set함수 호출 후의 메모리 상태이다. ( 메모리 주소는 임의로 설정 )
head가 가리키는 부분이 삽입된지 가장 오래된 노드이고,
rear가 가리키는 부분이 최근에 삽입된 부분이다.
선입선출인 큐의 규칙에 따라
삭제연산시 head가 가리키는 값이 삭제되고,
삽입연산시 rear가 가리키는 값 뒤에 새로운 노드가 삽입된다.
주요 로직은 정말 피보나치 수의 정의처럼
f(n) = f(n-2) + f(n-1)으로 f(n)의 값을 구하고 f(n-2)는 삭제한다.
fibo함수에서 주로 큐의 삽입과 삭제를 수행하는 부분은 다음과 같이
enque(p, create(deque(p)->data + p->rear->data));이 부분이다.
여기서 enque, create, deque 는 전부 본인이 새로 정의한 함수인데
void enque(qp* p, que* newn) { // rear뒤에 새로운 노드를 삽입한다.
if (is_empty(p)) { // 만약 큐가 공백이면
p->head = newn;
p->rear = newn; // head와 rear모두 새로운 노드를 가리키게한다.
}
else { // 큐가 공백이 아니면
p->rear->link = newn;
p->rear = newn; // rear뒤에 새로운 노드를 삽입하고, rear가 가리키는 값을 newn으로 변경
}
}enque 함수는 매개변수로 큐를 가리키는 head와 rear포인터를 가리키는 qp*를 입력받고,
또 큐 노드를 가리키는 que*포인터를 받는다.
그래서 조건문을 통해 큐가 NULL 상태이면
head, rear가 모두 매개변수로 넘겨받은 새로운 노드를 가리키게 하고
큐가 공백이 아닐 경우엔 rear가 기존에 가리키던 노드 뒤에 새로운 노드를 연결하고,
rear가 방금 연결된 새로운 노드를 가리키게한다.
que* create(int data) { // 연산한 데이터를 매개변수로 새로운 노드 생성 후 리턴
que* nq = (que*)malloc(sizeof(que));
if (nq == NULL) { printf("큐노드 생성 실패\n"); return NULL; }
nq->data = data;
nq->link = NULL;
return nq;
}create는 노드의 데이터가 될 int data를 매개변수로 받고
malloc를 이용해 새로운 메모리를 생성하여
해당 노드의 데이터와 링크를 초기화 해준 후 그 포인터를 반환한다.
que* deque(qp* p) { // head가 가리키는 값을 삭제
que* popn = NULL; // 삭제할 노드를 가리킬 popn 선언
if (is_empty(p)) { // 큐가 공백이면
printf("삭제할 큐노드가 없습니다.\n");
return NULL; // 삭제할 큐가 없음
}
else { // 큐가 공백이 아니면
popn = p->head; // head가 가리키는 값을 popn가 가리키게 하고
p->head = p->head->link;// head를 head다음 노드를 가리키게 한 다음
return popn; // 기존의 head가 가리키는 값이었던 popn이 가리키는 값을 리턴한다.
}
}deque는 큐의 데이터 연산을 위해 qp*를 매개변수로 받는다.
큐가 공백일 경우 NULL을 리턴하고,
공백이 아닐경우
임의의 큐포인터 popn에 기존의 head가 가리키고 있던 삭제대상 노드를 가리키고,
head가 가리키고 있던 노드를 head->link로 변경해준다.
그런다음 기존의 head가 가리키던 값을 가리키고있는 popn을 리턴해준다.
enque(p, create(deque(p)->data + p->rear->data));각각의 함수들을 이해했다면 위의 코드를 다시 보자.
삭제한 노드의 값(f(n-2))과, rear가 가리키고 있던 값(f(n-1))을 더한 값을
인수로 create함수를 호출하고
그 값으로 생성된 노드를 큐에 삽입한다.
이해하기 쉽게 그림으로 표현하면 다음과 같다.
이 루틴을 입력한 n의 값을 얻을 때 까지 반복하게 된다.
음수도 마찬가지인데,
네이버 블로그에서 설명했듯이,
음수일 경우엔 f(n-2) = f(n) - f(n-1)으로 계산한다.
그래서 음수인 경우엔 뒤의 항에 -1을 곱해준다.
해당 로직을 바탕으로 추가적으로 첨가를 해서 백준 1788번 문제도 해결했다.
큐라는 자료구조를 연습하기에 좋은 예제인 것 같다.