[CS50] Chapter 6. 자료구조

최초작성일: 2023-03-01
마지막 수정일: 2023-03-04

부스트코스 <모두를 위한 컴퓨터 과학 (CS50 2019)> 강의 수강

 

6. 자료구조 Data Structures

1. malloc과 포인터 복습

• 포인터의 개념과 malloc 함수의 용법을 잘 이해할 수 있다.
• 포인터, malloc

 

포인터 선언

int main(void)
{
    int *x;     // 정수를 가리키는 포인터를 만들고 x라고 부름
    int *y;     // 정수를 가리키는 변수 y

    x = malloc(sizeof(int));    // int 크기의 메모리를 만들어 x에 할당

    *x = 42;    // x에 저장된 주소로 가서 42를 저장
    *y = 13;    // 변수를 위한 공간을 할당하지 않음
}

• 포인터를 할당하면 어떤 포인티를 가리킬지 별개로 설정하는 과정이 필요하다.
• 위의 코드에서 y는 포인터로 선언만 되었을 뿐 어디를 가리킬지는 아직 정의되지 않은 상태
• 초기화되지 않은 *y는 프로그램 어딘가를 임의로 가리키고 있을 수 있다.

    y = x;      // x가 가리키는 곳과 동일한 곳 가리킴
    *y = 13;    // y에 저장된 주소(=x에 저장된 주소)로 가서 13 저장.
    // 원래 x에 저장된 주소 위치에 저장했던 42는 13으로 덮어쓰기된다.

 

2. 배열의 크기 조정하기

• 배열의 크기를 조정하는 코드를 작성할 수 있다.
• malloc, realloc

C에서 배열의 크기는 미리 지정해야

• 배열의 크기를 바꾸려면 다른 메모리로 이동시켜야 한다.
• O(n): 배열의 길이에 따라 옮기는 데 더 많은 과정이 필요

malloc 이용해서 배열 크기 바꾸기

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

int main(void)
{
    // int 자료형 3개로 이루어진 list라는 포인터를 선언하고 메모리 할당
    int *list = malloc(3 * sizeof(int));    // list는 메모리 덩어리의 주소를 담고 있음

    // 포인터가 잘 선언되었는지 확인
    if (list == NULL)   // 메모리가 부족해서 NULL이 반환되었을 때
    {
        return 1;
    }

    list[0] = 1;        // 주소는 4바이트씩 차이남
    list[1] = 2;
    list[2] = 3;

    int *tmp = malloc(4 * sizeof(int));
    if (tmp == NULL)
    {
        return 1;
    }

    // Copy integers from old array into new array
    for (int i = 0; i < 3; i++)
    {
        tmp[i] = list[i];
    }

    tmp[3] = 4;

    free(list);     // 메모리 해제

    list = tmp;     // 이름 바꿈

    for (int i = 0; i < 4; i++)
    {
        printf("%i\n", list[i]);
    }
}

/*
1
2
3
4
*/

realloc 이용해서 배열 크기 바꾸기

• realloc
  • 이미 할당받은 기존 메모리 덩어리를 새롭게 가져오고 새롭게 설정된 크기로 바꾸는 작업을 함
  • 기존 배열에서 새로운 배열로 데이터를 복사해줌

#include <stdio.h>
#include <stdlib.h>     // malloc   // realloc

int main(void)
{
    int *list = malloc(3 * sizeof(int));    // list는 메모리 덩어리의 주소를 담고 있음
    if (list == NULL)   // 메모리가 부족해서 NULL이 반환되었을 때
    {
        return 1;
    }

    list[0] = 1;        // 주소는 4바이트씩 차이남
    list[1] = 2;
    list[2] = 3;

    int *tmp = realloc(list, 4 * sizeof(int));
    if (tmp == NULL)
    {
        return 1;
    }

    list = tmp;

    tmp[3] = 4;

    for (int i = 0; i < 4; i++)
    {
        printf("%i\n", list[i]);
    }

    free(list);     // 메모리 누수 방지
}

/*
1
2
3
4
*/

 

3. 연결 리스트: 도입

• 연결 리스트의 정의를 설명할 수 있다.

연결 리스트 (Linked Lists)

배열

• 물리적으로 연속된 메모리상에 데이터가 저장되어 있다.
• 쉽게 인덱싱할 수 있고 대괄호를 통해 일정한 시간에 접근(random access)할 수 있어 탐색이 매우 빠르다. 이진탐색 이용 가능
• 그러나 배열의 크기를 변경할 때 메모리의 다른 공간에 값들을 복사하는 과정이 이루어진다.
• 많은 양의 데이터를 저장하려면 메모리상에 연속된 여유 공간이 존재해야 한다.

연결 리스트

• 배열의 메모리 문제를 해결해보자
• 메모리 덩어리에 자신의 값과 배열의 다음 요소를 가리키는 포인터(next)를 저장
• 배열의 끝에서는 NULL

