ExiiS 프로그래밍 저장소

0. 들어가기

우리는 앞선 시간에 스택과 큐에 대해서 공부했다.

이를 구현하기 위하여 배열과 연결리스트에 대해서 배웠고, 우리는 스택, 큐 구조를 구현했다.

스택과 큐의 경우 데이터를 한줄로 표현이 가능한 선형 구조에 해당했다.

이제 우리가 배워볼것은 계층을 가진 비선형구조, 트리에 대하여 배워 볼 것이다.

1. 트리의 기본 개념

트리의 경우 위와 같이 생겼다.

각 노드가 계층에 따라 갈라지는 모습을 하고있는 것이 나무를 반대로 세워놓은 것과 비슷해서 트리라는 이름이 붙여졌다.

그렇기 때문에 최상위에 있는 노드를 root node라고 부른다. 이와 마찬가지로 최하위에 있는 노드를 leaf node라고 부른다.

• tree 구조의 이름은 나무를 뜻하는 tree에서 가져왔다.
• 최상위 노드를 root node, 최하위 노드를 leaf node라고 부른다.

그럼 이번에는 각 노드간의 관계를 살펴보자.

같은 level에 존재하는 노드들을 형제노드(sibling)이라 부르고 자신의 하위에 있는 노드를 자식노드(children)이라고 부른다. 같은 맥락으로 자신의 상위에 있는 노드를 부모노드(parent)라고 부른다. 또한 자신의 상위에 있는 노드'들'을 조상(ancestor)이라 부른다. 

• 자신과 같은 레벨의 노드를 형제노드(sibling)이라 부른다.
• 자신의 하위노드를 자식노드(children)이라 부른다.
• 자신의 상위 노드를 부모노드(parent)이라 부른다.

이번에는 트리의 전체적인 구조를 살펴보자.

트리를 구성하는 일부분의 트리를 subtree 라고 부른다. 또한 그림에는 표시가 안되있으나 subtree의 집합을 forest라고 하며, 트리는 level으로 층이 분류가 되며, 트리의 가장 높은 level이 높이(height)가 된다.

• 트리를 구성하는 일부분의 트리를 subtree라고 한다.
• subtree의 집합을 forest라고 한다.
• 트리의 각 층은 level로 분류되며 가장 높은 level은 높이(height)가 된다.

트리의 기본은 이정도만 하고 가도 충분할 것 같다.

2. 이진트리 (binary tree)

그럼 자세한 트리를 만나볼 시간이다.

이번에 만날 트리는 이진트리, 즉 바이너리트리이다.

바이너리 트리는 왼쪽 자식과 오른쪽 자식, 두개의 자식만 갖는 트리이다.

즉, 좌측 노드와 우측 노드를 나눈다는 것에 의의가 생기는 구조이다.

이러한 바이너리 트리는 노드가 채워진 모양에 따라 다양하게 분류 될 수 있다.

full binary tree, complete binary tree,  등이 존재한다.

이들은 크게 중요한 개념이 아니므로 개인적으로 찾아보면 좋겠다.

다만 정말 중요한 개념은 다음의 것이다.

편향 트리, 경사트리라고도 하는 skewed tree의 모양이다.

노드가 한쪽 방향으로 치우쳐져있는 것을 볼 수있다.

이것이 트리의 단점인데, 데이터가 한쪽으로 치우칠경우 큐나 스택같은 선형구조와 다를게 없으며, 혹은 더 나쁜 상태가 된다.

따라서 이를 해결하기 위한 개념이 필수적인데 그것이 balanced tree 이다.

각 트리의 높이 차이를 제한을 둬서 최대한 균형을 맞춰보겠다는 의미이다.

3. 마무리

우리는 이제 선형구조에서 비선형 구조로 나아가는 첫걸음을 내딛었다.

다음시간에는 트리에서 사용되는 연산과 구현에 대해서 이야기 하자.

1. 들어가기

우리는 앞선 포스팅에서 스택과 큐에 대하여 간단하게 살펴보았다.

