[CS50] 6. 자료구조

 

 

📚 시리즈 목차 

1. 컴퓨팅 사고

2. C언어

3. 배열

4. 알고리즘

5. 메모리

6. 자료구조

 

 

6. 자료구조 

 

2) 배열의 크기 조정하기 

 

배열 이미 만들었는데 크기를 변경하려고 한다면 어떻게해야할까?

안전하게 하려면 새로운 공간에 큰 크기의 메모리를 다시 할당하고 기존 배열의 값을을 하나씩 옮겨줘야한다.

 

왜 이미 할당된 메모리의 크기를 바로 조절을 못하고 임시 메모리를 새로 할당한 뒤 작업을 해줘야할까?

이미 할당된 메모리 옆에는 다른 값이 저장되어있어 메모리를 연속적으로 사용할 수 없기 때문에 조절하고자 하는 크기로 임시 메모리를 새로 할당하여 기존의 값을 그대로 옮겨주고 추가로 할당한 메모리에 새로운 값을 추가 할 수 있다.

쉽게말해 메모리를 사물함이라고 한다면 사용할 사물함의 개수를 한 번 정한 이후에는 공간이 모자란다고해서 주변의 사물함을 마음대로 더 사용할 수 없다.   why? 이미 다른 누군가가 사용하고 있을 수도 있기 때문이다.   따라서 아예 새로운 사물함으로 원하는 크기만큼 할당 받고 다시 사용해야한다.  

 

이런한 메모리 크기를 조절하는 작업은 O(n), 즉 배열의 크기 n만큼의 실행 시간이 소요된다. 

이 과정은 아래 코드와 같다. 

 

1. list라는 포인터를 선언하고 메모리를 할당한다. 

  int *list = malloc(3 * sizeof(int));

 

 

2.  포인터가 메모리부족이나 오류로 인해  선언되지 않았으면 함수종료 

    if (list == NULL)
    {
        return 1;
    }

 

3. list 배열의 각 인덱스에 값 저장

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

4.  list 배열의 값을 임시 저장할 포인터 선언 후 이전보다 더 큰 메모리 할당

    int *tmp = malloc(4 * sizeof(int));

    if (tmp == NULL)
    {
        return 1;
    }

5. list의 값을 tmp로 옮기기

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

6.  확장한 메모리에 값저장 후 기존 list의 메모리를 free()함수로 초기화

    tmp[3] = 4;


    free(list);

7. list가 tmp와 같은 곳을 가리키도록 지정후 새로운 배열 list의 값 확인하기 (기존 가리키던 곳은 연결 끊김)

    list = tmp;


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

8. list의 메모리 초기화

    free(list);

 

전체 코드 

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

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

    // 포인터가 잘 선언되었는지 확인
    if (list == NULL)
    {
        return 1;
    }

    // list 배열의 각 인덱스에 값 저장
    list[0] = 1;
    list[1] = 2;
    list[2] = 3;

    //int 자료형 4개 크기의 tmp 라는 포인터를 선언하고 메모리 할당
    int *tmp = malloc(4 * sizeof(int));

    if (tmp == NULL)
    {
        return 1;
    }

    // list의 값을 tmp로 복사
    for (int i = 0; i < 3; i++)
    {
        tmp[i] = list[i];
    }

    // tmp배열의 네 번째 값도 저장
    tmp[3] = 4;

    // list의 메모리를 초기화
    free(list);

    // list가 tmp와 같은 곳을 가리키도록 지정
    list = tmp;

    // 새로운 배열 list의 값 확인
    for (int i = 0; i < 4; i++)
    {
        printf("%i\n", list[i]);
    }

    // list의 메모리 초기화
    free(list);
}

 

위와 동일한 작업을 realloc이라는 함수를 이용해서 수행할 수도 있다. 

 

📌 realloc()

realloc() 함수는 동적으로 할당된 메모리 블록의 크기를 조정하는데 사용된다. 

realloc() 함수는 기존에 할당된 메모리 블록의 주소를 받아와서 해당 블록의 크기를 변경한 후 새로운 크기에 맞게 메모리를 재할당한다.  재할당된 메모리 블록은 이전 데이터를 보존하면서 새로운 크기로 조정된다. 따라서 기존 메모리 블록을 새로운 크기로 확장하거나 축소할 수 있다. 

