[CS50X] 2024 Week5 Data Structures

 

Stacks, Queues

스택과 큐는 추상적인 데이터 구조이다.

처음 스택과 큐를 접했을 땐 stack 과 queue 라는 구조체가 있는 줄 알았다.

이건 프로그래밍 언어에서 지원하는 실질적인 구조체가 아니라

추상적인 데이터 구조이고 C에서는 많은 부분을 직접 구현해야한다.

 

Stack 은 1, 2, 3을 순서대로 넣는다면

3

2

1

이런 모양을 갖는다. 그리고 꺼낼땐 맨 위부터 꺼낼 수 있기 때문에

3 2 1 이 순서대로 꺼내진다.

이런 특징을 LIFO (Last In First Out) 라고 한다.

내가 어떤 문제를 푸는데 마지막에 들어간 것이 첫번째로 나와야 한다면 

Stack 구조를 생각해 볼 수 있다. ex) 최신 자료부터 보여주는 게시물

 

Queue 는 1, 2, 3 을 순서대로 넣는다면

1 2 3 

이런 모양이 된다. 왼쪽 부터 꺼내지기 때문에

1 2 3 그대로 꺼내진다. 

이런 특징은 FIFO (First In First Out) 라고 한다.

만약 먼저 들어간게 먼저 나와야하는 구조라면 Queue 구조를 생각해 볼 수 있다.

 

스택과 큐는 배열을 포함한 구조체로 생각해 볼 수 있으며

사실상 같은 구조를 갖지만 위에서 말한 것 처럼 사용자가 stack 혹은 queue 에 맞게 사용하는 것이다.

const int CAPACITY = 50;

typedef struct
{
    person people[CAPACITY];
    int size;
}
stack;

typedef struct
{
    person people[CAPACITY];
    int size;
}
queue;

 

 

 

 

Resizing Arrays

스택과 큐도 배열을 이용하고 배열은 메모리의 덩어리이고 연속적인 특성을 가지고 있다.

int arr[3] = {1, 2, 3} 을 할당했을 때 컴퓨터 메모리 캔버스이다.

arr의 메모리 덩어리를 어디에 저장할 지는 컴퓨터가 결정한다.

그리고 우리가 다루지 않는 메모리에는 가비지 값이 할당되어 있다.

고정된 크기의 배열을 사용하는 경우 문제가 없는데 

만약 배열의 크기를 동적으로 조절해야한다면 메모리의 크기를 조절해야한다.

메모리를 동적으로 melloc 을 이용하면 가능하다. 

melloc 으로 더 큰 메모리 덩어리를 할당 받아 arr를 복사하여 입력하고

arr 는 free로 풀어주는 방식이다. 

분명히 배열을 동적으로 늘릴 수 있는 방법이긴 한데

컴퓨터 메모리를 많이 사용할 뿐만 아니라 시간도 오래걸린다.

시간 복잡도는 O(n)이다.

배열의 길이가 30000이라면 1개를 더 입력하려면 30001 크기의 메모리를 새로 할당해야하고

60001 크기의 메모리를 순간적으로 사용하게 된다.

배열의 크기를 조절하는 방식이 좋은 디자인은 아닌 것 같다.

 

 

 

 

 

Linked Lists

배열에 추가적인 값을 넣고 싶을 때 배열 크기 자체를 조절하는 것은 적절하지 않다는 것을 알았다.

내가 어떤 문제를 해결하는데 직관적으로 배열을 사용해야 할 것 같을 때

크기가 동적으로 변한다면 연결 리스트 자료구조를 고려해 볼 수 있다.

배열과 달리 포인터를 활용하여 다음 값의 주소를 가르키는 방법을 사용한다.

메모리를 사용해서 값과 포인터를 함께 담고 있는 구조체를 만드는 것이다.

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

 

그리고 이런 구조체를 일반적으로 노드 라고 부른다. 

컴퓨터 메모리 노드의 모습

동작하는 모습

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

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

int main(int argc, char *argv[])
{
    node *list = NULL;
    for (int i = 1; i < argc; i++)
    {
        node *n = malloc(sizeof(node));
        if (n == NULL)
        {
            return 1;
        }
        n -> number = atoi(argv[i]);
        n -> next = list;
        list = n;
    }

    node *ptr = list;
    while (ptr != NULL)
    {
        printf("%i\n", ptr->number);
        ptr = ptr -> next;
    }
    
    ptr = list;
    while (ptr != NULL)
    {
        node *next = ptr->next;
        free(ptr);
        ptr = next;
    }
}

 

기본적인 형태의 연결 리스트 구현이다.