혹시나, 앞 포스팅을 보지 않았더라면 배열파트부터 살펴보는 것을 추천한다.

배열과 링크드리스트를 모른다면 자료구조는 시작할 수 없다.

2.  본론

이번에는 앞에서 배운 자료구조를 응용해보자 한다.

다만, 앞서서 살펴본 간단한 예제들과는 사뭇 다른 느낌이 들것이다.

이는 다음과 같은점 때문이라고 생각한다.

• 이론에서 응용으로의 문제
• 각종 예외처리에 대한 문제

pop, push에 대해서 null pointer 에대한 접근으로 인하여 생기는 segmentaion fault가 자주 발생 할 것이다.

통칭 세그폴트라고 불리는 저 오류는 자료구조를 공부할 때 정말 많이 나올 것이다.

따라서 여러분이 세그폴트를 만났을 때, null pointer에 접근하지 않는지 살펴보면 대부분 해결 될 것이다.

3. 각종 예제

백준 온라인 저지에 있는 스택, 큐,덱 카테고리의 문제를 살펴보자.

exiis-programming.tistory.com/category/%EB%B0%B1%EC%A4%80%20%EC%98%A8%EB%9D%BC%EC%9D%B8%20%EC%A0%80%EC%A7%80%20-%20%EB%8B%A8%EA%B3%84%EB%B3%84%EB%A1%9C%20%ED%92%80%EC%96%B4%EB%B3%B4%EA%B8%B0/%EC%8A%A4%ED%83%9D

exiis-programming.tistory.com/category/%EB%B0%B1%EC%A4%80%20%EC%98%A8%EB%9D%BC%EC%9D%B8%20%EC%A0%80%EC%A7%80%20-%20%EB%8B%A8%EA%B3%84%EB%B3%84%EB%A1%9C%20%ED%92%80%EC%96%B4%EB%B3%B4%EA%B8%B0/%ED%81%90%2C%20%EB%8D%B1

1. 큐란?

큐란 FIFO(First In First Out) 즉, 선입 선출 구조를 가진 자료구조다.

프린터의 대기열이나 번호표 등이 큐의 예시라고 이해하면 된다.]

2. 큐의 구현

큐 역시 배열과 링크드리스트 두가지의 방법으로 구현이 가능하다.

Enqueue와 Dequeue를 구현하는것을 목표로 진행하겠다.

2-1. 배열을 이용한 스택의 구현

// queue_array.c

#define MAX_LEN 5
#include<stdio.h>

void enqueue(int data);
void dequeue();
void show();

int queue[MAX_LEN];
int count = 0;

int main(void){
        int i;

        for(i=0; i<MAX_LEN; i++)
                enqueue(i);
        show();

        for(i=0; i<MAX_LEN; i++)
                dequeue();
        show();
        return 0;
}

void enqueue(int data){
        queue[count++] = data;
        printf("Enqueue %d \n", data);
}

void dequeue(){
        printf("Dequeue %d \n", queue[0]);
        for(int i=0; i<count-1; i++)
                queue[i] = queue[i+1];
        count--;
}

void show(){
        if(count == 0)
                printf("NO QUEUE!\n");
        for(int i=0; i<count; i++)
                printf("%d -> ", queue[i]);
        printf("\n");
}

5개의 데이터를 저장할 수 있는 큐를 배열로 만들었다.

스택과의 차이점이라고 하면 역시 입출력 순서일 것이다.

또한 큐를 당겨야하는 작업도 dequeue에서만 필요할 뿐 enqueue에서는 필요가 없다.

들어간 순서대로 나오기 때문에 0번째 인덱스부터 차곡차곡 데이터를 쌓아나간다.

이후 0번째 요소를 dequeue 하고, 나머지 요소들을 한칸씩 당겨주면 완성이다.

실행시 위와 같이 출력된다.

2-2. 링크드 리스트를 이용한 큐의 구현

// queue_linkedList.c

#define INPUT_LEN 5
#include<stdio.h>
#include<stdlib.h>

void enqueue(int num);
void dequeue();
void show();