void* realloc(void* ptr, size_t size);

• ptr: 이전에 할당된 메모리 블록의 포인터이다.
• size: 새로 할당할 메모리 블록의 크기이다.

1. ptr이 NULL인 경우, realloc은 malloc(size)와 동일한 기능을 수행하여 주어진 크기의 메모리 블록을 할당하고 포인터를 반환한다.
2. ptr이 NULL이 아닌 경우, realloc은 기존 메모리 블록의 크기를 size로 변경한다.
   • 만약 size가 현재 크기보다 작은 경우, 메모리 블록은 축소된다. 데이터의 일부가 잘려나갈 수 있다.
   • 만약 size가 현재 크기보다 큰 경우, 메모리 블록은 확장된다. 추가된 부분은 이전 값이나 0으로 초기화된다.
   • 만약 size가 0인 경우, 메모리 블록이 해제된다. ptr이 NULL을 가리키게 된다.
   • realloc 함수는 메모리 할당이 실패할 경우 NULL을 반환한다. 따라서, 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;

    // tmp 포인터에 메모리를 할당하고 list의 값 복사
    int *tmp = realloc(list, 4 * sizeof(int));
    if (tmp == NULL)
    {
        return 1;
    }

    // list가 tmp와 같은 곳을 가리키도록 지정
    list = tmp;

    // 새로운 list의 네 번째 값 저장
    list[3] = 4;

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

    //list 의 메모리 초기화
    free(list);
}

 

 

3) 연결 리스트 : 도입

기본적인 포이터 구조만을 이용해서 메모리를 관리하기에는 다소 번거로울 때가 많다. 그래서 메모리를 조금 더 효율적을 관리하고 사용하는 방법을 배우기 위해  데이터 구조의 개념과 연결 리스트에 대해 더 알아보자. 

 

 

 

연결 리스트

 

연결리스트는 데이터 구조중 하나이다.  

 

배열에서는 각 인덱스의 값이 메모리상에 연이어 저장되어있다.  그래서 크기를 더 확장하고 싶으면 아예 새로운 메모리로 값을 옮겨야한다.  하지만 조금 다르게 하는 방법도 있다.  

 

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

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

 

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

연결 리스트는 아래 코드와 같이 간단한 구조체로 정의할 수 있다. 

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

연결 리스트는 데이터 요소들이 Node라 불리는 객체들로 연결되어있는 자료 구조이다.  

각 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어져 있다. 

 

 

 

4) 연결 리스트 : 코딩

 

 

연결 리스트는 아래와 같이 값을 저장한다.

이것을 코드로 표현하면 아래와 같다

 

1. 먼저 연결 리스트의 기본 단위가 되는 node 구조체를 정의한다. 

typedef struct node
{

    int number; 
    struct node *next;
}
node;

 

2. list 라는 이름의 node 포인터를 정의한다. 이 포인터는 현재 아무것도 가리키고 있지 않기 때문에 NULL로 초기화한다. 

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

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

새로운 node를 위해 메모리를 할당하고 포인터 *n으로 가리킨다.  n은 포인터 변수로 만들기 위해 *을 사용했다. 

 

3. n의 number 필드에 1의 값을 저장한다.  n->number은 (*n).number와 동일한 의미이다. 

n 다음에 정의된 node가 없으므로 NULL로 초기화한다.  

그리고 첫번째 node를 정의했기 때문에 list포인터를 n포인터로 바꿔 준다.  

   n->number = 1;
   n->next = NULL;
   list = n;

 

4. 이제 list에 다른 node를 더 연결하기 위해 n에 새로운 메모리를 다시 할당한다.  

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

 

5. n의 number와 ndext의 값을 각각 저장한다. 

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

6. list가 가리키는 것은 첫 번째 node이다.  이 node의 다음 node를 n포인터로 지정한다. 

    list->next = n;

7. 다시 한 번 n 포인터에 새로운 메모리를 할당하고 number과 next의 값을 저장한다. 

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

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

8. 다음 node(list->next)의 다음 node(list->next->next)를 n 포인터로 지정한다. 

    list->next->next = n;