사용자에게 값을 받아서 출력하고 마지막에 malloc 한 메모리를 free 해준다.

이 구조에서 새로운 노드를 추가하는 시간 복잡도는 O(1) 이다.

배열의 O(n)과 비교하면 엄청나게 빨라진 것이다.

하지만 연결 리스트에서 특정한 노드를 찾는 시간 복잡도는 O(n) 이다.

배열에서의 이진탐색은 연결 리스트에서 사용할 수 없다. 메모리가 연속적으로 있는 것이 아니라 임의로 연결 했기 때문

배열 이진탐색의 시간복잡도는 O(log n)이다.

탐색에 있어서 연결 리스트가 더 느리다.

 

연결리스트에서 정렬을 구현해보면

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

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

int main(int argc, char *argv[])
{
    node *list = NULL;
    for (int i = 1; i < argc; i++)
    {
        node *n = malloc(sizeof(node));
        if (n == NULL)
        {
            return 1;
        }
        n -> number = atoi(argv[i]);
        n -> next = NULL;
        if (list == NULL)
        {
            list = n;
        }
        else if (n -> number < list -> number)
        {
            n -> next = list;
            list = n;
        }
        else
        {
            for (node *ptr = list; ptr != NULL; ptr = ptr -> next)
            {
                if (ptr -> next == NULL)
                {
                    ptr -> next = n;
                    break;
                }

                if (n -> number < ptr -> next -> number)
                {
                    n -> next = ptr -> next;
                    ptr -> next = n;
                    break;
                }
            }
        }
    }

    for (node *ptr = list; ptr != NULL; ptr = ptr -> next)
    {
        printf("%i\n", ptr -> number);
    }

    node *ptr = list;
    while (ptr != NULL)
    {
        node *next = ptr->next;
        free(ptr);
        ptr = next;
    }
}

 

이렇게 구현 할 수 있다.

이때의 시간 복잡도는 마찬가지로 O(n) 이다.

 

*강의에는 없는 내용이지만 내 생각에는 연결 리스트는 스택과 연계해서 사용하기 좋을 것 같다.

연결 리스트 구조에서 정렬이 필요하거나 내가 먼저 삽입한 것을 먼저 추출하려고 하면

꽤나 오랜 시간 O(n)이 걸린다.

하지만 스택과 같이 마지막에 삽입한게 먼저 추출한다고 하면 삽입을 O(1)에 구현할 수 있고 추출도 굉장히 빠르다. 

 

 

 

 

 

 

 

 

Trees

연결 리스트는 확실히 동적으로 변하는 데이터 구조를 만드는 것에 효과가 있었다.

하지만 탐색에 있어서 O(n) 이라는 상당히 긴 시간이 필요했다.

이러한 문제를 트리로 해결 할 수 있다.

트리는 종류가 상당히 다양한데 루트 노드가 있고 자식 노드로 뿌리내리는 계층적 데이터 구조를 트리라고 한다.

그 중에서도 Binary Search Tree 이진 탐색 트리에 대해 알아보면

이진 탐색 트리에서 부모 노드는 항상 2개의 자식 노드를 갖는다.

노드의 왼쪽에는 항상 더 작은 수가, 오른쪽에는 항상 더 큰 수가 위치한다.

이런 구조에서 탐색을 한다면 가장 아랫 단계까지 도달하려면 log n 만큼의 단계를 거쳐야한다.

찾으려는 수 가 가장 아랫 단계 (최악의 수)에 시간이 log n 즉 O(log n) 인 것이다.

새로운 수를 삽입하는 경우에도 O(log n) 이다.

이진 탐색 트리는 구조 자체를 Binary 와 Recursion 을 이용했다.

그래서 연결 리스트와 이진 탐색 트리는 선형 탐색과 이진 탐색의 차이와 유사한 점이 많다.

선형 탐색보다 이진 탐색이 속도가 빠른 대신 공간을 더 쓰는 것 처럼

이진 탐색 트리는 재귀적 구조로 더 많은 공간을 쓸 뿐만 아니라 구조 자체도

왼쪽, 오른쪽 2개의 포인터를 담을 공간이 필요하다.

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

// Represents a node
typedef struct node
{
    int number;
    struct node *left;
    struct node *right;
}
node;

void free_tree(node *root);
void print_tree(node *root);

