〔CS50 / C언어〕자료구조: 메모리 할당, 연결 리스트, 해시 테이블, 트라이, 스택, 큐, 딕셔너리

1. malloc

int main(void)
{
    int *x;
    int *y;

    x = malloc(sizeof(int));

    *x = 42;
    *y = 13;
}

 

위의 코드는 y 가 어디를 가리키는지 정의하지 않았다는 점에서 오류가 있다.

초기화되지 않은 *y 에 13 이라는 값을 저장하려고 하면 오류가 발생한다.따라서 y 가 가리키는 곳이 어디인지 정의하는 과정이 필요하다.

 

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

int main(void)
{
    int *x;
    int *y; 
    
    x = malloc(sizeof(int));
    
    y = x;
    
    *y = 13;
    
    printf("%i\n", *x);
    printf("%i\n", *y);
    
    free(x);
}

 

y = x 라는 코드를 더해줌으로써 y 가 가리키는 곳이 x 와 같게 되었다.

따라서 *y = 13 이라는 값을 저장하면 *x 역시 13 으로 출력되는 것을 확인할 수 있다.

 

---

 

2. realloc

이미 저장된 배열의 크기를 늘리고 싶다면 어떻게 해야할까?

현재 배열이 저장된 메모리의 바로 옆에 메모리를 덧붙인다면, 이미 다른 데이터가 저장되어 있을 수 있다는 문제가 있다.

따라서 새로운 공간에 원하는 크기의 메모리를 다시 할당하고 기존 배열의 값을 복사하여야 한다.

배열의 값을 하나하나 복사하는 과정에서 n 만큼의 실행 시간이 필요하므로 실행 시간의 상한은 O(n) 이 된다.

 

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

int main(void)
{
    int *list = malloc(3 * sizeof(int));
    
    if (list == NULL)
    {
        return 1;
    }
    
    list[0] = 1;
    list[1] = 2;
    list[2] = 3;
    
    // Reallocation of memory
    int *tmp = realloc(list, 4 * sizeof(int));
    
    if (tmp == NULL)
    {
        return 1;
    }
    
    list = tmp;
    
    list[3] = 4;
    
    for (int i = 0; i < 4; i++)
    {
        printf("%i\n", list[i]);
    }
    
    free(list);
}

 

realloc(복사하려는 배열, 메모리 크기) 함수를 이용하면 간단하게 메모리를 재할당하고 값을 복사할 수 있다.

만약 realloc 함수를 이용하지 않는다면 *tmp = malloc(4 * sizeof(int)) 로 새로운 메모리를 할당해주고

for 반복문을 이용하여 기존 배열의 값들을 tmp 배열에 복사하는 두 가지의 과정이 필요하게 된다.

*** 메모리를 할당한 후에는 free 함수를 이용하여 메모리 공간을 해제하는 것을 잊지 말자!

 

---

 

3. 연결 리스트(Linked Lists)

(1) 정의

배열에서는 각 인덱스의 값이 메모리 상에 연이어 저장되어 있다.

하지만 연결 리스트를 이용한다면 값들이 메모리 상에 산재되어 있더라도 여전히 값을 연이어 읽어들일 수 있다.

연결 리스트는 각 인덱스의 메모리 주소에서 자신의 값과 바로 다음 값의 메모리 주소(=포인터)를 저장한다.

typedef struct node
{
    int number;
    struct node *next;
}
node;

 

node 라는 이름의 구조체에는  number 와  *next  두 개의 필드가 함께 정의되어 있다.

여기서 number 는 각 노드가 가지는 값을 의미하며 *next 는 다음 노드 를 가리키는 포인터를 의미한다.  

위의 예시에서 연결 리스트의 첫 번째 노드는 "1" 과 다음 노드의 메모리 주소인 "0x456" 을 저장하고 있다.마지막 노드는 다음 값이 존재하지 않기 때문에 "3"과 NULL, 즉 "\0" 을 저장하고 있다.

 

연결 리스트에 값을 추가하거나 검색하는 경우 실행 시간의 상한은 어떻게 될까?

해당 위치까지 연결 리스트의 각 노드를 따라 이동해야 하므로 실행 시간의 상한은 O(n) 이 된다.

 