typedef struct Node{
        int data;
        struct Node *next;
}node;

node* queue = NULL;

int main(void){
        int i;

        for(i=0; i<INPUT_LEN; i++)
                enqueue(i);
        show();
        for(i=0; i<INPUT_LEN; i++)
                dequeue();
        show();

        return 0;
}

void enqueue(int num){
        node* new_node = (node*)malloc(sizeof(node));
        new_node->data = num;
        new_node-> next = NULL;

        if(queue == NULL)
                queue = new_node;
        else{
                node* temp = queue;
                while(temp->next != NULL)
                        temp = temp->next;
                temp->next = new_node;

                printf("Enqueue %d\n", num);
        }


}

void dequeue(){
        printf("Dequeue %d\n", queue->data);
        node* temp = queue;
        queue = queue->next;
        free(temp);
}

void show(){
        node* temp = queue;
        if(temp == NULL) {
                printf("NO QUEUE!\n");
                return;
        }
        while(temp != NULL){
                printf("%d-> ", temp->data);
                temp = temp->next;
        }
        printf("\n");
}

링크드 리스트를 활용한 코드는 위와 같다.

코드의 길이가 길어졌지만 노드 구조체에 대한 부분이 추가되었을 뿐 큰 동작의 차이는 없다.

동작에 대한 도식화를 진행하면 다음과 같다.

링크드 리스트의 Front 부분인 node* queue에서 진입하여 3을 저장한 노드까지 이동한 다음 3의 next를 새로운 노드, 즉 4를 저장한 노드로 설정하면 enqueue 동작이 끝난다.

여기서 동작을 빠르게 하기 위하여 tail이라 표시된 부분, back의 주소를 따로 저장하여 back을 이용하여 enqueue 동작을 수행하는 방법도 있다.

• 위 코드에서는 enqueue 동작시 front부터 tail까지 하나하나 거쳐가며 새로운 노드가 들어갈 자리를 찾는다.           ( 0, 1, 2, 3 순서로 거쳐간다.)
• back이라는 새로운 변수를 통하여 바로 접근하여 enqueue 할 경우 성능의 향상을 도모할 수 있다.                       ( back 즉, 3에 바로 접근하여 4를 추가한다음 4를 back으로 설정한다면 성능 개선이 가능하다. )

dequeue의 경우에는 front에서 진행하므로 front를 dequeue하고 다음 노드인 1을 front로 설정해주면 된다.

이 코드의 출력은 다음과 같다.

3. 마무리

큐의 기본적인 구현 방법에 대하여 알아보았다.

다만 큐는 다양한 종류를 가지고 있다. 어떻게 연결되었는지, 방향이 어디인지 등에 따라 나눠진다.

다음에는 그에 대한 것을 다뤄보겠다.

1. 스택이란?

스택이란 LIFO(Last In First Out) 즉, 후입선출 구조를 가진 자료구조이다.

쓰레기통을 생각하면 가장 편하게 떠올릴 수 있으며, 게임을 좋아하는 사람이라면 스택이란 용어가 익숙할 것이다.

2. 스택의 구현

스택의 구현을 어떻게 할까?

구현 방법에 대해서는 이미 우리는 알고 있다.

앞에서 배운 배열과 링크드리스트 중 하나를 선택하는 것이다.

2-1. 배열을 이용한 스택의 구현

// stack_array.c

#define MAX_LEN 5

#include<stdio.h>

int count = 0;
int array[MAX_LEN];

void push(int num);
void pop();
void show();

int main(void){
        int i;

        for(i=0; i<MAX_LEN; i++)
                push(i);
        show();
        for(i=0; i<MAX_LEN; i++)
                pop();

        show();
        return 0;
}

void push(int num){
        for(int i=count; i>0; i--)
                array[i] = array[i-1];

        array[0] = num;
        printf("push : %d\n", num);
        count++;
}

void pop(){
        printf("pop : %d\n", array[0]);
        for(int i=0; i<count-1; i++)
                array[i] = array[i+1];
        array[--count] = -1;
}

