[CS50] 6강 자료구조

 

하버드 cs50 강의의 최종장

 

강의의 시작은 malloc과 포인터에 대한 복습으로 시작하고, malloc으로 선언한 배열의 크기를 조정할 수 있는 realloc 사용하는 방법을 배운다.

// tmp라는 포인터에 기존에 정의한 list 배열에
// int크기(4byte) 5개의 메모리주소를 재 정의후 기존 배열 값들을 복사한다.
int *tmp = realloc(list, 5*sizeof(int));

 

 

연결 리스트

 

일반적으로 자료 구조란 C나 C++, 자바, 파이썬에 있는 프로그래밍 구조일 뿐이다. 

컴퓨터 메모리에 정보를 각기 다른 방법으로 저장할 수 있도록 해준다.

 

배열에서는 각 인덱스의 값이 메모리상에 나란히 붙어서 저장되어 있다. 그래서 중간중간 데이터를 추가하려 할 때 realloc으로 배열의 길이를 재 할당하고 포인터를 옮겨주고, 다시 free로 기존 할당되었던 malloc 함수를 해제시켜줘야 하는 번거로움이 있다. 하지만 각각의 값이 메모리 상의 여러 군데 나뉘어 있고 메모리 주소만 기억하고 있다면 값을 추가하기 쉬울 것이고 값을 연속해서 읽어올 수도 있다. 

 

이것을 "연결 리스트" 라고 표현하는데 malloc으로 메모리를 생성할 때 struct를 이용해 자신의 값과 다음 주소 값(포인터)을 가지고 있는 것이다.

 

연결 리스트 추상 이미지

 

연결 리스트는 메모리 덩어리 여러 개를 포함한 데이터 구조이다. 어떤 방식으로든 연결되어 있는데 어떤 방식은 곧 포인터로서 연결되어있다. 

구조체 struct를 이용해 연결 리스트 개념을 만들 수 있다.

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

node라는 이름을 가진 구조체를 선언하고, 선언된 node 자료형을 구조체 안에서 next포인터 변수로 다음 가리킬 주소 값을 저장할 수 있게 재귀 형태로 만들 수 있다.

 

연결 리스트를 이용해 배열을 추가하는 코드를 작성해봤다.

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

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

int main(void)
{
    node *list = NULL;

    node *n = malloc(sizeof(node));
    if (n == NULL)
    {
        return 1;
    }

    printf("name of list pointer : %p\n", list);
    printf("name of n pointer : %p\n", n);
    printf("------------------------------\n");

    n->number = 1; // 새로 선언한 포인터 n이 가리키는 number와 next주소값을 추가한다.
    n->next = NULL; // 다음에 해당하는 값이 없으므로 NULL

    list = n; // 기존선언한 list포인터는 node 가 n을 가리키게 되며 리스트가 첫번째 node를 갖게 되었다.
    printf("name of list pointer : %p\n", list);
    printf("name of n pointer : %p\n", n);
    printf("------------------------------\n");

    // n은 다시 malloc 함수를 통해 메모리를 재 할당받는다.
    // 이하 반복
    n = malloc(sizeof(node));
    if (n == NULL)
    {
        return 1;
    }

    printf("2name of list pointer : %p\n", list);
    printf("2name of n pointer : %p\n", n);
    printf("2------------------------------\n");

    n->number = 2;
    n->next = NULL;

    // list가 가리킨 next의 주소값인 node의 next에 두번째 node n을 추가한다.
    list->next = n; 
    printf("2name of list pointer : %p\n", list);
    printf("2name of n pointer : %p\n", n);
    printf("2------------------------------\n");

}

 

연결 리스트는 값을 검색하는데 걸리는 시간은 줄을 짓는 모습으로 연결되어 있는 모습으로 O(n)이 된다.

 

 

 

트리

트리는 연결리스트를 기반으로 한 새로운 데이터 구조이다. 일차원적인 배열에서 이차원 배열로 바라보는 방식이다.

이진 탐색 트리

연결 리스트가 다음 연결 주소를 한 개만 갖고 있는 반면 트리 구조는 두 개의 포인터 (left, right)를 갖고 있다.

가계도 같은 트리를 만드는 데 사용하고 이것이 이진 탐색 트리이다.

 

가장 높은 층에서 트리가 시작되는 노드를 '루트'라고 한다. 루트 노드는 다음 층의 노드 두 개를 가리키고 이것을 '자식 노드'라고 부른다.

 

2차원 적이고 재귀적으로 정의되어 있다. 왼쪽은 작고, 오른쪽은 크다. 따라서 일차원적인 연결 리스트를 벗어나 이진 검색이 가능하게 된다.