typedef struct node     // 구조체 안에서 node를 사용하기 위해 미리 말해줌
{
    int number;             // 각 노드가 가지는 값
    struct node *next;      // 다음 노드를 가리키는 포인터
}
node;

 

4. 연결 리스트: 코딩

• 연결 리스트를 구현하고 사용할 수 있다.

연결 리스트 구현

#include <stdio.h>
#include <stdlib.h>     // malloc, free

// Represents a node
// 연결 리스트의 기본 단위 node 구조체 정의
typedef struct node
{
    int number; 
    struct node *next;
}
node;

int main(void)
{
    // List of size 0
    // list라는 이름의 node 포인터 정의. 연결 리스트의 가장 첫 번째 node를 가리킴. 
    // 현재 아무 것도 가리키고 있지 않으므로 NULL 로 초기화.
    node *list = NULL;

    // 새로운 node를 위해 메모리를 할당하고 포인터 *n으로 가리킴(임시로 쓰는 변수).
    node *n = malloc(sizeof(node));
    if (n == NULL)      // 메모리가 제대로 할당되었는지 검사.
    {
        return 1;
    }
    // NULL이 아닐 경우 *n의 number와 next 값을 저장하는 것으로도 쓸 수 있음.


    // n의 number 필드에 1의 값을 저장.
    // n이 가리키는 node의 number 필드에 접근해서 1로 만들어준다.
    n->number = 1;      // “(*n).numer”와 동일한 의미

    // n 다음에 정의된 node가 없으므로 NULL로 초기화.
    n->next = NULL;

    // 이제 첫번째 node를 정의했기 떄문에 list 포인터를 n 포인터로 바꿈.
    list = n;

    // list에 다른 node를 더 연결하기 위해 n에 새로운 메모리를 다시 할당.
    n = malloc(sizeof(node));
    if (n == NULL)
    {
        return 1;
    }

    // n의 number와 next의 값을 각각 저장.
    n->number = 2;
    n->next = NULL;

    // list가 가리키는 것은 첫 번째 node 
    //이 node의 다음 node를 n 포인터로 지정.
    list->next = n; // list의 next 필드에 포인터 n 저장

    // 다시 한 번 n 포인터에 새로운 메모리를 할당하고 number과 next의 값을 저장.
    n = malloc(sizeof(node));
    if (n == NULL)
    {
        return 1;
    }

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

    // 현재 list는 첫번째 node를 가리키고, 이는 두번째 node와 연결되어 있다. 
    // 따라서 세 번째 node를 더 연결하기 위해 첫 번째 node (list)의 
    // 다음 node(list->next)의 다음 node(list->next->next)를 n 포인터로 지정.
    list->next->next = n;       // 보통은 루프를 이용

    // 이제 list에 연결된 node를 처음부터 방문하면서 각 number 값을 출력. 
    // 마지막 node의 next에는 NULL이 저장. 이것이 for 루프의 종료 조건.
    for (node *tmp = list; tmp != NULL; tmp = tmp->next)
    {
        printf("%i\n", tmp->number);
    }

    // Free list
    // 메모리를 해제해주기 위해 list에 연결된 node들을 처음부터 방문하면서 free 해 줌.
    while (list != NULL)        
    {
        node *tmp = list->next;
        free(list);
        list = tmp;
    }
}

// 내가 무엇을 가리키고 있든 next 필드를 가리켜라

node *tmp = list;
while (tmp->next != NULL)   // NULL이 아니라면
{
    tmp = tmp->next;        // 계속해서 자기 자신을 업데이트해서 그 자신이 가리키고 있는 것을 가리키도록 함
}
// 

구현 시 주의점

• A, B 노드 사이에 C 노드를 추가한다고 할 때, 새로 추가되는 노드(C)에 뒤에 이어질 노드(B)의 주소값을 저장해 둔 뒤에(이때 A와 C 모두가 B를 가리킨다) 원래 그 노드(B)를 가리키고 있던 노드(A)에 저장된 다음 노드 주소를 바꿔주어야(B 주소를 C 주소로) 한다.
• 노드 C에 값을 넣은 뒤에 다음 노드(B)에 대한 정보를 넣지 않고 바로 A에 저장된 다음 노드 주소를 바꿔버리면 노드 B 이후의 노드들은 버려지게 된다.(메모리 누수(memory leak) 발생)
  • 이 경우 이 값들이 어디에 있는지 기억하고 있는 변수가 없기 때문에 이 메모리에 다시 접근할 수 없다.

 

5. 연결 리스트: 시연

• 연결 리스트와 배열의 장단점을 설명할 수 있다.
• 연결 리스트, 배열

연결 리스트의 장단점

장점

• 배열처럼 데이터를 추가하기 위해 크기를 조절하고 기존의 값을 모두 옮기지 않아도 된다.
• 원래 있었던 것을 움직이지 않고도 리스트를 늘릴 수 있음.

단점