9. list에 연결된 node를 처음부터 방문하면서 각 number 값을 출력한다. 

      // 마지막 node의 next에는 NULL이 저장되어 있을 것이기 때문에 이 것이 for 루프의 종료 조건이 된다.
  for (node *tmp = list; tmp != NULL; tmp = tmp->next)
    {
        printf("%i\n", tmp->number);
    }

10. 메모리를 해제해주기 위해 list에 연결된 node들을 처음부터 방문하면서 free해준다. 

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

 

전체 코드

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

//연결 리스트의 기본 단위가 되는 node 구조체를 정의합니다.
typedef struct node
{
    //node 안에서 정수형 값이 저장되는 변수를 name으로 지정합니다.
    int number; 

    //다음 node의 주소를 가리키는 포인터를  *next로 지정합니다.
    struct node *next;
}
node;

int main(void)
{
    // list라는 이름의 node 포인터를 정의합니다. 연결 리스트의 가장 첫 번째 node를 가리킬 것입니다. 
    // 이 포인터는 현재 아무 것도 가리키고 있지 않기 때문에 NULL 로 초기화합니다.
    node *list = NULL;

    // 새로운 node를 위해 메모리를 할당하고 포인터 *n으로 가리킵니다.
    node *n = malloc(sizeof(node));
    if (n == NULL)
    {
        return 1;
    }

    // n의 number 필드에 1의 값을 저장합니다. “n->number”는 “(*n).numer”와 동일한 의미입니다. 
    // 즉, n이 가리키는 node의 number 필드를 의미하는 것입니다. 
    // 간단하게 화살표 표시 ‘->’로 쓸 수 있습니다. n의 number의 값을 1로 저장합니다.
    n->number = 1;

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

    // 다시 한 번 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);
    }

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

 

새로운 노드를 추가하려면 아래와 같이 하면된다. 

 

새로 노드를 추가할 때 조심해야한다.  바로 새로운 노드를 중간에 추가한다고 next를 새로운 node와 연결해버리면 이전에 연결되어있던 부분들은 잃어버린다. 

 

그래서 새로운 노드를 먼저 추가할 위치 다음 노드를 먼저 가리키게 한다.

그 다음 추가할 위치 이전 노드에서 추가할 노드를 가리키도록 하면 안전하게 노드를 추가할 수 있다. 

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


//연결 리스트의 기본 단위가 되는 node 구조체를 정의합니다.
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;
    }


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


    list = n;


    // 첫 번째 노드의 number 확인
    printf("number : %i\n",list->number );


    // n에 새로운 메모리를 다시 할당
    n = malloc(sizeof(node));
    if (n == NULL)
    {
        return 1;
    }


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


    list->next = n;


    // 두 번째 노드의 number 확인
    printf("number : %i\n", list->next->number);


    // 다시 n에 새로운 메모리 할당
    n = malloc(sizeof(node));
    if (n == NULL)
    {
        return 1;
    }


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


    list->next->next = n;


    // 세 번째 노드의 number 확인
    printf("number : %i\n", list->next->next->number);



    // 두 번째 노드와 세 번째 노드 사이에 노드 추가하기


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

    // 새로 추가된 노드 구분을 위해 3대신 33을 추가
    tmp->number = 33;
    // 먼저 tmp에 세번 째 노드를 가리키도록 설정
    tmp->next = n;


    // 세 번째노드(미래 네번째 노드)에 잘 연결되었는지 확인
    printf("number check : %i\n", tmp->number);


    // 두 번째 노드 다음에 새로 추가한 노드와 연결
    list->next->next = tmp;


    // 새로워진 네 번째 노드에 number 4로 교체후 next  NULL로 교체
    n->number = 4;
    n->next = NULL;



    // 두 번째 노드와 세 번째 노드(새로 추가된)가 잘 연결되어 네 번째 노드 까지 출력이 되는지 확인
    printf("number : %i\n", list->next->next->number);

    // 최종 전체 list 확인
     for (node *tmps = list; tmps != NULL; tmps = tmps->next)
    {
        printf("%i\n", tmps->number);
    }



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

 

중간 노드를 제거할 때

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


