2007년 1학기 첫번째 리포트... 10진수를 2진수로 변환(STACK)

 어제 알고리즘 수업을 들어갔는데 첫 수업부터 리포트가 나왔다(수업 안 할 줄 알았건만...). 10진수를 입력 받아서 2진수로 변환해서 출력하라는 리포트였는데, 교수님은 stack을 썼으면 좋겠다는 얘기를 하셨다. 최초에 머리속에는 배열에 순차적으로 집어넣어서 역순으로 빼내면 되겠다는 생각을 했었는데, 친구녀석이 배열로 하는 것을 보고 있으니 링크드 리스트를 써서 짜보고 싶어졌다.
 링크드 리스트로 짜서 들고가니 교수님은 이정도 프로그램에서 링크드 리스트 쓰면 얻는 것보다 잃는게 많다고, 낭비 아니냐고 하셨다. 프로그램 짤 때는 쉬운 것부터 생각 나는 것이 당연하다고, 쉬운 것 부터 짜고 그 다음을 생각하는 게 좋다고 하셨다. 뭐, 이건 개인적인 얘기니까...

 최초에 짤 때는 참고 할 책이 주변에 없어서 naver를 검색해서 나오는 stack 소스를 수정해서 제출했는데, stack을 구현하는데 top과 bottom을 쓰는 구조라 bottom의 경우, 쓰이지 않는 낭비되는 구조였다. 이게 석연치 않아서 어떻게 바꾸어서 제출하려고 했는데, 당일 오후 6시 제출이라는 시간에 쫓겨서 이대로 제출했다. 하지만 역시 마음에 걸려서 오늘 도서관에 가서 책을 빌려서 새롭게 짜보았다. 아~ 언제나 느끼는 거지만 프로그램을 짠다는 건 어렵다. 이렇게 간단한 프로그램인데도...

// 최초 버전
#include <stdio.h>
#include <stdlib.h>

// 스택 구조체 선언
typedef struct stack
{
int val; // 값
struct stack *next; // 다음 노드
}node;

node *top; // 스택의 최상위
node *bottom; // 스택의 바닥

node* push(); // push 함수 선언
int pop(); // pop 함수 선언

int main()
{
top = (node *)malloc(sizeof(node)); // top 구조체 정의
bottom = (node *)malloc(sizeof(node)); // bottom 구저체 정의
top->next = bottom; // 최초의 top의 다음 노드는 bottom
bottom->next = NULL; // bottom의 다음 노드는 없다.

int integer, i = 0; // 입력 받을 값, 반복을 위한 변수 선언

printf("변환할 10진수 : ");
scanf("%d", &integer); // 2진수로 변환할 정수 입력 받음

// interger를 2로 나눈 값이 0보다 크면 반복
while(integer > 0)
{
// integer 값을 2로 나눈 나머지 값을 스택에 저정
push(integer%2);
// integer 값을 2로 나눈 값을 integer에 저장
integer = integer / 2;
// pop() 호출 횟수를 정하기 위한 변수
i++;
}
printf("변환된 2진수 : ");
// push 한 횟수만큼 pop을 반복
while(i > 0)
{
// 스택에서 저장된 값을 가져옴
printf("%d", pop());
// push한 횟수만큼 반복하기 위한 변수
i--;
}
printf("\n");
return 0;
}

node* push(int val)
{
// 새로운 노드 new 선언
node *new;
// new 노드에 메모리 할당
if( (new = (node *)malloc(sizeof(node))) == NULL) {
// NULL 일 경우 메모리 할당 실패
printf("out of memory\n");
exit(1);
}
// 새로운 노드의 값은 넘어온 인자값 val
new->val = val;
// 새로운 노드의 다음 노드는 기존의 최상위 노드의 다음 노드
new->next = top->next;
// 최상위 노드의 다음 노드는 새로운 노드
top->next = new;

return new;
}

int
pop()
{
// 꺼내줄 노드 popup 선언
node *popup;
int val;
// popup 노드는 top의 다음 노드
popup = top->next;
// popup이 NULL이면 스택의 끝이다.
if (popup == NULL) return -1;
// 리턴할 값은 꺼내줄 노드 popup의 값
val = popup->val;
// 꺼내준 후 최상위 노드의 다음 노드는 기존의 최상위 노드의 다음->다음 노드
top->next = top->next->next;
// 꺼내준 노드의 메모리를 해제
free(popup);

return val;
}

참고 사이트
  http://blog.naver.com/takeoffx2?Redirect=Log&logNo=10012216700

// 최초버전
#include
<stdio.h>
#include <stdlib.h>

