모두를 위한 컴퓨터 과학(하버드CS50 2019)(4)

 

문제 코드 분석

 

#include <stdlib.h>

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

    x = malloc(sizeof(int));

    *x = 42;
    *y = 13;  // ❗ 버그 발생
}

 

1. 무엇이 문제인가?

• int *x; int *y;는 포인터 변수만 선언했을 뿐 아무 메모리도 가리키지 않습니다.
• x = malloc(sizeof(int));를 해서(*x에 값을 넣는 건 이제 가능) x는 새로운 메모리 공간을 가리킵니다.
• 하지만 y는 여전히 어디를 가리키는지 모르는 “쓰레기 주소” 를 가지고 있습니다.

x → [메모리 공간: OK]
y → [쓰레기 값: 위험]

• 그런데 *y = 13;로Segmentation Fault (메모리 접근 오류) 가 터질 수 있습니다.
• y가 가리키는(아무거나) 주소에 13을 저장하려 하니까

 

2. 수정된 올바른 코드

 

#include <stdlib.h>

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

    x = malloc(sizeof(int));

    *x = 42;
    y = x;  // y가 x가 가리키는 메모리를 같이 가리킴
    *y = 13;  // OK

    free(x);
}

• 여기서는 y = x;로 y가 x와 같은 메모리 주소를 가리키게 했습니다.
• *y = 13;를 하면 결국 x가 가리키는 메모리도 13으로 바뀝니다.

 

3. 메모리 그림으로 이해

Heap 메모리: [ 13 ]
x → [ 13 ]
y → [ 13 ]

• x와 y 모두 같은 곳(동일한 메모리 주소)을 가리킵니다.
• 하나를 수정하면 둘 다 수정된 것처럼 보입니다.

 

4. 추가 포인트

 

int x; int y; 와 int *x; int *y;의 차이

int x;	정수형 값 4바이트 공간 확보
int *x;	정수를 가리킬 포인터 공간 확보 (주소 저장)

• int x, y;는 → 실제 정수 값을 저장할 메모리 공간을 만들었다는 뜻
• int *x, *y;는 → 정수형 변수를 가리킬 수 있는 포인터만 만들었다는 뜻

포인터를 만들었으면, 반드시 가리킬 대상을 지정해줘야 한다!

 

malloc 이후 free

• malloc으로 얻은 메모리는 프로그램 끝나기 전에 반드시 free로 해제해야 합니다.
• 안 그러면 메모리 누수(memory leak)가 발생합니다.

free(x); // 메모리 반납

 

---

Use-After-Free 버그란?

 

Use-After-Free (UAF) 는 메모리를 free()로 해제한 뒤에도 그 메모리에 접근하려는 버그를 말합니다.

free(p);를 했는데 그 이후에 *p, p[i], p->member 등을 사용하면 심각한 오류(세그멘테이션 폴트)나 보안 취약점이 발생합니다.

“이미 반납한 메모리를 다시 쓰려는 것” → use-after-free

Use-After-Free 버그 예시

 

잘못된 코드 (Use-After-Free 발생)

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

int main(void)
{
    int *x = malloc(sizeof(int));
    *x = 42;

    free(x);    // ✅ 메모리 해제

    *x = 13;    // ❌ 해제된 메모리에 접근 (use-after-free)

    printf("%i\n", *x); // ❌ undefined behavior

    return 0;
}

실행 결과

프로그램이 크래시(세그폴트) 할 수도 있고, 가끔은 “운 좋게” 정상 출력될 수도 있습니다. → 하지만 이건 운일 뿐이고, 코드가 잘못된 것입니다.

 

3. 왜 위험한가?

• 메모리 해제 후에는 OS가 그 메모리 블록을 다른 용도로 재사용할 수 있습니다.
• 이미 다른 프로그램이나 다른 데이터가 그 공간을 사용할 수도 있는데 거기에 다시 쓰거나 읽으면 → 데이터 손상, 보안 취약점 발생합니다.

 

4. 포인터를 안전하게 관리하는 좋은 습관

 

(1) 포인터 선언 직후 초기화

int *p = NULL;