//연결 리스트의 기본 단위가 되는 node 구조체를 정의합니다.
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;
    }


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


    list = n;


    // 첫 번째 노드의 number 확인
    printf("number : %i\n",list->number );


    // n에 새로운 메모리를 다시 할당
    n = malloc(sizeof(node));
    if (n == NULL)
    {
        return 1;
    }


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


    list->next = n;


    // 두 번째 노드의 number 확인
    printf("number : %i\n", list->next->number);


    // 다시 n에 새로운 메모리 할당
    n = malloc(sizeof(node));
    if (n == NULL)
    {
        return 1;
    }


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


    list->next->next = n;


    // 세 번째 노드의 number 확인
    printf("number : %i\n", list->next->next->number);



    // 두 번째 노드 제거
    list->next = list->next->next;

    // 만약 마지막에 메모리 제거를 해주지 않을 때
    //  node* temp = list->next->next;
    //  free( list->next);
    //  list->next = temp;


    // 최종 전체 list 확인
     for (node *tmps = list; tmps != NULL; tmps = tmps->next)
    {
        printf("%i\n", tmps->number);
    }



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

 

 

5) 연결 리스트 : 시연

 

연결리스트도 단점이 존재한다.  바로 배열과 달리 연결 리스트에서는 임의 접근이 불가능하다.

 

연결 리스트에 값을 추가하거나 검색하는 경우에는 해당하는 위치까지 연결 리스트의 각 node들을 따라 이동해야한다. 

따라서 연결 리스트의 크기가 n 일때 그 실행 시간은 O(n)이 된다. 

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

 

다시 말하자면 

배열이 정렬되어있다면 이진 검색으로 검색 소요시간이 O(log n)으로 줄일 수 있지만 정렬이 되어있지않으면

최악의 경우 검색 대상이 배열의 마지막 요소에 위치하거나 배열에 존재하지 않을 경우 배열의 모든 요소를 비교해야 하므로 O(n)의 시간이 소요된다. 

 

연결리스트는 검색을 하려면 첫 번째 노드부터 시작하여 링크를 따라가면서 검색대상을 찾아야함으로 최악의 경우, 검색 대상이 연결 리스트의 마지막 노드에 위치하거나 연결 리스트에 존재하지 않을 경우 모든 노드를 순차적으로 비교해야 하므로 O(n)의 시작 복잡도로 정렬되지 않은 배열에서 탐색할 때와 시간이 같다.

 

만약에 특정 위치에 있다는 것을 안다면  배열은 인덱스를 사용하여 상수 시간에 특정 위치의 요소에 접근 할 수 있기 때문에 검색 소요시간을 O(1)로 줄일 수 있지만 연결 리스트는 각 노드가 불연속적으로 저장되어 있기 때문에 순차적 탐색으로 인해 여전히 O(n)의 시간이 소용된다.  

 

각각 장단점이 존재하기 때문에 프로그래밍 할 때 목적에 부합하는 가장 효율적인 데이터 구조를 고민해서 사용하는 것이 중요하다. 

 

 

6) 연결 리스트 : 트리

연결 리스트를 활용해서 보다 더 다양한 데이터 구조를 만들 수 있다.

기존의 연결 리스트 처럼 각 요소가 다른 요소를 하나씩만 가리키고 있지 않고 가리키는 요소가 여러개가 된다면 어떤 장단점이 있을까?

 

 

트리는 연결리스트를 기반으로 한 새로운 데이터 구조이다.  

연결리스트에서 각 노드들의 연결이 1차원적으로 구성되어 있다면, 트리에서의 노드들의 연결은 2차원적으로 구성되어있다.  

각 노드는 일정한 층에 속하고 다음 층의 노드들을 가리키는 포인터를 가지게 된다. 

 

 

가장 높은 층에서 트리가 시작되는 노드를 '루트'라고 한다. 루트 노드는 다음 층의 노드들을 가리키고 있고, 이를 '자식 노드'라고 한다. 

위 그림에 묘사된 트리는 구체적으로 '이진 검색 트리'이다. 

이런 트리 구조는 이진 검색을 수행하는데 유리하다 .

 

특징