typedef struct {} 가 아니라 typedef struct node{} 인 이유는 구조체 안에서 node 를 사용하기 위해서이다.

마찬가지로 node *next; 가 아니라 struct node *next; 라고 써야 구조체 안에서 node 자료형을 인식할 수 있다.

 

---

 

(2) 연결리스트: 코딩

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

typedef struct node
{
    int number;
    struct node *next;
}
node;

int main(void)
{
    node *list = NULL;
    
    node *n = malloc(sizeof(node));
    
    if (n != NULL)
    {
        n->number = 1;
        n->next = NULL;
    }
    
    list = n;
    
    n = malloc(sizeof(node));
    if (n != NULL)
    {
        n->number = 2;
        n->next = NULL;
    }
    
    list->next = n;
    
    n = malloc(sizeof(node));
    if (n != NULL)
    {
        n->number = 3;
        n->next = NULL;
    }
    
    list->next->next = n;
    
    for (node *tmp = list; tmp != NULL; tmp = tmp->next)
    {
        printf("%i\n", tmp->number);
    }
    
    while (list != NULL)
    {
        node *tmp = list->next;
        free(list);
        list = tmp;
    }
}

 

앞에서 정의한 node 구조체를 이용해서 실제로 연결 리스트를 구현해보자.

우선 연결 리스트의 첫 번째 노드를 가리킬 list 라는 이름의 node 포인터를 정의한다.

지금으로서 아무것도 가리키지 않고 있기 때문에 node *list = NULL; 로 초기화 해준다.

 

이제 새로운 노드에 값을 저장하기 위해 n 이라는 이름의 node 포인터를 만들고 메모리를 할당해준다.

n의 number 필드에는 "1" 을 값으로 저장하고 다음에 저장된 노드가 없으므로 "next" 필드는 NULL 로 초기화한다.

이로써 첫 번째 노드가 정의되었기 때문에 list 포인터가 n 의 메모리 주소를 가리키도록 list = n; 을 작성한다.

 

이제 list 에 두 번째 노드를 연결하기 위해 n 에 새로운 메모리를 할당하고 number 에 "2" 를 저장하고 next 를 초기화한다.

현재 list 가 가리키고 있는 것은 첫 번째 노드이므로 두 번째 노드를 n 포인터로 지정하도록 list -> next = n; 을 작성해준다.

마찬가지로 세 번째 노드를 연결하기 위해 n 에 새로운 메모리를 할당하고 number 에 "3" 을 저장하고 next를 초기화한다.

list -> next -> next = n; 으로써 list 가 가리키는 첫 번째 노드(list->next)가 가리키는 두 번째 노드(list->next->next) 가 가리키는 메모리 주소를 n 포인터로 지정한다.

 

마지막으로 for 반복문으로 각 노드를 처음부터 방문하며 number 값을 출력하고 while 반복문을 통해 메모리를 해제한다.

n->number 는 (*n).number 을 더욱 간단하게 표현하는 방식으로 같은 의미를 가진다.

 

---

 

 

 

(3) 연결 리스트: 트리(Tree)

 

 

트리는 연결 리스트를 기반으로한 새로운 데이터 구조이다.

연결 리스트의 노드들이 1차원적으로 연결되어 있는 것에 반해 트리에서의 노드들은 2차원적으로 연결되어 있다.

각 노드들은 일정한 층에 속하고 다음 층의 노드들을 가리키는 포인터를 가진다.

최상위 층의 노드를 루트(Root) 노드라고 하며 하위 노드들을 자식(Child) 노드라고 한다.

 

사진에 있는 '이진 검색 트리' 는 이진 검색을 수행하는데에 유리하다.

아래의 예시는 이진 검색 트리의 노드 구조체 정의와 '50' 을 재귀적으로 검색하는 이진 검색 함수를 구현한 코드이다.

 

typedef struct node
{
    int number;
    struct node *left;
    struct node *right;
}
node;

bool search (node *tree)
{
    if (tree == NULL)
    {
        return false;
    }
    else if (node *tree > 50)
    {
        return search (tree->left)
    }
    else if (node *tree < 50)
    {
        return search (tree->right)
    }
    else
    {
        return true;
    }
}