• 쓰레기 값이 아닌, 명확한 NULL로 초기화합니다.
• 포인터가 가리키는 대상이 없음을 확실히 합니다.

 

(2) malloc 후 항상 NULL 체크

int *p = malloc(sizeof(int));
if (p == NULL)
{
    // 메모리 할당 실패 처리
}

• malloc이 실패할 수도 있으니까, 무조건 NULL 체크를 습관화합니다.

 

(3) free 후 포인터를 NULL로 덮어쓰기

free(p);
p = NULL;

• free 한 후에도 포인터가 이전 주소를 가리키고 있으면 위험합니다.
• 그래서 free 한 직후 NULL로 초기화하면, 잘못 접근했을 때 바로 잡을 수 있습니다.

 

올바른 안전한 코드 예시

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

int main(void)
{
    int *x = malloc(sizeof(int));
    if (x == NULL)
    {
        return 1;
    }

    *x = 42;
    free(x);
    x = NULL; // ✅ free 후 NULL로 설정

    if (x != NULL)
    {
        *x = 13; // ❌ 이 블록은 실행되지 않음
    }

    return 0;
}

• free 하고 NULL로 덮으면,
• 이후 코드에서 실수로 사용하려고 해도 접근이 차단됩니다.

---

 

 

1. 배열의 한계

• C의 배열(array) 은 메모리상에 연속된 공간을 요구합니다.

int list[3];  // [ ] [ ] [ ] (메모리 연속)

• 이 배열은 처음 크기가 고정됩니다.
• 공간이 부족해져도, 배열 크기를 늘릴 수 없습니다.
• 새 공간이 필요하면 → 새 배열을 만들고 → 복사해야 합니다.

 

2. 고정 배열 예시

#include <stdio.h>

int main(void)
{
    int list[3];

    list[0] = 1;
    list[1] = 2;
    list[2] = 3;

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

• 배열 list[3]은 3칸만 존재합니다.
• 4번째 값을 넣을 공간은 없습니다.

배열은 컴파일 시점에 크기가 고정되어 버린다.

 

3. malloc과 tmp로 복사하는 방법

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

int main(void)
{
    int *list = malloc(3 * sizeof(int)); // 12 bytes 할당
    if (list == NULL)
    {
        return 1;
    }

    list[0] = 1;
    list[1] = 2;
    list[2] = 3;

    int *tmp = malloc(4 * sizeof(int));
    if (tmp == NULL)
    {
        free(list); // 기존 메모리도 반납해야 함
        return 1;
    }

    for (int i = 0; i < 3; i++)
    {
        tmp[i] = list[i];
    }
    tmp[3] = 4;

    free(list); // 먼저 기존 list 메모리 해제

    list = tmp; // list가 tmp 메모리를 가리키게 함
    // 이제 tmp는 더 이상 free하지 않는다!
    // tmp는 list로 이름만 바뀐 것!

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

    free(list); // 마지막에 list 메모리 해제
}

• malloc(3 * sizeof(int))으로 3칸짜리 배열 생성
• tmp를 추가로 만들어 4칸짜리 배열 생성
• for 루프로 값 복사
• 메모리를 해제하고 새 배열을 연결

 

4. realloc으로 확장하는 방법

#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;

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

    list = tmp;
    list[3] = 4; // 추가한 요소 초기화

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

    free(list);
}

• realloc(list, 4 * sizeof(int))
  • 기존 list의 메모리를 “가능하면 확장”합니다.
  • 확장할 수 없으면 새로운 공간을 만들고 복사해줍니다.
• 복사 과정이 자동이라 for문 필요 없음!

realloc은 공간을 재할당할 수도 있고, 안 할 수도 있기 때문에 항상 반환값을 tmp에 저장해서 NULL을 체크해야 합니다.

 

메모리 복사에는 O(n) 시간

• 배열 복사(for문 또는 realloc 내부)는 배열의 모든 요소를 복사하기 때문에 시간 복잡도는 O(n) 입니다.
• 즉, 배열 크기가 커질수록 복사 시간도 선형으로 증가합니다.

 

정렬된 배열 탐색은 O(log n)

 

• 만약 배열이 정렬되어 있다면, 이진 탐색(binary search) 를 사용할 수 있습니다.
• 이진 탐색은 한번에 절반씩 줄여나가기 때문에 → O(log n) 시간에 원하는 값을 찾을 수 있습니다.

 

---

 

자료 구조(Data Structure)란

• 프로그램에서 정보(데이터)를 저장하고 조직화하는 방법입니다.
• 배열, 연결 리스트, 트리, 해시 테이블 같은 것이 대표적입니다.
• 자료 구조는 정보를 “어떤 방식”으로 저장할지를 정하기 때문에, 어떤 연산을 빠르게 할 수 있는지도 결정합니다.

 

---

• struct는 여러 데이터를 하나의 묶음(레코드)으로 만드는 키워드입니다.

struct student {
    string name;
    int age;
};

• . 연산자를 사용해서 구조체 안의 속성값에 접근합니다.

struct student s;
s.age = 20;

• * 연산자는 포인터를 다룰 때 사용합니다.
  • 메모리 주소로부터 값에 접근(역참조) 하는 데 필요합니다.

---

• 배열은 빠르지만 고정 크기라 realloc 없이 크기를 늘릴 수 없습니다.
• 연결 리스트는 메모리 어디에나 데이터를 저장하고 링크(포인터) 로 이어붙입니다.

연결 리스트란?

 

• 연결 리스트(Linked List) 는 노드(node) 들이 서로 포인터로 연결된 자료구조입니다.
• 각 노드는 하나의 데이터(number 등)와 다음 노드를 가리키는 포인터(next) 를 가지고 있습니다.

[1 | next] → [2 | next] → [3 | NULL]

• 마지막 노드의 next 포인터는 NULL을 가리켜서 끝을 표시합니다.

구조체 노드 정의

 

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

왜 이렇게 해야 할까?

1. struct node 내부에서는그래서 구조체 안에서는 struct node *next;라고 써야 합니다.
2. 아직 node라는 이름이 완성되지 않았습니다.
3. typedef struct node { … } node;**“앞으로 struct node 대신 그냥 node라고 간단히 쓰자”**는 의미입니다.
4. 이걸 추가로 쓰는 이유는,

만약 typedef를 안 하면?

struct node *head;

• 매번 struct node라고 풀네임을 써야 해서 번거롭습니다.

typedef를 하면?

node *head;

• 더 깔끔하고 간결해집니다.

typedef는 긴 타입 이름을 간단하게 별명(alias) 으로 만들어주는 것입니다.

연결 리스트를 메모리 그림으로 보면

메모리 (heap):

[1 | next] --> [2 | next] --> [3 | NULL]

1번 노드의 next 포인터 → 2번 노드를 가리킴
2번 노드의 next 포인터 → 3번 노드를 가리킴
3번 노드의 next 포인터 → NULL

• 각 노드는 따로따로 메모리 어딘가에 존재합니다.
• 포인터로 서로를 연결합니다.

---

연결리스트 코드

#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 = 2;
        n->next = NULL;
    }
    else
    {
        return 1; // 메모리 할당 실패
    }

    // 리스트에 추가
    if (list == NULL)
    {
        // 리스트가 비어있으면 바로 추가
        list = n;
    }
    else
    {
        // 리스트가 비어있지 않으면 (현재 구조에서는 필요 없음, 참고용)
        node *tmp = list;
        while (tmp->next != NULL)
        {
            tmp = tmp->next;
        }
        tmp->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;
    }
}

list = NULL	연결 리스트 비어있음 표시
malloc + NULL 체크	메모리 확보
n->number, n->next 설정	노드 값 설정
list = n	리스트에 새 노드 추가 (맨 앞)
리스트 출력	값 순회 출력
메모리 해제	메모리 누수 방지

(1) 리스트 초기화

node *list = NULL;

• 리스트는 처음에 아무것도 없습니다.
• list 포인터가 NULL이라는 것은 “아직 연결 리스트가 비어있다”는 것을 명시적으로 표현하는 것입니다.

(2) 새 노드 동적 메모리 할당

node *n = malloc(sizeof(node));

• malloc을 이용해 메모리에 node 하나 크기만큼 공간을 확보합니다.
• n은 이 새 공간을 가리킵니다.
• 할당이 성공했는지 꼭 if (n != NULL)로 체크합니다.

 

(3) 새 노드 초기화

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

• 새 노드에 2를 저장합니다.
• 그리고 이 노드는 아직 다른 노드를 가리키지 않기 때문에 next를 NULL로 설정합니다.

 

(4) 리스트 순회 준비

node *tmp = list;

• 리스트를 탐색하기 위해 임시 포인터 tmp를 사용합니다.
• tmp는 처음에 list를 가리키도록 합니다.

 

(5) 주의사항: tmp->next를 접근

while (tmp->next != NULL)
{
    tmp = tmp->next;
}

• 문제 발생 가능 지점: list가 아직 NULL인데 tmp->next를 접근하면 → 세그멘테이션 폴트(메모리 오류) 발생
• 이유: NULL은 아무 메모리도 가리키지 않는데 거기에 .next로 접근하려고 했기 때문입니다.

(6) 리스트에 새 노드 추가

n->next = list;
list = n;

• 새로운 노드 n을 리스트의 맨 앞(head) 에 추가합니다.
• n->next가 기존의 list를 가리키게 하고,
• list가 새 노드 n을 가리키게 합니다.

결과:

list → [2 | NULL]

 

전체 흐름을 시각화

 

처음

list → NULL

n 생성

n → [2 | NULL]

추가 이후

list → [2 | NULL]

• list는 새로 만든 노드 n을 가리킵니다.
• n은 next가 NULL이라 리스트 끝입니다.

비유하자면, list는 기차의 기관차입니다. n은 새로운 객차입니다. 처음에는 기관차 하나만 있는 상태가 되는 것입니다.

 

C언어 연결 리스트는 포인터를 잘 다루는 연습이다.

메모리 할당(malloc), 포인터 연결, 메모리 해제(free) 이 3가지를 정확히 관리해야 한다.

---

최종 연결 리스트 구현

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

// node 구조체 정의
typedef struct node
{
    int number;
    struct node *next;
}
node;

int main(void)
{
    // 1. 아무것도 가리키지 않는 list 포인터 생성 (⓪)
    node *list = NULL;

    // 2. (malloc으로) 새 노드 생성, 숫자 할당 (❷)
    node *n2 = malloc(sizeof(node));
    if (n2 == NULL)
    {
        return 1;
    }
    n2->number = 2;
    n2->next = NULL;

    // 3. list 포인터로 2번에서 생성된 노드❷ 가리키기
    list = n2;

    // 4. 새 노드 생성, 숫자 할당 (❹)
    node *n4 = malloc(sizeof(node));
    if (n4 == NULL)
    {
        free(list);
        return 1;
    }
    n4->number = 4;
    n4->next = NULL;

    // 5. 임시변수(tmp) 활용하여 list 순회하여 NULL 탐색
    node *tmp = list;
    while (tmp->next != NULL)
    {
        tmp = tmp->next;
    }

    // 6. 2번에서 생성된 노드❷ 포인터로 4번에서 생성된 노드❹ 가리키기
    tmp->next = n4;

    // 7. 새 노드 생성, 숫자 할당 (❺)
    node *n5 = malloc(sizeof(node));
    if (n5 == NULL)
    {
        // 앞서 malloc한 메모리 정리
        while (list != NULL)
        {
            node *next = list->next;
            free(list);
            list = next;
        }
        return 1;
    }
    n5->number = 5;
    n5->next = NULL;

    // 8. 임시변수(tmp) 활용하여 list 순회하여 NULL 탐색
    tmp = list;
    while (tmp->next != NULL)
    {
        tmp = tmp->next;
    }

    // 9. 4번에서 생성된 노드❹ 포인터로 7번에서 생성된 노드❺ 가리키기
    tmp->next = n5;

    // (2번에서 생성된 노드❷ 전에 ❶추가하기)

    // 10. 새 노드 생성, 숫자 할당 (❶)
    node *n1 = malloc(sizeof(node));
    if (n1 == NULL)
    {
        while (list != NULL)
        {
            node *next = list->next;
            free(list);
            list = next;
        }
        return 1;
    }
    n1->number = 1;

    // 11. 10번에서 생성된 포인터❶로 list가 가리키는 노드❷ 가리키기
    n1->next = list;

    // 12. list 포인터를 10번에서 생성된 노드❶로 바꿔주기
    list = n1;

    // (2번에서 생성된 노드❷와 4번에서 생성된 노드❹ 사이에 ❸ 추가)

    // 13. 새 노드 생성, 숫자 할당 (❸)
    node *n3 = malloc(sizeof(node));
    if (n3 == NULL)
    {
        while (list != NULL)
        {
            node *next = list->next;
            free(list);
            list = next;
        }
        return 1;
    }
    n3->number = 3;

    // 14. 13번에서 생성된 노드❸ 포인터로 4번에서 생성된 노드❹ 가리키기
    n3->next = n4;

    // 15. 2번에서 생성된 노드❷ 포인터로 13번에서 생성된 노드❸ 가리키기
    tmp = list;
    while (tmp != NULL && tmp->number != 2)
    {
        tmp = tmp->next;
    }
    if (tmp != NULL)
    {
        tmp->next = n3;
    }

    // 리스트 출력
    printf("Linked list contents:\n");
    for (node *ptr = list; ptr != NULL; ptr = ptr->next)
    {
        printf("%i -> ", ptr->number);
    }
    printf("NULL\n");

    // 메모리 해제
    while (list != NULL)
    {
        node *next = list->next;
        free(list);
        list = next;
    }
}