• 컴퓨터는 한 번에 한 개의 메모리만 볼 수 있다.
  • 특정 값을 찾으려면 포인터를 따라가면서 모든 메모리를 하나씩 열어봐야 한다.
  • 순서를 맞춰서 중간에 삽입할 곳을 찾을 때에도 마찬가지.
• 임의 접근(random access)을 할 수 없다. -> 이진 탐색을 효과적으로 할 수 없다.

연결 리스트를 이용한 작업의 시간복잡도

• 탐색: O(n)
• 삽입: O(n) - 배열의 경우는 이진 탐색을 이용하면 O(logn)

 

6. 연결 리스트: 트리

• 트리의 구조를 설명하고 활용하는 코드를 작성할 수 있다.
• 트리, 루트

이진 탐색 트리

• 트리에서 노드들의 연결은 2차원적.
• 트리의 노드들이 모두 최대 두 개의 자식 노드가 있는 '이진 트리'
• 탐색을 위해 데이터의 순서에 신경 쓴 '탐색 트리'
• 트리에 있는 모든 노드에서, 왼쪽 자식 노드는 그 노드보다 더 작고 오른쪽 자식 노드는 더 큼.(재귀적 정의)
• 연결 리스트처럼 역동성을 가지면서 이진 탐색도 가능한 자료 구조
• 트리를 저장하기 위해 하나의 포인터가 루트를 가리켜야.
• 루트: 트리가 시작되는 노드. 부모가 없는 노드.

//이진 검색 트리의 노드 구조체
typedef struct node
{
    int number;
    struct node *left;      // 왼쪽 자식 노드
    struct node *right;     // 오른쪽 자식 노드
} node;

// 이진 검색 함수 (*tree는 이진 검색 트리를 가리키는 포인터)
bool search(node *tree)
{
    // 트리가 비어있는 경우 ‘false’를 반환하고 함수 종료
    if (tree == NULL)       // 재귀의 종료 조건
    {
        return false;
    }
    // 현재 노드의 값이 50보다 크면 왼쪽 노드 검색
    else if (50 < tree->number)
    {
        return search(tree->left);  // 왼쪽 서브 트리
    }
    // 현재 노드의 값이 50보다 작으면 오른쪽 노드 검색
    else if (50 > tree->number)
    {
        return search(tree->right); // 오른쪽 서브 트리
    }
    // 위 모든 조건이 만족하지 않으면 노드의 값이 50이므로 ‘true’ 반환
    else {
        return true;
    }
}

• 탐색의 시간복잡도는 O(logn)
• 재귀에 가장 적합한 방법
• 값을 삽입 또는 삭제할 경우 트리의 균형을 유지해줄 수 있는 알고리즘이라면 logn의 실행 시간.

 

7. 해시 테이블

• 해시 테이블의 원리와 구조를 설명할 수 있다.
• 해시 테이블, 해시 함수

해시 테이블

• 연결 리스트의 배열
• 해시 함수라는 맞춤형 함수를 통해 어떤 칸에 담기는지 결정
• 같은 칸에 담기는 값들(충돌 발생)은 그 칸에서 새롭게 정의되는 연결 리스트로 이어짐

 

• 해시 함수가 이상적이라면 해시 테이블의 각 칸에는 단 하나의 값들만 담겨 검색 시간은 O(1)이 된다.
• 최악의 경우에는 단 하나의 칸에 모든 값들이 담겨 O(n)이 된다.
• 일반적으로는 최대한 충돌이 일어나지 않도록 하는 해시 함수를 만들어서 거의 O(1)에 가깝다.

 

8. 트라이

• 트라이의 원리와 구조를 설명할 수 있다.

트라이

• 각 노드가 배열로 구성되어 있는 트리 형태의 자료 구조

예시

• 영어 알파벳으로 이루어진 문자열 값을 저장한다고 하면 이 노드는 a부터 z까지의 값을 갖는 배열
• 배열의 각 요소는 다음 층의 노드(a-z 배열)를 가리킴
• 영어 이름을 트라이에 저장한다고 했을 때, 문자 순서대로 따라가면서 노드들이 이어진다.
  • 그런 트라이에서 값을 검색하는 데 걸리는 시간은 문자열의 길이에 의해 한정.
  • 영어 이름의 길이를 n이라 할 때, 검색 시간은 O(n)이지만, 대부분의 이름의 길이는 그리 크지 않은 상수값이므로 O(1)이나 마찬가지.

 

9. 스택, 큐, 딕셔너리

• 스택, 큐, 딕셔너리의 원리와 구조를 설명할 수 있다.

큐 (Queue)

FIFO. 선입선출의 특징을 가진 자료구조

큐의 연산

• enqueue
• dequeue

스택 (Stack)

LIFO. 후입선출의 특징을 가진 자료구조

스택의 연산

• push
• pop

딕셔너리 (Dictionary)

키와 값의 쌍으로 이루어진 자료구조

• 일종의 해시 테이블
• 키를 어떻게 정의할 것인지가 중요하다.