• 계층적 구조: 트리는 부모-자식 관계를 가지는 계층적인 구조이다. 각 노드는 하나의 부모 노드와 여러개의 자식 노드를 가질 수 있다.
• 단일 루트 : 트리는 단일한 루트 노드를 가지며, 모든 노드는 루트로부터 도달 가능해야 한다.
• 순환 구조 없음 : 트리는 순환 구조를 가질 수 없다. 즉, 어떤 노드에서 출발하여 자기 자신으로 되돌아오는 경로가 존재하지 않는다.
• 간선: 트리의 각 노드들은 간선으로 연결되어 있다. 간선은 부모 노드와 자식 노드를 연결하는 선이며, 각 노드는 최대 하나의 부모와 여러 개의 자식을 가질 수 있다.

 

값을 검색할 때 이진 검색 트리가 기본 연결 리스트에 비해 가지는 장단점은 아래와 같다.

 

장점

• 1. 가장 큰 장점은 검색 속도가 훨씬 더 빠르다는 것이다.  이진 검색 트리는 데이터를 정렬된상태로 유지하기에 검색 작업을 수행할 때 평균적으로 O(long n)의 시간 복잡도를 가진다.  데이터 규모가 커도 효율적인 검색이 가능하다.
• 2. 기본 연결 리스트에 비해 접근 속도가 빠르기에 삽입과 삭제를 더 빠르게 수행할 수 있다.  

단점

• 1. 삽입 및 삭제 연산에 있어서 최악의 경우 트리의 균형이 깨지고 비효율적인 상태가 될 수 있다.  균형이 깨진 이진 검색 트리는 특정 연산(탐색,삽입,삭제)의 시간 복잡도가 O(n)에 가까워지며, 이는 이진 검색 트리의 장점을 상실하게 된다.  

 

위에서 말한 균형이 깨진 트리를 개선하기 위해 균형 잡힌 트리구조가 사용된다.  균형 잡힌 트리는 트리의 높이를 가능한 작게 유지하여 탐색, 삽입, 삭제등의 연산을 빠르게 수행할 수 있도록 한다.  대표적으로 균형 잡힌 트리로는 AVL 트리, 레드-블랙 트리, B-트리 등이 있다.  

이러한 균형 잡힌 트리는 특정 규칙과 조건을 유지하면서 데이터를 삽입, 삭제할 때 자동으로 균형을 유지하는 기능을 갖고 있다. 

이를 통해 트리의 균형이 깨지지 않고 일정한 성능을 유지할 수 있다. 

 

 

아래 코드에서는 이진 검색 트리의 노드 구조체와 '50'을 재귀적으로 검색하는 이진 검색 함수를 구현한 것이다.

//이진 검색 트리의 노드 구조체
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;
    }
}

 

 

7) 해시 테이블

해시 테이블은 '연결 리스트의 배열'이다.

 

연결리스트나 트리에서는 값을 검색할 때 O(n) 또는 O(log n)의 시간이 걸렸다.   이 시간을 조금 더 단축해서 거의 O(1)에 가깝게 할수 있는 자료 구조가 있다.  바로 '해시 테이블' 이다.

 

해시 테이블은 데이터를 효율적으로 저장하고 검색하기 위한 데이터 구조이다. 해시 테이블은 키-값쌍으로 이루어진 데이터를 저장하는데, 키를 해시 함수를 통해 해시 값으로 변환한 후 해당 값을 배열의 인덱스로 사용하여 데이터를 저장하고 검색한다.  이를 통해 매우 빠른 데이터 접근이 가능하며, 시간 복잡도는 평균적으로 O(1)에 가깝다.  

 

특징 및 장점