메모리 구조 그림

list → [1 | ] → [2 | ] → [3 | ] → [4 | ] → [5 | NULL]

순서대로 정확히 ❶ → ❷ → ❸ → ❹ → ❺ 로 이어집니다.

• 탐색 (찾기) = O(n)
• 삽입 (노드 추가) = O(n) (순회해서 NULL 찾아야 하므로)

연결 리스트는 “포인터를 따라가야만” 값을 찾을 수 있습니다.

→ 배열처럼 “임의 접근(random access)“이 불가능합니다.

→ 따라서 이진 탐색도 불가능합니다.

연결 리스트는 탐색이나 삽입이 O(n)이지만, 메모리를 유연하게 다루고 크기 제한 없이 노드를 추가할 수 있는 장점이 있다.

---

1. 연결 리스트(Linked List) → 트리(Tree)로 확장

 

연결 리스트는 한 노드가 한 방향(next) 으로만 이어졌습니다.

트리는 한 노드가 두 방향(left, right) 으로 뻗어나갑니다.

포인터를 하나 더 추가하면 리스트가 트리로 발전하는 것입니다.

2. 이진 탐색 트리(Binary Search Tree, BST) 구조

 

노드 정의

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

• left : 자기보다 작은 값을 가진 노드를 가리킴
• right : 자기보다 큰 값을 가진 노드를 가리킴

 

3. 트리 구조 예시 (숫자: 4, 2, 6, 1, 3, 5, 7)

그림으로 표현하면:

      4
    /   \
   2     6
  / \   / \
 1   3 5   7

• 왼쪽으로 갈수록 작고, 오른쪽으로 갈수록 큽니다.

 

4. 50을 찾는 트리 탐색 알고리즘 

bool search(node *tree)
{
    if (tree == NULL)
    {
        return false; // 못 찾으면 false
    }
    else if (50 < tree->number)
    {
        return search(tree->left); // 작으면 왼쪽으로
    }
    else if (50 > tree->number)
    {
        return search(tree->right); // 크면 오른쪽으로
    }
    else
    {
        return true; // 찾았다!
    }
}

• 현재 노드가 비어있으면(false)
• 찾는 값이 현재 노드보다 작으면 왼쪽으로, 크면 오른쪽으로 이동합니다.
• 값이 같으면 찾은 것입니다.

 

5. 시간 복잡도

 

이진 탐색 트리(Binary Search Tree, BST)를 이용하면

• 트리의 높이가 h라고 할 때, 탐색 시간은 O(h) 입니다.

완전한 트리 (balanced tree) 의 경우,

• h ≈ log₂(n) → 따라서 탐색 시간은 O(log n) 이 됩니다!

즉,

탐색: O(log n)

삽입: O(log n)

삭제: O(log n)