하지만 포인터가 두개이므로 기존 연결 리스트보다 메모리 사용이 증가하는 것을 감수해야 하는 단점이 있다.

 

 

해시 테이블

해시 테이블은 배열과 연결리스트를 조합한 것이다.

배열을 가로가 아닌 세로로 표현한 상태에서 가로로 배열을 추가하는 구조가 바로 해시 테이블이다.

 

입력값을 받아서 출력값을 내보내는 것으로 기존 함수와 같은 역할을 하는 것이 해시 함수라고 한다.

해시함수는 이러한 자료구조에서 인덱싱을 하는 데 사용하는 함수인 것이다.

 

이미지는 사람의 이름이 해시 테이블로 저장되고, 해시 함수는 이름의 첫 글자 알파벳이다. 

이 경우 알파벳에 총 갯수에 해당하는 26개의 포인터가 있고 각 포인터는 알파벳으로 시작하는 이름을 저장하는 연결 리스트를 가리키게 된다. 이 테이블의 성능을 결정하는 것은 메모리 저장 공간이다.

Hagrid 이름을 검색하게 되면 연결 리스트를 이용해 3번의 절차를 확인해야 한다. 테이블의 성능을 확장시키려면 알파벳 이름의 두 글자까지 늘려 Ha Hb Hc Hd... Ht Hu.. Hy Hz 두 개의 알파벳까지 저장할 수 있는 테이블을 만들면 메모리는 급격하게 필요하지만 성능은 더욱 향상될 수 있다. 해시함수에 중복되어 들어가게 되는 값들이 하나일 경우 이상적이라고 할 수 있다.

 

일반적으로 해시함수를 사용하는 경우에 최대한 확장한 해시함수를 사용하기 때문에 O(1)에 가깝다고 한다.

 

 

 

트라이 Tries

검색 (retrieval)의 줄임말로서 '트라이'라고 불리는 자료구조는 기본적으로 '트리' 형태의 자료 구조이다.

트라이는 하나의 자원을 절약하기 위해 다른 자원을 소비하는 패턴을 가진다. 트라이에는 많은 메모리가 들지만 자료구조 안에 있는 이름이나 단어를 검색할 때 일정한 실행시간 O를 갖는다.

각각의 노드가 배열로 이루어진 트리이다.

자료구조 트라이 이미지

트라이는 각 노드가 배열로 구성되어 있으므로 맨 첫번째 배열이 루트 노드가 된다. 

 

트라이에서 값을 검색하는데 걸리는 시간은 '문자열의 길이 = n'에 한정된다. 따라서 O(n)으로 표현할 수 있고, 이름 검색 같은 조건은 크지 않은 상수값으로 한정되기 때문에 O(1)이라고 부를 수 있다.

 

검색 속도가 어마어마하게 빠르겠지만 각 글자마다 배열인 노드를 부여하기 때문에 막대한 메모리 용량이 필요할 것이다.

 

 

큐 Queues | 스택 stack

큐는 가게나 식당 앞에 서있는 대기 줄 같은 것이다. 줄을 먼저 선 사람이 가장 먼저 티켓을 구매할 수 있다. 그러므로 가장 늦게 온 사람은 가장 늦게 티켓을 받을 수 있다. 이것을 선입 선출이라고 하고 FIFO (First In First Out)라고 한다. 

예전에 카페 알바에서 우유 같은 식품을 선입 선출하라고 교육받았던 게 생각난다.

큐에서 사용되는 용어가 두 개 있다. enqueue 줄에 들어가서 서는 것을 의미하고, dequeue는 줄에서 빠져나오는 것을 의미한다.

 

큐와 반대의 개념인 스택은 쌓인 쟁반 같은 것이다. 카페 알바를 할 때 잘 닦은 쟁반을 앞에 쌓아둔다.

손님에게 나갈 때 맨 위에 쌓인 쟁반으로 커피를 올려 벨을 울리곤 했다. 아래에서 위로 쌓이고 위에서 가장 먼저 빠져나간다. 이것을 LIFO(Last In First Out)라고 한다. 메일함도 LIFO형태이다. 가장 최신의 메일이 위에 쌓이고 일찍이 온 메일들은 아래로 밀려난다. 스택에서 사용되는 용어는 push 스택에 어떤 요소를 추가한다는 뜻이고, pop은 가장 위의 요소를 뺀다는 뜻이다.

 

강의에서는 딕셔너리 dict 형태를 키와 값 단어와 페이지 번호 등 다양한 쌍으로 이루어져 있는 영어 사전 같은 것이라고 짧게 말하고 넘어가고 CS50 강의를 마무리한다.