void show(){
        printf("ARRAY INFO\n");
        printf("COUNT : %d\n", count);
        for(int i=0; i<MAX_LEN; i++)
                printf("%d -> ", array[i]);
        printf("\n");
}

이번 구현은 편하게 전역변수를 이용했다.

구현에 있어서 중요한 요소들은 다음과 같다.

• 전역변수 int count : 현재 스택에 있는 데이터의 갯수
• int array[MAX_LEN] : 스택의 역할을 할 배열
• #define MAX_LEN 5 : 배열의 길이인 5를 선언
• push, pop, show 함수 : 각각 스택에 값을 저장, 꺼내기, 스택을 보여주기 역할을 하는 함수

먼저 main함수에서의 동작은 다음과 같다.

1. 스택에 반복문을 이용하여 0~4의 값을 push
2. show()를 통하여 현재 상태 출력
3. 반복문을 이용하여 pop()을 5번 호출
4. show()를 통하여 현재 상태를 출력

다음은 push 함수의 동작을 도식화 해보았다.

배열을 활용한 스택의 경우, 각 원소들을 뒤로 한칸씩 계속 밀어줘야한다.

맨 마지막 배열의 4가 들어간 곳을 쓰레기통의 입구라고 생각하고, 0이 저장된 곳이 쓰레기통의 바닥이라고 생각하면 편하다.

pop의 경우, 원소들이 미뤄지는 방향만 바꾼것이라고 생각하면 편하다.

pop에서는 이렇게 빠져나간 자리에는 -1을 대입하여서 빠져나갔음을 표시해 주었다.

프로그램을 실행하면 다음과 같이 동작한다.

2-2. 링크드 리스트를 이용한 스택의 구현

// stack_linkedList.c

#define INPUT_LEN 5

#include<stdio.h>
#include<stdlib.h>

typedef struct Node{
        int data;
        struct Node *next;
}node;

void push(int num);
void pop();
void show();

node* head = NULL;

int main(void){
        int i;
        for(i=0; i<INPUT_LEN; i++)
                push(i);

        show();

        for(i=0; i<INPUT_LEN; i++)
                pop();
        show();
        return 0;
}

void push(int num){
        node* new_node = (node*)malloc(sizeof(node));
        new_node->data = num;
        new_node->next = head;
        head = new_node;
        printf("push %d\n", head->data);
}

void pop(){
        node* temp = head;
        printf("pop %d\n", head->data);
        head = head->next;
        free(temp);

}

void show(){
        node* temp = head;
        if(temp == NULL) printf("NO STACK!");
        while(temp != NULL){
                printf("%d ->", temp->data);
                temp = temp->next;
        }
        printf("\n");

}

링크드 리스트를 활용한 스택의 구현 또한 쉽게 만들어 봤다.

코드의 길이는 길어졌을 지 모르겠으나 링크드 리스트를 이용한 구현이 더욱 편리하다.

링크드리스트에서 필요한 필수 요소는 다음과 같다.

• 스택 접근을 위한 전역변수 head
• push, pop, show 함수

배열보다 훨씬 간단하지 않은가?

main 함수의 구성은 array로 구현했을때와 동일하다.

그럼 링크드 리스트를 활용한 각 동작을 도식화한 사진을 보면서 이해해보도록 하겠다.

새로운 값을 가진 노드를 이전 head와 연결해주고, 새로운 노드를 다시 head로 지정해주면 끝난다.

녹색 상자를 살펴보면, 배열에 비해 얼마나 간단한지 알 수 있다.

배열의 경우 새로운 값이 들어오게 된다면 나머지 요소들을 다 뒤로 한칸씩 미뤄줘야 했다.

허나 링크드리스트를 사용한다면 노드의 연결과정과 head의 재설정만 해주면 끝난다.

좌측이 배열을 사용한 push 과정이고 우측이 linked list를 이용한 push 과정이다.

얼마나 linked list가 간단한지 한눈에 보이지 않는가?