• 빠른 데이터 접근 : 해시 테이블은 키를 해시 함수를 통해 해시 값으로 변환하고, 해당 값을 배열의 인덱스로 사용하여 데이터에 접근한다. 이렇게 함으로써 데이터를 매우 빠르게 검색할 수 있다. 
• 고유한 키 : 해시 테이블에서 사용되는 키는 고유해야 한다. 각 키는 해시 함수를 통해 고유한 해시 값으로 매핑되며, 이를 통해 중복된 키를 허용하지 않고 데이터를 구분한다.
• 충돌 해결, 서로 다른 키가 같은 해시 값으로 매핑될 수 있으며, 이를 "충돌"이라고 한다. 충돌을 해결하기 위해 일반적으로 체이닝 또는 개방 주소법을 사용한다. 체이닝은 같은 해시 값에 대한 데이터를 연결 리스트 형태로 연결하여 저장하는 방식이고, 개방 주소법은 충돌이 발생한 경우 빈 공간을 찾아 데이터를 저장하는 방식이다.
• 메모리 효율성: 해시 테이블은 키와 값의 쌍으로 데이터를 저장하기 때문에 메모리부문에서 효율적이다. 각 데이터의 저장 위치를 해시 값으로 계산하여 인덱스로 사용하기 때문에 배열의 크기가 상대적으로 작아도 많은 데이터를 저장할 수 있다. 
• 다양한 응용 분야 : 해시 테이블은 데이터베이스 캐시, 캐싱 알고리즘, 중복 검사, 데이터 인덱싱등 다양한 분야에서 활용된다. 데이터의  고유성이 중요하고 빠른 검색 속도가 필요한 경우 해시 테이블은 매우 유용하다. 

 

❗️ 해시 값

해시 테이블에서 데이터의 저장 위치를 결정하기 위해 해시 값으로 계산한다는 것은, 데이터의 키를 해시 함수에 입력하여 해시 값을 얻은 후, 그 해시 값을 배열의 인덱스로 사용하여 데이터를 저장하는 것을 의미한다.  

 

해시 함수는 키를 입력으로 받아서 고유한 해시 값으로 변환하는 함수이다. 이 해시 값은 보통 정수형으로 표현되며, 배열의 인덱스로 사용된다. 해시 함수는 다양한 방식으로 구현될 수 있으며, 좋은 해시 함수는 데이터를 고르게 분포시키고 충돌을 최소화해야 한다.

 

예를 들어, 해시 테이블에 학생들의 성적을 저장한다고 가정해보자. 각 학생의 이름이 키가 될 수 있고, 해당 학생의 성적을 값으로 저장할 수 있다. 해시 함수는 학생의 이름을 입력으로 받아 고유한 해시 값으로 변환한다. 예를 들어, 해시 함수에'John"이라는 이름을 입력하면 5라는 해시 값이 반환될 수 있다. 이 해시 값 5는 배열의 인덱스로 사용되어, 성적 데이터를 배열의 5번 인덱스에 저장한다.

 

이렇게 해시 함수를 사용하여 각 데이터의 해시 값으로 계산된 인덱스를 통해 데이터를 저장하고 검색함으로써, 데이터 접근 속도를 효율적으로 관리할 수 있다.

 

예시 )

아래 그림과 같이 사람의 이름이 해시 테이블에 저장되며, 해시 함수는 '이름의 가장 첫 글자'인 경우를 생각해보자.

그 경우 알파벳 개수에 해당하는 총 26개의 포인터들이 있을 수 있으며, 각 포인터는 그 알파벳으로 시작하는 이름들을 저장하는 연결 리스트를 가리키게 된다. 

만약 해시 함수가 이상적이라면, 각 바구니에는 단 하나의 값들만 담기게 될 것이다. 

따라서 검색 시간은 O(1)이 된다.

하지만 그렇지 않은 경우, 최악의 상황에는 단 하나의 바구니에 모든 값들이 담겨서 O(n)이 될 수도 있다. 

일반적으로는 최대한 많은 바구니를 만드는 해시 함수를 사용하기 때문에 거의 O(1)에 가깝다고 볼 수 있다.

 

 

8) 트라이

 

트라이는 기본적으로 '트리' 형태의 자료 구조이다.

특이한 점은 각 노드가 '배열'로 이루어져있다는 것이다.  

예를 들어 영어 알파벳으로 이루어진 문자열 값을 저장한다면 이 노드는 a부터 z까지의 값을 가지는 배열이 된다.  

그리고 배열의 각 요소, 즉 알파벳은 다음 층의 노드 (a-z배열)를 가리킨다. 

 

주로 단어 검색, 자동 완성, 철자 검사 등의 기능을 구현하는데에 활용된다. 

트라이의 기본 아이디어는 문자열의 각 문자를 노드로 표현하는 것이다. 루트 노드에서 시작하여 각 문자마다 자식 노드로 연결되는 경로를 형성한다.  이 때, 각 노드는 문자와 함께 종료 노드인지를 나타내는 플래그 변수를 가질 수 있다.  트라이의 장점 중 하나는 문자열 검색의 속도가 빠르다는 것이다. 문자열의 길이에 관계없이 상수 시간 내에 검색할 수 있다.

 

예시)

아래 그림과 같이 Hermione, Harry, Hagrid 세 문자열을 트라이에 저장해보자

루트 노드를 시작으로 각 화살표가 가리키는 알파벳을 따라가면서 노드를 이어주면 된다. 

 

위와 같은 트라이에서 값을 검색하는데 걸리는 시간은 '문자열의 길이'에 의해 한정된다.

일반적인 영어 이름의 길이를 n이라고 했을 때, 검색 시간은 O(n)이 되지만, 대부분의 이름은 그리 크지 않은 상수값이기 때문에 O(1)이나 마찬가지라고 볼 수 있다. 

 

 

트리가 해시 테이블에 비해 가지는 장단점을 알아보자.

 

트라이 장점

• 접두사 탐색 : 트라이는 각 노드에서 문자를 나타내는 링크를 통해 문자열을 저장하기 때문에 특정 접두사를 탐색하는 데 걸리는 시간은 O(1)상수에 가깝다.
• 메모리 효율성: 해시 테이블은 모든 키를 해시 함수를 통해 인덱스로 변환하고, 인덱스를 통해 값을 저장한다. 해시 테이블은 키를 위한 메모리 공간을 할당해야 하므로, 저장되는 키의 수가 적더라도 상대적으로 많은 메모리를 사용할 가능성이 있지만 트라이는 문자열을 노드로 저장하므로, 중복되는 문자열의 경우 메모리를 더 효율적으로 사용할 수 있다. 
• 자동완성 : 트라이는 접두사 탐색을 쉽게 수행할 수 있기 때문에 자동완성 기능을 구현하는 데에도 유용한다. 트라이는 사용자가 입력한 문자열의 접두사에 해당하는 모든 가능한 완성어를 효율적으로 찾아낼 수 있다.

트라이 단점

• 메모리 요구량: 트라이는 문자열 저장을 위해 많은 포인터를 사용하기 때문에 문자열이 매우 길거나 문자열의 수가 많은 경우에는 메모리 요구량이 크게 증가할 수 있다.
• 삽입/삭제 비효율성 : 해시 테이블보다 트라이가 삽입 삭제에서 비효율적이다. 트라이는 구조를 유지하기 위해서는 많은 노드를 이동하고 연결 해야하기 때문이다. 따라서 트라이는 정적인 데이터 세트에 적합하며 동적인 세트에서는 삽입과 삭제 작업에 대해 상대적으로 느릴 수 있다.

 

9) 스택, 큐, 딕셔너리

 

대표적인 자료 구조인 스택, 큐, 딕셔너리에 대해 알아보자.

 

큐

큐는 메모리 구조에서 살펴봤듯이 값이 아래로 쌓이는 구조이다. 

값을 넣고 뺄 때 '선입 선출' 또는 'FIFO'라는 방식을 따르게 된다.  즉 가장 먼저 들어온 값이 가장 먼저 나가는 것이다. 

배열이나 연결 리스트를 통해 구현이 가능하다. 

 

 

스택

스택은 위로 쌓이는 구조이다.

따라서 값을 넣고 뺄 때 "후입 선출" 또는 'LIFO'라는 방식을 따르게 된다.   즉 가장 나중에 들어온 값이 가장 먼저 나가는 것이다.

배열이나 연결 리스트를 통해 구현 가능하다.

 

딕셔너리

딕셔너리는 키와 값이라는 요소로 이루어져있다.  

일반적인 의미에서 '해시 테이블'과 동일한 개념이라고도 볼 수 있다.

https://domythang.tistory.com/183

 

 

 

퀴즈 복습

 

 

---

정렬이되어있는 배열이라면 이진 탐색을 통해 O(log n)으로 접근할 수 있다.  연결 리스트는 무조건 O(n)이다. 

하지만 배열이 정렬되어있지 않으면  선형 검색을 해야하기 때문에 O(n)이다. 