(단, 트리가 “균형”이 잘 맞아야 합니다. skewed tree(삐뚤어진 트리)가 되면 O(n)까지 떨어질 수 있음)

 

6. 트리 구조 메모리 시각화

 

각 노드는 메모리에 따로 존재하고, 포인터로 연결됩니다:

[4|left|right]
   ↙        ↘
[2|left|right] [6|left|right]
 ↙   ↘         ↙   ↘
[1]  [3]     [5]   [7]

• 리스트는 일직선인데,
• 트리는 포인터가 위아래로 뻗어나갑니다.

 

 

 

 

---

해시 테이블이란?

해시 테이블은 “키(key)를 빠르게 찾아갈 수 있게 만든 자료구조” 입니다.

기본적으로 “배열(Array)” + “연결 리스트(Linked List)”의 조합입니다.

 

구조

1) 배열 (Buckets)

• 0번부터 25번까지, 26개의 배열 칸(바구니, buckets) 을 준비합니다.
• 각각의 바구니는 특정 키(key)를 저장할 수 있도록 준비됩니다.

2) 연결 리스트 (Chaining)

• 만약 같은 바구니에 여러 개의 데이터가 들어오면 연결 리스트로 이어붙여 저장합니다.

 

동작 흐름

1) 해시 함수(Hash Function)

• 키(예: 이름)를 입력받아 어떤 바구니(index) 에 저장할지를 결정합니다.
• 예를 들어 이름의 첫 글자 AZ를 숫자로 변환해서 025 중 하나의 인덱스를 반환할 수 있습니다.

2) 삽입(Insert)

• 해시 함수 결과에 따라 바구니를 선택합니다.
• 이미 다른 데이터가 있다면 연결 리스트로 이어붙입니다.

3) 검색(Search)

• 해시 함수를 이용해 빠르게 “해당 바구니”를 찾아갑니다.
• 연결 리스트를 따라서 필요한 데이터를 찾습니다.

 

해시 충돌 (Collision)

만약 다른 키들이 같은 바구니로 가게 되면 충돌(collision)이 발생합니다.

충돌 해결 방법: 체이닝(Chaining)

• 같은 바구니에 여러 값을 연결 리스트 형태로 이어붙입니다.
• 즉, 하나의 인덱스에 여러 개의 노드가 연결됩니다.

 

예시: 이름 저장

 

26개 바구니 준비 (0 ~ 25)

인덱스 | 내용

0	A…
1	B…
2	C…
…	…
25	Z…

• 이름 “Zoo” → ‘Z’ → 25번 바구니로
• 이름 “Alice” → ‘A’ → 0번 바구니로

만약 모두 ‘H’로 시작한다면?

• “Harry”, “Hank”, “Helen”
• 전부 7번 바구니에 몰립니다 (H: 7번째).
• 이때는 연결 리스트로 순서대로 이어붙입니다.

 

바구니를 늘려서 충돌 줄이기

 

• 처음에는 ‘H’만 구분했지만,
• 좀 더 섬세하게 나누려면 “Ha”, “Hb”, “Hc” 등으로 세분화할 수 있습니다.
• 더 세분화하면 “Haa”, “Hab”, “Hac”…처럼도 가능합니다.

이렇게 하면 충돌이 줄어들고 O(1)에 가까워집니다.

하지만 배열 크기가 폭발적으로 커지기 때문에 메모리를 많이 소모합니다.

 

공간과 시간의 균형

 

공간(메모리)시간(속도)

바구니 수가 많을수록	검색이 빠름 (O(1))
바구니 수가 적을수록	충돌 많아짐 → 검색 느려짐 (O(n))

현실에서는 적절히 타협해서 사용합니다.

실제 해시 테이블은 평균적으로 O(1) 에 가깝지만, 최악의 경우 O(n) 시간이 걸릴 수 있습니다.

---

 

 

Trie(트라이)란 무엇인가?

Trie는 “Retrieval (검색)”의 줄임말입니다.

트라이는 문자열(string) 검색을 빠르게 하기 위해 만들어진 특별한 자료구조입니다.

 

Trie 구조

트라이는 기본적으로 노드(node) 들로 구성되어 있으며, 각 노드가 ‘A’~‘Z’(26개) 배열을 가집니다.