pop 과정 또한 역시 free()를 활용하여 노드의 메모리 할당을 해제해주고 head를 기존 head의 next로 설정해주기만 하면 끝이다.

3. 정리

배열과 링크드리스트를 활용하여 스택을 구현해보았다.

아직까지는 큰 어려움이 없는 자료구조라고 생각한다.

하지만 링크드리스트를 공부한지 얼마 안된 사람들이라면 링크드 리스트의 강력함을 알았으면 좋겠고 배열보다는 노드구조를 활용하여 구현하는 것에 익숙해졌으면 좋겠다.

1. 들어가기

우리는 이전 시간 배열을 통한 출석부 프로그램을 만들었다.

다만 그 프로그램에서 마음에 안드는 부분이 있었다.

• 30개의 배열을 선언했는데, 30명을 다 못채우면 메모리 낭비가 생긴다.
• 인원이 30명 이상이면 배열로썬 저장할 방법이 없어진다.

위의 문제점을 해결하기 위하여 연결리스트라는 방법을 사용할 것이다.

2. 연결 리스트(Linked List)

링크드 리스트는 데이터와 포인터를 가진 노드라는 구조를 이용하여 데이터를 저장하는 방식이다.

위의 그림을 살펴보면 각 노드는 12, 99, 37이라는 데이터를 저장하고 있고, 다음의 노드로 연결되어 있다.

이것을 C로 구현해보자.

2.1 노드의 구조

// node.c

#include<stdio.h>
#include<stdlib.h>

typedef struct Node{
        int data;
        struct Node* next;
}node;

int main(void){
        node* head = (node*)malloc(sizeof(node));
        head->data = 12;

        printf("%d", head->data);

        return 0;
}

Node구조체를 선언하고 그 이름을 typedef를 이용하여 node로 지어줬다.

main 함수에서 맨 처음 노드인 head를 설정하여 malloc으로 메모리를 할당했다.

malloc 함수는 주소값을 반환하기 때문에 node* 형 변수를 선언해줘야한다.

이후, data를 12로 초기화 하고 head의 데이터 값을 출력한다.

실행시켜보면 다음과 같이 출력한다.

2.2 노드의 추가 및 보여주기

//node.c

#include<stdio.h>
#include<stdlib.h>

typedef struct Node{
        int data;
        struct Node* next;
}node;

void insert(node** head){
        node *temp = *head;
        node *new_node = (node*)malloc(sizeof(node));
		
        // point 1
        while(temp->next != NULL)
                temp = temp->next;

        printf("input new data : ");
		
        //point 2
        scanf("%d", &(new_node->data));
        new_node->next = NULL;

        temp->next = new_node;
        printf("done.\n");
}

void show(node** head){
        printf("--- start print ---\n");

        node *temp = *head;
        while(temp != NULL){
                printf("%d\n", temp->data);
                temp = temp->next;
        }
}

int main(void){
        node* head = (node*)malloc(sizeof(node));
        head->data = 12;
        head->next = NULL;

        insert(&head);
        insert(&head);

        show(&head);

        return 0;
}

노드의 추가에 관한 방법이다.

insert, show, main 함수로 코드가 이루어져 있으며, insert부터 살펴보겠다. 

노드의 next가 null이 아닐경우 다음 노드로 이동하고,

next가 null일경우 다음 노드가 삽입될 부분을 찾았으므로 삽입한다.

그다음 주석 point 2에서는 노드에 데이터를 넣고, next를 NULL로 초기화 해주는 모습이다.

show 함수의 경우, 위의 그림과 비슷한 과정을 보여주므로 큰 설명은 생략하겠다.

단지 노드를 넘어가는 과정에서 해당 노드 값을 출력하는 것을 추가해줬을 뿐이며, temp가 NULL이 되면 반복을 종료한다.

출력 결과

원하는 출력 결과를 얻을 수 있음을 확인할 수 있다.

* 참고 : 코드의 도식화

new_node에 대하여 접근하는 요소들을 정리했다.

*new_node 의 경우 할당받은 메모리의 첫 주소를 가르키게 되고,