---

---

• 연결 리스트는 원하는 값을 찾을 때 까지 노드를 타고 타고 들어가야 해서 O(n)이다. 
• 트리 : 이진 검색 트리를 활용하였을 때 검색 실행 시간과 노드 삽입 시간은 모두 O(log n)이다. 
• 해시 테이블은 최악의 경우 단 하나의 바구니에 모든 값들이 담겨서 O(n)이긴 하지만  해시 함수가 이상적이라면(최대한 많은 바구니에 담으면) 거의 O(1)에 가깝다.  
• 트라이는 영어 이름의 길이를 n이라고 했을 때, 검색 시간은 O(n)이 되지만 , 대부분의 이름은 그리 크지 않은 상수값(예, 20자 이내)이기 때문에 O(1)이나 마찬가지이다. 

---

 

트리는 가장 최상위 노드를  '루트 노트'라고 지칭하고  그 아래에 각 노드들은 하나의 부모 노드와 여러개의 자식노드로 이루어져있다. 

 

---

---

 

트라이는 각 노드가 배열로 이루어져있다. 영어 문자열인 경우 문자 하나당 하나의 노드에 들어가고 각 노드는 a~z까지 존재한다. 

즉 문자 하나를 선택하면 하위 노드로 넘어가서 해당 문자를 저장하고 또 그 하위 노드로 들어가서 다음 단어를 저장하는 식으로 진행된다.

최상위 노드를 '루트 노드'라고 지칭하고 그 아래는 여러개의 자식 노드가 있다.

 

---

큐 : 선입 선출 ( FIFO )

스택 : 후입 선출( LIFO )

딕셔너리 : 키와 값으로 이루어져있다.  즉 키값을 입력하면 바로 값이 나온다. 

트리 : 연결리스트를 기반으로 한 데이터 구조, 트리에서 노드들은 2차원적으로 연결되어있다.  (연결 리스트 1차원)

 

---

 

 

---

 

• 시간 복잡도 : 자료 구조에따라 속도는 빠르지만 메모리가 많이 필요한 경우가 있고 속도는 느리지만 메모리가 적게드는 경우등 다양하기에 빠르게 처리해야하는지 느리게 처리해야하는지등 자료구조를 구현할 때 꼭 고려해야할 사항 중 하나이다. 
• 공간 복잡도 : 공간 복잡도는 프로그램이 사용하는 메모리 공간의 양을 의미한다.  예를 들어, 해시 테이블은 고정된 크기의 배열과 연결 리스트로 구성되어 있으며, 필요한 메모리 공간을 효율적으로 할당하여 사용한다. 불필요한 공간 낭비를 줄이기 위해 해시 테이블의 크기를 적절하게 설정하고, 충돌을 최소화하는 해시 함수를 설계하는 등의 고려가 필요하다. 또한 필요한 데이터만을 저장하도록 자료구조를 설계하는 것도 중요하다. 예를 들어, 이름과 전화번호 외에 다른 정보를 저장하지 않는다면 해당 정보를 위한 공간은 불필요하게 소모되지 않도록 구현해야 한다.  공간 복잡도는 프로그램의 성능과 메모리 사용량에 직접적인 영향을 미치므로, 가능한 한 효율적으로 메모리를 활용할 수 있는 자료구조와 알고리즘을 선택하여 설계하는 것이 좋다. 
• 데이터의 양: 데이터의 양은 프로그램의 성능과 메모리 사용에 직접적인 영향을 미친다.  데이터의 양이 많은 경우, 효율적인 자료구조를 선택하고 알고리즘을 설계해야 한다.  예를 들어, 검색 연산이 빈번한 경우에는 해시 테이블이나 트리 자료구조를 사용하여 빠른 검색이 가능한 구조를 선택할 수 있다. 
• 메모리 주소 표기법 : 일반적으로 프로그래밍 언어 수준에서는 직접적으로 다루지 않는 경우가 많기에 반드시 고려해야할 점은 아니다.  대부분의 프로그래밍 언어에서는 메모리 관리를 추상화하여 개발자가 직접 메모리 주소를 다루지 않고 변수, 포인터 등을 활용하여 메모리에 접근한다. 

 

 

---

Reference

 

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