각 노드는 다음 글자로 이동하는 포인터 배열을 가지고 있고 끝나는 단어인지 표시하는 flag (예: bool is_word)를 가질 수도 있습니다.

 

트라이의 검색 과정

 

예를 들어 APPLE이라는 단어를 트라이에 저장한다면:

1. 루트 노드에서 ‘A’로 이동
2. ‘A’ 노드에서 ‘P’로 이동
3. ‘P’ 노드에서 또 ‘P’로 이동
4. ‘P’ 노드에서 ‘L’로 이동
5. ‘L’ 노드에서 ‘E’로 이동
6. ‘E’ 노드에 “이곳이 하나의 완성된 단어임”을 표시

 

트라이의 시간 복잡도

트라이에서 단어를 찾는 시간은 문자열의 길이에 비례합니다.

항목설명

검색 시간	O(단어 길이)
삽입 시간	O(단어 길이)
삭제 시간	O(단어 길이)

• 트라이의 성능은 문자열 길이에만 비례합니다.
• 전체 데이터 개수에 따라 속도가 느려지지 않습니다.

→ 상수에 가까운 시간이라고 표현할 수 있습니다!

 

트라이의 단점

 

시간은 빠르지만, 메모리를 엄청나게 사용합니다.

노드마다	26개의 포인터(또는 NULL) 필요
많은 단어를 저장할 때	대부분 포인터는 NULL인데, 공간은 낭비됨

Trie 노드 기본 구조

typedef struct node
{
    bool is_word;      // 이 노드가 하나의 단어 끝인지 표시
    struct node *children[26]; // A~Z를 위한 포인터 배열
}
node;

단, 모든 경로(문자) 에 대해 길을 준비해놔야 해서 메모리가 많이 듭니다.

---

추상화된 자료형이란? (ADT: Abstract Data Type)

ADT(추상 자료형) 이란

• 데이터를 어떻게 “사용”할지에 대한 규약입니다.
• 내부가 어떻게 구현되었는지는 숨기고 “어떤 기능을 제공하는지”에만 집중하는 개념입니다.

 

큐 (Queue)

 

현실 세계에서는 가게 앞에 선 줄을 생각하면 됩니다.

큐는 First In, First Out (FIFO) 규칙을 따릅니다.

enqueue	줄을 맨 뒤에 추가 (줄 서기)
dequeue	줄의 맨 앞에서 제거 (줄 빠지기)

프린터 대기열, 서버 요청 처리 등 → “순서대로 처리해야 하는 상황”에 사용됩니다.

큐의 시간 복잡도

enqueue	O(1)
dequeue	O(1)

• (잘 구현하면 항상 상수 시간에 작동합니다.)

---

스택 (Stack)

현실 세계에서는 쟁반 쌓기를 떠올리면 됩니다.

스택은 Last In, First Out (LIFO) 규칙을 따릅니다.

push	맨 위에 쟁반 올리기
pop	맨 위 쟁반 꺼내기

웹 브라우저 방문 기록, 이메일 관리 등 → “최근에 들어온 것부터 처리”할 때 사용됩니다.

 

스택의 시간 복잡도

push	O(1)
pop	O(1)

• 역시 잘 구현하면 항상 빠르게 작동합니다.

---

딕셔너리 (Dictionary)

 

현실 세계에서는 단어(키)와 뜻(값)을 저장한 사전(Dictionary) 을 떠올리면 됩니다.

딕셔너리는 키(key) 와 값(value) 쌍을 저장합니다.

삽입	(단어, 뜻) 저장
검색	단어로 뜻 찾기
삭제	특정 단어 삭제

파이썬의 dict, 자바스크립트의 object, C++의 unordered_map 등이 대표적인 딕셔너리 구현체입니다.

내부적으로는 대부분 해시 테이블을 기반으로 구현됩니다.

 

딕셔너리의 시간 복잡도

삽입/검색/삭제 (평균)	O(1)
삽입/검색/삭제 (최악)	O(n)

• 평균적으로는 매우 빠르지만, 충돌이 심하게 일어나면 최악의 경우 전체를 검색해야 해서 O(n)이 될 수 있습니다.