new_node->data의 경우 data의 메모리 주소, ( = int data )

new_node->next의 경우 next의 메모리 주소를 가르키게 된다. ( = node* next )

3. 활용

이전시간에 만든 출석부를 배열이 아닌 링크드리스트를 활용하여 설계해보자.

4. 마무리

우리는 자료구조에서 가장 중요한 노드라는 것을 배웠다. 또한 이를 이용하여 링크드리스트를 작성하는 방법을 배웠다.

이 배움은 우리에게 다음의 이점을 가져다 주었다.

• 더이상 배열에 의존해서 숫자 제한에 난감해질 필요가 없다.
• 메모리를 좀더 효율적으로 사용할 수 있게 되었다.

이제 자료구조를 배우기위한 중요한 조건, 노드라는 것을 이해했다. 

그럼 이제 본격적으로 자료구조와 알고리즘을 공부해보도록 하자.

1. 배열에 대하여

배열은 아주 쉽고 기초적으로 사용할 수 있는 자료구조이다.

숫자가 한정된 자료에 대하여 효과적인 방법이나, 큰 데이터를 다루기에는 부적합하다.

2. C에서의 배열

C에서는 아주 간단하게 배열을 선언하기만 하면 사용할 수 있다.

int array[100];

단 코드 한줄로 배열을 만들 수 있다.

위의 코드는 정수형 100칸짜리 배열을 선언하는 코드이다.

3. 배열을 사용한 자료구조

배열을 그 자체로 사용하여 자료구조를 활용할 수 있다.

예시로 학생의 출석부를 작성하는 프로그램을 구상해보자.

우리가 저장해야할 정보에 대해서는 다음과 같다.

• 학생의 출석번호
• 학생의 이름

4. 배열을 이용한 출석부의 구현

#include<stdio.h>

typedef struct stud{
        int stud_num;
        char* stud_name;
}student;


int main(void){
        student roster[30];

        roster[0].stud_num = 1;
        roster[0].stud_name = "김철수";
        printf("%d %s\n", roster[0].stud_num, roster[0].stud_name);
        return 0;
}

위의 코드는 stud_num과 stud_name을 가진 구조체를 선언하고, 구조체의 배열을 활용하여 출석부를 만든 예제이다.

sample data로 0번째 인덱스에 1번 김철수 학생을 넣었다.

따라서 출력은 다음과 같이 나온다.

1 김철수

위의 코드에서 입력을 받고 그 값을 출력하도록(조금더 있어 보이게) 만들면 다음과 같아진다.

// #01
// 배열을 이용한 출석부 만들기


#include<stdio.h>
#include<stdlib.h>

typedef struct stud{
        int stud_num;
        char* stud_name;
}student;


int main(void){
        int N;

        printf("number of student : ");
        scanf("%d", &N);

        //출석부 역할의 roster, student 배열 선언
        student roster[30];

        for(int i=0; i<N; i++){
                //문자열을 저장하기 위하여 동적 할당
                roster[i].stud_name = (char*)malloc(sizeof(char)*5);
                scanf("%d %s", &roster[i].stud_num, roster[i].stud_name);
        }

        printf("\n\n----print roster...----\n");
        for(int i=0; i<N; i++)
                printf("%d %s\n", roster[i].stud_num, roster[i].stud_name);
        printf("end print...\n");

        for(int i=0; i<N; i++)
                free(roster[i].stud_name);
        printf("end free...\n");

        return 0;
}

실행화면은 다음과 같다.

5. 정리

배열을 활용하여서 간단한 출석부를 만들고, 출석부의 내용을 출력하는 프로그램을 만들어 보았다.

다만, 여기서 마음에 안드는 부분이 생길 수 있다.

• 출석부 배열이 30명인데 5명을 저장하면 나머지 25명 분량은 메모리 손해를 본다.
• 인원이 30명 이상이 되버리면 저장을 하지 못한다.

이를 해결하기 위하여 다음 시간엔 링크드리스트를 학습하도록 하겠다.