int main(void)
{
    // Tree of size 0
    node *tree = NULL;

    // Add number to list
    node *n = malloc(sizeof(node));
    if (n == NULL)
    {
        return 1;
    }
    n->number = 2;
    n->left = NULL;
    n->right = NULL;
    tree = n;

    // Add number to list
    n = malloc(sizeof(node));
    if (n == NULL)
    {
        free_tree(tree);
        return 1;
    }
    n->number = 1;
    n->left = NULL;
    n->right = NULL;
    tree->left = n;

    // Add number to list
    n = malloc(sizeof(node));
    if (n == NULL)
    {
        free_tree(tree);
        return 1;
    }
    n->number = 3;
    n->left = NULL;
    n->right = NULL;
    tree->right = n;

    // Print tree
    print_tree(tree);

    // Free tree
    free_tree(tree);
    return 0;
}

void free_tree(node *root)
{
    if (root == NULL)
    {
        return;
    }
    free_tree(root->left);
    free_tree(root->right);
    free(root);
}

void print_tree(node *root)
{
    if (root == NULL)
    {
        return;
    }
    print_tree(root->left);
    printf("%i\n", root->number);
    print_tree(root->right);
}

 

 

 

 

 

 

 

Dictionaries / Hashing

"우리는 모두 O(1)를 꿈꾼다. 단지 공간이 부족할 뿐"

딕셔너리는 키와 값 의 형태로 된 자료구조를 뜻한다.

키를 통해 값을 찾을 수 있고 이 과정은 O(1)의 시간이 걸린다.

키와 값을 연결 시키는 것을 매핑이라고 하며

키 배열과 값 배열이 모두 배열이기 때문에 키와 값을 매핑하는 시간이 오래 걸릴 뿐더러

만약 키와 값의 갯수가 바뀐다면 훨씬 더 많은 시간과 메모리를 소모할 것이다.

달성하고 싶은 O(1)

 

딕셔너리 자체만으로는 부족한 점을 고안하기 위해 해싱과 해쉬테이블이라는 자료 구조가 나왔다.

딕셔너리가 배열과 배열을 매핑한 것이라면 해쉬테이블은 배열에 연결리스트를 매핑하는 것이다.

따라서 해쉬 테이블 키 값에 하나의 값만 있다면 O(1) 으로 처리 가능하지만

최악의 경우 모든 값들이 하나의 키에 매핑 되어 있다면 O(n)의 시간이 걸릴 것이고

일반적으로는 O(n/k)의 시간을 기대해 볼 수 있을 것이다.

시간 복잡도 O 로만 따지면 O(n/k) 나 O(n) 이나 같기 때문에

해쉬 테이블이 연결리스트에 비해 갖는 장점이 적어 보일 수 있는데

이론적으로는 같지만 현실에서 O(n/k)와 O(n) 는 상당히 큰 시간 차이를 보여주기 때문에 충분히 의미가 있다.

*더 알아보니 해쉬 테이블은 여러 형태로 구현 가능하고 연결리스트를 배열에 매핑하는 것은 체이닝 이라는 방식이다.

 

 

 

 

 

 

 

 

Tries

tries 트라이 자료구조는 배열의 트리이다.

트리의 각 노드는 배열이며 입력 가능한 모든 조합을 매핑한다.

포인터를 통해 노드로 하향 이동하고 키를 찾은 끝에는 값의 정보가 있다.

이러면 탐색을 하는데 O(k) 즉 O(1) 시간 밖에 걸리지 않는다.

하지만 노드에서 자식들에 대한 포인터를 모두 배열로 가지고 있기 때문에 큰 공간을 차지한다.

 

트라이는 동작할 때 이 전의 접두사들을 공유 하기 때문에 TOM 을 찾는다면 

1. 찾아야할 것 : T,O,M  /  찾은 것 : 

2. 찾아야할 것 : O,M  /  찾은 것 : T

3. 찾아야할 것 : M  /  찾은 것 : T,O

4. 찾아야할 것 :  /  찾은 것 : T,O,M. ==> 찾아야 할 것이 없으므로 찾고자 한 것을 찾은 상태

이런 방식으로 동작하기 때문에 접두사를 공유한다.

이런 특성 때문에 문자열 검색, 접두사 검색, 자동 완성 등에 특화되어 있다.

 

자료 구조를 정리하면서 느낀 것은 자료구조마다 특징이 다른데

탐색, 정렬과 마찬가지로 메모리와 시간의 상충 관계가 존재한다는 것이다.

초기 자료구조 생성에서 공간을 많이 쓰던 계산에서 공간을 많이 쓰던 공간을 많이 쓰면 시간이 빨라진다.

따라서 내가 공간은 많은데 빠른 시간이 필요할 지 시간이 좀 늦어도 되고 공간이 부족한 지에 따라

선택하는 자료구조가 달라질 것이며 용도와 상황에 따라 선택하는 자료구조는 달라질 것이다.