6. 자료구조

eunheelog·2023년 6월 15일

boostcourse

목록 보기

11/13

1. malloc과 포인터 복습

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

    x = malloc(sizeof(int));

    *x = 42;
    *y = 13;
}
→ 초기화 되지 않은 *y는 오류를 발생시킬 수도 있다.
y = x;

*y = 13;
→ 추가하게 되면 y는 x와 같은 곳을 가리키게 되므로 13이 저장된다.

생각해보기-1

포인터를 초기화시키지 않고 값을 저장하면 어떤 오류를 발생할 수 있을까요?
→ 기존에 있는 데이터를 의도치 않게 변경하는 오류가 발생할 수 있다.

2. 배열의 크기 조정하기

SourceCode
새로운 변수를 선언, 메모리할당한 후 값 복사

#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 함수로 값 복사

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

생각해보기-2

이미 할당된 메모리 크기를 조절할 때 임시 메모리를 새로 할당해줘야 하는 이유는 무엇일까요?
→ 데이터는 연속적으로 저장되기 때문에 할당된 메모리 다음 공간에 저장된 데이터에 영향을 주지 않기 위해서

3. 연결 리스트 : 도입

연결 리스트 → 각 인덱스의 메모리 주소에서 자신의 값과 다음 값의 주소(포인터)를 저장한다.
연결 리스트의 가장 첫 번째 값인 1은 2의 메모리 주소를, 2는 3의 메모리 주소를 저장한다.
다음 값이 없을 경우 NULL을 다음 값의 주소로 저장한다.
SourceCode
연결리스트를 간단한 구조체로 정의
```
typedef struct node
{
    int number;
    struct node *next;
}
node;
```
→ number는 각 node가 가지는 값
→ *next는 다음 node를 가리키는 포인터
→ typedef struct가 아닌 typedef struct node 라고 명시하는 것은 구조체 안에서 node를 사용하기 위함 !

생각해보기-3

연결 리스트를 배열과 비교하였을 때 장단점은 무엇이 있을까요?
→ 배열에 비해 삽입과 삭제가 용이하다는 장점과 다음 배열의 주소도 함께 저장해야해서 추가적으로 메모리가 더 필요하다는 단점이 있다.

4. 연결 리스트 : 코딩

SourceCode
구조체로 연결 리스트 구현

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

생각해보기-4

연결 리스트의 중간에 node를 추가하거나 삭제하는 코드는 어떻게 작성할 수 있을까요?
→ 다음 값을 가리키는 주소를 변경해주면 된다.
ex) 이전 노드 before, 추가하거나 변경할 노드 now, 다음 노드 next라고 정의하자.

추가할 경우 before은 now를 가리키게 하고 now는 next를 가리키게 한다.
삭제할 경우 before은 next를 가리키게 한다.

5. 연결 리스트 : 시연

배열과 비교해서 연결리스트는 새로운 값을 추가할 때 메모리를 다시 할당하지 않아도 된다 !
연결 리스트의 크기가 n일 경우 값을 추가하거나 검색하는 경우 O(n)
정렬되어 있는 배열의 경우 이진 검색을 이용하면 O(log n)
목적에 부합하는 효율적인 데이터 구조를 사용하는 것이 중요하다 !!!

생각해보기-5

배열이 정렬되어 있지 않은 경우의 검색 소요 시간을 연결 리스트의 검색 시간과 비교해보세요.
→ 둘 다 하나씩 탐색해봐야하므로 O(n)이라고 생각한다.

6. 연결 리스트 : 트리

루트 : 가장 높은 층에서 트리가 시작되는 노드
자식 노드 : 루트 노드가 가리키는 다음 층의 노드

위 그림은 이진 검색 트리이다.
- 하나의 노드는 두 개의 자식 노드를 가진다.
- 왼쪽 자식 노드는 자신의 값보다 작다.
- 오른쪽 자식 노드는 자신의 값보다 크다.
- 이진 검색을 수행할 때 유리하다.

SourceCode
이진 검색 함수
(이진 검색 트리의 노드 구조체와 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;
    }
}

이진 검색 트리의 검색 실행 시간과 노드 삽입 시간은 모두 O(log n)

생각해보기-6

값을 검색할 때 이진 검색 트리가 기본 연결 리스트에 비해 가지는 장점과 단점은 무엇이 있을까요?
→ 검색 범위를 반으로 줄여나갈 수 있는 장점이 있고 삽입과 삭제가 복잡하다는 단점이 있다.

7. 해시 테이블

해시 테이블 : 연결 리스트의 배열
위 그림과 같이 사람의 이름이 해시 테이블에 저장된다.
해시 함수가 이름의 가장 첫 글자인 경우 알파벳 개수에 해당하는 26개의 포인터들이 있을 수 있다.
→ 각 포인터는 그 알파벳으로 시작하는 이름들을 저장하는 연결 리스트를 가리키게 된다.
이상적인 해시 함수는 각 바구니에 단 하나의 값만 담기므로 검색 시간은 O(1)
최악의 상황에는 단 하나의 바구니에 모든 값이 담겨 O(n)이 될 수도 있다.

생각해보기-7

해시 함수는 어떻게 만들 수 있을까요?
→ 분류 기준을 만들고 함수를 만들면 될 것 같다.

8. 트라이

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

각 노드가 배열로 이루어져있다.
Hermione, Harry, Hagrid 문자열을 트라이에 저장해보면 아래 그림과 같다.

→ 루트 노드를 시작으로 각 화살표가 가리키는 알파벳을 따라가며 노드를 이어준다.
트라이에서 값을 검색하는 데 걸리는 시간은 문자열의 길이에 한정된다.
일반적인 영어 이름의 길이가 n이라면 검색 시간은 O(n)
대부분의 이름은 크지 않은 상수값(20자 이내)이기에 O(1)이라고 볼 수 있다.

생각해보기-8

트라이가 해시 테이블에 비해 가지는 장점과 단점은 무엇일까요?
→ 검색이 용이하다는 장점이 있지만 메모리가 많이 필요하다는 단점이 있다.

9. 스택, 큐, 딕셔너리

큐
- 아래로 쌓이는 구조
- 값을 넣고 뺄 때 선입 선출 or FIFO(First In First Out) 방식을 따름
- 배열이나 연결 리스트를 통해 구현 가능
스택
- 위로 쌓이는 구조
- 값을 넣고 뺄 때 후입 선출 or ‘LIFO(Last In First Out) 방식을 따름
- 배열이나 연결 리스트를 통해 구현 가능
딕셔너리
- 키와 값이라는 요소로 구성됨
- 해시 테이블과 동일한 개념
- 키를 어떻게 정의할 것인지가 중요함

eunheelog

⛧1일 1알고리즘⛧

이전 포스트

Quiz 5

다음 포스트