typedef struct stack {
int val; // 저장된 이진수 값
struct stack* next; // 다음 노드를 가리킴
}node;

void push(int val);
node* pop();
node* head;

int main()
{
//
node* new = NULL;
head = NULL;

int integer; // 입력 받을 값이 들어갈 변수

printf("변환할 10진수 : ");
scanf("%d", &integer); // 2진수로 변환할 정수 입력 받음

//interger를 2로 나눈 값이 0보다 크면 반복
while(integer > 0)
{
// integer 값을 2로 나눈 나머지 값을 스택에 저정
push(integer%2);
// integer 값을 2로 나눈 값을 integer에 저장
integer = integer / 2;
}

printf("변환된 2진수 : ");
// while 문의 정상적인 동작을 위해 최초의 pop을 수행
new = pop();
// node가 NULL(끝) 일때 까지 pop을 수행
while(new)
{
// 스택에서 저장된 값을 가져옴
printf("%d", new->val);
// pop을 한 후에 그 노드의 메모리를 해제
free(new);
// 다음 노드를 pop
new = pop();
}
printf("\n");
return 0;
}

void
push(int val)
{
node* new = NULL;

// 새로운 노드에 메모리 할당
new = (node*) malloc(sizeof(node));
// 새로운 노드에 값을 할당
new->val = val;

// 새로운 노드의 다음 노드는 기존의 최상위 노드가 되고,
new->next = head;
// 새로운 최상위 노드는 새로운 노드가 된다.
head = new;
}

node* pop()
{
// 값을 돌려주는데 사용할 노드 선언
node* new = NULL;
// 값을 돌려줄 노드에 최상위 노드를 할당
new = head;

// 최상위 노드가 NULL(끝)이 아니면
// 다음에 넘겨줄 최상위 노드를 설정한다.
if(head != NULL) {
head = head->next;
}

// 현재의 최상위 노드를 돌려준다.
return new;
}

참고자료
  C/C++ 개발자를 위한 포인터 실무 KIN - 사이텍 미디어

by sakuragi | 2007/03/06 18:39 | :: R space :: 과제 | 트랙백 | 덧글(11)

트랙백 주소 : http://sakuragis.egloos.com/tb/3170259
☞ 내 이글루에 이 글과 관련된 글 쓰기 (트랙백 보내기) [도움말]
Commented by 환상경 at 2007/03/06 20:40
우아아아아 천재천재천재~~~~~~~
우어어어어 굇수굇수굇수~~~~~~~
링크드 리스트;;;; Stack;;;;;

흑 머리속이 갑자기 어지러워지기 시작해요 흐~
Commented by LinDol at 2007/03/06 21:43
우와.. 예전에 풀어보려고 했는데 못풀었던 문제 ㅜ_ㅜ
대단하신..
Commented by sakuragi at 2007/03/06 22:33
환상경, 왜 이러셔요, 항상 공부 열심히 하시면서...
LinDol, 장기 게임 만드시는 LinDol 님이 대단하신거죠. :D
저는 아무것도 아니예요.. - _-)a
Commented by at 2007/03/07 18:59
결론: 숙제는 자기 힘으로.
Commented by lowid at 2007/03/07 23:46
그냥 2로 나눠효...
stack? 자료구조(또는 알고리즘?) 시간 같네요..
Commented by dasomoli at 2007/03/09 00:56
Recusive로 구현하면 저절로 Stack 구현이~~~~~
Commented by LinDol at 2007/03/09 22:09
스택은 예전 장기게임 한수 물르기 기능 구현할때.. 스택을 몰라서
완전..새됐던... 역시 기초가 중요! ㅋㅋ
Commented by sakuragi at 2007/03/10 13:04
샌, 자기 힘으로 해야죠.. -_-a
lowid, 알고리즘 수업이긴 한데.. 생각보다 만만치 않네요.
dasomoli, 재귀적인 프로그래밍은 너무 어려워요. 지금 그거 때문에 머리 깨질 것 같네요.
LinDol, 네. 기초가 중요하죠. 기초보다 수학이 중요하다고 느끼는 중.. ㅜㅡ
Commented at 2007/03/11 00:04
비공개 덧글입니다.
Commented by LinDol at 2007/03/12 10:45
수학 ㅜ_ㅜ
Commented by sakuragi at 2007/03/13 00:24
Magi, 그냥 내 잡다한 이야기를 하는 공간일 뿐일지도, 그러다 보면, 어쩌면, 그 이상이 될지도 모르지..
LinDol, 저도 수학에서 OTL

:         :

:

비공개 덧글

◀ 이전 페이지          다음 페이지 ▶

:+: sakuragi's Steam :+: