200816_TIL

hyeojung·2020년 8월 16일

목록 보기

12/62

부스트 코딩뉴비챌린지

6주차 강의를 들었다. 어제 들었어야 했는데 피곤해서 집 도착하자마자 잠들어버리는 바람에 아침 일찍 일어나서 들은 건 안 비밀..^^
이번 주차 자료구조 강의는 앞으로의 코딩에도 매우매우 중요하게 사용될 것들이고, 처음 배우는 내용이므로 정리를 해보려고 한다!
realloc 함수는 메모리를 재설정해준다. realloc(list, sizeof(int)*n); 과 같이 쓰이며 이때 원 메모리 공간에 저장되어 있던 값들이 사라질 수 있으므로 임시 메모리 공간을 할당해 주는 것이 필요하다. 물론 malloc 이나 realloc 으로 할당한 메모리가 더 이상 필요하지 않게 되면 free 함수로 해제해 주어야 한다.

구조체

: struct 구조체이름 { 자료형 멤버이름; . . . }; 혹은 typedef struct { 자료형 멤버이름; . . . } 구조체이름; 과 같이 정의한다. 구조체의 속성값에 접근하려면 구조체이름.멤버이름처럼 점(.) 연산자를 이용한다.

연결 리스트(linked list)

: 메모리 덩어리 여러 개를 포함하는 데이터 구조로, 메모리들이 포인터를 통해 연결되어 있다(값들이 배열처럼 인접해 있지 않기 때문). 값들 뿐만 아니라 값들의 개수만큼의 포인터도 저장해야 하므로 메모리는 두 배 정도 사용된다.
- 아래와 같은 형태로, node가 갖는 값(여기에서는 int형 변수) 후에 struct node형의 포인터(다음 node를 가리킴)가 오는 형식으로 구성되어 있다.

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

Linked list의 구현

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

//연결 리스트의 기본 단위가 되는 node 구조체를 정의합니다.
typedef struct node
{
    //node 안에서 정수형 값이 저장되는 변수를 number으로 지정합니다.
    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;
    }
}

연결 리스트(linked list)에 새로운 값을 추가하거나 삭제하려면?

// node 추가
node *newnode = malloc(sizeof(node));
newnode->next = n;
n = newnode;

// node 삭제
n->next = NULL;
free(n);

연결 리스트(linked list)의 장단점

장점: 배열과 비교했을 때, 새로운 값을 추가할 때 다시 메모리를 할당하지 않아도 된다.
단점: 구조가 정적인 배열과 달리 연결 리스트에서는 임의 접근이 불가능하므로, 연결 리스트에 값을 추가하거나 변경하는 경우 해당 위치까지 연결 리스트의 각 node들을 따라 이동해야 하기 때문에 연결 리스트의 크기가 n일 때 실행 시간은 O(n)이 된다.
배열의 경우 임의 접근이 가능하기 때문에(정렬되어 있는 경우) 이진 검색을 이용하면 O(log n)의 실행 시간이 소요되는 것에 비해서 다소 불리하다.

이진 검색 트리 (Binary Search Tree)

연결 리스트(linked list)를 기반으로 한 새로운 데이터 구조로, 메모리를 더 할당하여 노드들의 연결을 2차원적으로 만든 것이다.
트리가 시작되는 노드를 "루트"라고 하며 루트 노드는 다음 층의 노드들을 가리킨다.
각 노드는 일정 층에 속하고, 다음 층의 노드들을 가리키는 포인터를 가지게 되는데 이진 검색 트리의 경우에는 이 포인터가 2개이다(하나의 노드는 두 개의 자식 노드를 가진다).
왼쪽 자식 노드는 자신의 값보다 작고 오른쪽 자식 노드는 자신의 값보다 크다(재귀적으로 정의되어 있다). 따라서 이진 검색에 유리하다. 실제로 이진 검색 트리를 활용 시 검색 실행 시간과 노드 삽입 시간은 모두 O(log n)이다.
이진 검색 트리의 노드 구조체와 “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;
    }
}