이진 검색 트리의 검색 실행 시간과 노드 삽입 시간의 상한은 O(log n) 이다.

반드시 연결 리스트를 이용하지 않아도 배열의 인덱스를 이용하여 트리를 만드는 방법도 있다.

 

---

 

4. 해시 테이블(Hash Table)

 

해시 테이블은 연결 리스트의 배열 으로 버킷(Bucket) 이라고도 한다.

 

해시(Hash)란 데이터를 변환하는 기법 중의 하나로 임의의 문자열에 해시 함수를 취하여 고정된 길이의 문자열을 반환한다.

해시 함수(Hash Function)는 주어진 입력값을 이용하여 특정한 인덱스로 변환시켜주는 함수이다.

여기서 해시 함수의 입력값인 임의의 문자열을 키(Key) 라고 한다.

그리고 출력값인 고정 문자열을 해시 테이블의 인덱스(Index) 혹은 버킷 주소(Bucket Address) 라고 한다.

인덱스는 해시 테이블에 접근하기 위하여 사용된다.

만약 다른 입력값에 대해 동일한 인덱스가 나오게 되면 충돌(Collision) 이 되므로 주의해야 한다.

충돌이 잦으면 해시의 최대 장점인 key 를 통해 O(1) 만에 value 를 가져올 수 없게 된다.

 

해시 테이블(Hash Table)은 key-value 가 한 쌍을 이루는 자료 구조를 의미한다.

여기서 key 는 해시 함수의 입력값을 value 는 해시 함수의 출력값을 의미한다.

버킷 사이즈(Bucket Size)는 충돌이 발생할 경우를 대비하여 key 를 연속적으로 저장하기 위한 공간을 의미한다.

 

예시로 위의 사진처럼 사람의 이름을 해시 테이블에 저장할 수 있다.

여기서 해시 함수는 '이름의 가장 첫 글자' 이며 알파벳 개수만큼 총 26개의 포인터가 생긴다.

각각의 포인터는 해당 알파벳으로 시작하는 이름들을 저장하는 연결 리스트를 가리키게 된다.

여기서 'H' 와 'L' 로 시작하는 이름이 세 개이므로 버킷 사이즈는 '3' 이 된다. 

 

---

 

5. 트라이(Trie)

 

트라이는 기본적으로 '트리' 형태의 자료 구조로 각 노드가 커다란 배열을 가진다.

문자열의 길이가 일정한 경우 문자열들을 저장하고 관리하기에 최적의 자료 구조이나 직접 구현하기에 난이도가 매우 높다.

트라이는 검색 엔진이나 사전에서의 자동 완성 기능에 사용될 수 있다.

 

오른쪽 사진은 영어 알파벳으로 이루어진 문자열을 저장한 예시로 각각의 노드는 A 부터 Z 까지의 값을 가지는 배열이 된다.

만약 'Hermione' 'Harry' 'Hagrid' 을 위의 트라이에서 검색한다면 각각 8, 5, 6 의 실행 시간이 소요된다.

이처럼 트라이에서 검색 실행 시간은 대부분 작은 '문자열의 길이'에 한정되므로 실행 시간의 상한은 O(1) 이나 마찬가지이다.

 

---

 

6. 스택 · 큐 

스택과 큐는 데이터를 일시적으로 저장하기 위한 자료 구조이다.

스택(Stack)은 데이터가 위로 저장되는 구조로 후입선출(LIFO) 방식으로 값을 넣고 뺀다.

예를 들어 은행에서 가장 먼저 줄을 선 사람이 가장 먼저 업무를 처리하는 것과 같다.

큐(Queue)는 데이터가 아래로 저장되는 구조로 선입선출(FIFO) 방식으로 값을 넣고 뺀다.

예를 들어 뷔페에서 사람들이 가장 나중에 쌓인 접시를 가장 먼저 들고 가는 것과 같다.

스택과 큐는 모두 배열이나 연결 리스트를 통해 구현 가능하다.

키워드 코딩 프로그래밍

 

[참고]

네이버 부스트코스 모두를 위한 컴퓨터 과학

모두를 위한 컴퓨터 과학 (CS50 2019)

 

컴퓨터 프로그래밍 코딩 교육