[cs50 모두를 위한 컴퓨터 과학] 자료구조(Data Structure)

📝 연결 리스트(Linked list)

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

하지만 각 값이 메모리상의 여러 군데 나뉘어져 있다고 하더라도 바로 다음 값의 메모리 주소만 기억하고 있다면 여전히 값을 연이어서 읽어들일 수 있다. ⇒ 이를 ‘연결 리스트’라고 한다.

 

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

3은 다음 값이 없기 때문에 NULL(\n, 즉 0)을 다음 값의 주소로 저장한다.

 

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

- 연결리스트를 구조체로 정의한 것

 

배열과 비교해 연결 리스트는 새로운 값을 추가할 때 다시 메모리를 할당하지 않아도 되는 장점이 있다.

But, 연결 리스트에 값을 추가하거나 검색하는 경우 이를 위해 해당 위치까지 연결 리스트의 각 node들을 따라 이동해야 한다. 따라서 연결 리스트의 크기가 n일때, 그 실행 시간은 O(n)이 된다.

배열의 경우 임의 접근이 가능하기 때문에 (정렬 되어 있는 경우) 이진 검색을 이용하면 O(log n)의 실행 시간이 소요 되는 것에 비해서 다소 불리하다. (정렬 되어 있지 않은 경우) 배열도 O(n)의 실행 시간이 걸린다.

 

---

📝 트리(Tree)

연결리스트에서의 각 노드 (연결 리스트 내의 한 요소를 지칭)들의 연결이 1차원적으로 구성되어 있다면, 트리에서의 노드들의 연결은 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;
    }
}

- 이진 검색 트리의 노드 구조체, ‘50’을 재귀적으로 검색하는 이진 검색 함수

• 재귀함수(Recursion)는 정의 단계에서 자신을 재참조하는 함수를 뜻한다. 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 방식으로 주어진 문제를 푸는 방법이다. 재귀 호출이나 되부름이라고도 한다.
• 어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적(recursive)이라고 한다.

이진 검색 트리를 활용하였을 때 검색 실행 시간과 노드 삽입 시간은 모두 O(log n)이다.

 

---

📝 해시 테이블(Hash Table)? = 연결 리스트의 배열

컴퓨터는 임의 접근(random access)가능

 

인덱싱(Indexing)을 하는데 사용하는 배열 = 해시 함수

 

바구니에 각자 학생들의 이름표를 표시(바구니는 세로로 나열 vertical) → 한 바구니에 같은 철자로 시작하는 여러 학생들을 표시하려면 가로로(horizontal) 묶어 표시 (ex_ 26개(a~z) 바구니)

 

But, 같은 철자로 시작하는 사람들의 수가 너무 많으면 O(n)의 시간복잡도로 해시 테이블도 효율적으로 사용할 수 없음

→ 첫 두글자 철자로 구별(ex_ 26 x 26 = 676개 바구니) → 더 많은 바구니가 필요함(공간은 더 많이 필요하지만 충돌할 확률은 더 낮아진다) → 같은 첫 두글자 철자 이름 충돌이 일어남 → 첫 세글자 철자를 저장한다(ex_ 26 x 26 x 26 = 17576개 바구니) → 이름이 구별되어 개선되었지만 같은 철자 이름이 엄청 많다면 여전히 O(n)의 시간복잡도

 

 

But! 단순 Hermione, Hagrid, Harry의 적은 수의 이름이라면 훨씬 빠르게 개선됨(모든 이름을 연결 리스트나 배열에 넣는 것 보다는 해시 테이블이 훨씬 빠르다)

 

이상적인 해시 테이블 - O(1) → 모든 이름이 다 다른 바구니에 저장

(시간과 공간 사이에 균형이 필요)

 

---

📝 트라이(Trie)? = 각각의 노드가 배열로 이루어진 트리

트라이는 기본적으로 트리 형태의 자료 구조인데 특이한 점은 각 노드가 배열로 이루어져 있다.

Hagrid 이름 저장

Harry 이름 추가

Hermione 이름 추가

n명이 존재하면 철자 수만큼 Step이 필요(fixed value) - ex_ H a r r y (5단계)

⇒ 시간 복잡도 : O(1) 상수 시간

(대부분의 이름은 그리 크지 않은 상수값이므로 크게보면 O(1)과 같다.)

O(k) = O(1)

 

장점 : 문자열의 길이가 일정한 경우 문자열들을 저장, 관리하는데 최적의 자료 구조

단점 : 트라이 자료 구조는 매우 넓고 밀도가 높다. 이론적으로 상수 시간의 실행 시간을 제공하기 위해 아주 많은 양의 메모리가 필요하다.

 

---

📝 스택(Stack), 큐(Queue), 딕셔너리(Dictionary)

큐 Queue : FIFO(First In, First Out) 선입 선출 Data Structure

ex_ 햄버거 가게에서 줄을 서서 가장 먼저 온 순서대로 햄버거를 받는 것

• enqueue : get in line 줄 서는 것
• dequeue : get out of line 줄에서 빠져나오는 것

스택 Stack : LIFO(Last In, First Out) 후입 선출

ex_ gmail : 항상 최신 메일을 먼저 볼 수 있음

• push : 요소 추가
• pop : 요소 제거

딕셔너리 Dictionary = Hash Table

‘키’와 ‘값’이라는 요소로 이루어져 있다.

키에 해당하는 값을 저장하고 읽어온다.

ex_ 대학교에서 학번(키)에 따라 학생(값)이 결정 된다.

 

• 다양한 자료구조를 구현할 때는 공간 복잡도, 시간 복잡도, 데이터의 양을 고려해야 한다.

 

참고 사이트 

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

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

 

 

※ 공부하면서 정리한 글입니다. 문제가 있을시 알려주세요.