NAVER 부스트코스 CS50 - 6. 자료구조

6 자료구조

 

6-1 malloc과 포인터 복습

포인터 초기화: 포인터 변수에 malloc으로 메모리영역을 할당해 주는 것

초기화 되지 않은 포인터는 프로그램 어딘가를 임의로 가리키고 있을 수 있고, 오류를 발생시킬 수 있다. 

 

 

6-2 배열의 크기 조정하기

일정한 크기의 배열이 주어졌을 때, 그 크기를 키우려면 새로운 공간에 큰 크기의 메모리를 다시 할당해 기존 배열의 값들을 하나씩 옮겨줘야 한다. 코드로 나타내 보게 되면,

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

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

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

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

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

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

    tmp[3] = 4;


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

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

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

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

이렇게 된다. 그러나 realloc이라는 함수를 사용해 수행할 수도 있다. 

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

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

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

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

    //int 자료형 4개 크기의 tmp 라는 포인터를 선언하고 메모리 할당
    int *tmp = realloc(4 * sizeof(int));
    if (tmp == NULL){
        return 1;
    }
    
    list = tmp; // list가 tmp와 같은 곳을 가리키도록 지정
    
    list[3] = 4;

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

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

realloc을 사용하게 되면 총 코드의 길이는 훨씬 줄어들고 tmp포인터를 list와 같은 곳을 가리키게 만들어 반복되는 작업들도 피할 수 있게 만든다.

 

 

6-3 연결 리스트: 도입

데이터 구조는 메모리를 더 효율적을 관리하기 위해 새로 정의하는 구조체이다. 어떤 값들이 메모리상의 여러 군데 나눠져 있다고 해도 바로 다음 값의 메모리 주소만 기억하고 있으면 여전히 값을 연이어 읽을 수 있다. 이것을 ‘연결리스트’라고 하며, 연결리스트는 자신의 값과 함께 바로 다음 값의 주소(포인터)를 저장한다.

데이터를 추가할 때 매번 메모리의 크기와 추가할 데이터의 메모리 크기를 할당하지 않아도 된다는 장점이 있으나 포인터를 저장하는 메모리가 별도로 필요하고 인덱스를 이용해 자료를 빠르게 읽을 수 없다는 단점이 있다.

 

 

6-4 연결 리스트: 코딩

여기서는 코딩을 통해 연결리스트를 구현해보는 시간을 가졌다.

#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){
    	return 1;
    }
    
    n->number = 1; // n의 number 값으로 1로 저장한다.
    n->next = NULL; // n 다음 정의된 노드가 없으므로 NULL로 초기화
    list = n; // 첫 번째 노드 정의가 끝났기 때문에 list포인터를 n포인터로 변경
    
    n = malloc(sizeof(node)); // list에 다른 노드를 더 연결하기 위해 n에 새로운 메모리 할당
    if (n == NULL){
    	return 1;
    }
    
    n->number = 2;
    n->next = NULL;
    
    list->next = n;
    
    n = malloc(sizeof(node));
    if (n == NULL){
    	return 1;
    }
    
    n->number = 3;
    n->next = NULL;
    
    list->next->next = n; // 다음 노드의 다음 노드를 n 포인터로 지정
    
    //list에 연결된 노드를 처음부터 방문해 각 number 값을 출력하고 마지막 노드의 next에는 NULL값이 저장돼 있고,
    //이것이 루프의 종료 조건
    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;
    }
}

 

6-5 연결 리스트: 시연

학생들을 강의장 위로 불러 좀 더 구체적이고 시각적으로 연결리스트에 대해 설명한다.

 

6-6 연결 리스트: 트리

연결리스트를 기반으로 한 새로운 데이터 구조로 트리가 있다. 트리에서 노드들의 연결은 2차원적으로 구성되어 있다. 그림에서 노드가 구성되어 있는 구조를 살펴보면 일정한 규칙을 알 수 있다. 하나의 노드는 두개의 자식 노드를 가지며, 왼쪽 자식 노드는 자신의 값 보다 작고, 오른쪽 자식 노드는 자신의 값 보다 크다. 따라서 이런 트리 구조는 이진 검색을 수행하는데 유리하다. 

 

6-7 해시 테이블

해시 테이블은 연결리스트의 배열이다. 강의에서는 이름표를 정리하는 것을 예로 들어 설명한다. 인덱싱을 하는데 사용하는 배열(강의에서는 이름의 첫글자로 분류한 알파벳 박스들)은 해시 함수라고 부른다.

해시 함수가 이상적이라면 검색 시간은 O(1)이 되지만 그렇지 않다면 최악의 상황에는 O(n)이 될 수도 있다.

 

 

6-8 트라이

트라이는 트리 형태의 자료 구조이다. 특이한 점은 각 노드가 배열로 이루어 졌다는 것인데, 예를 들어 알파벳으로 이뤄진 문자열 값을 저장한다고 하면 트라이에서 값을 검색하는데 걸리는 시간은 ‘문자열의 길이’에 의해 한정된다. 일반적으로 이름은 그리 크지 않은 상수값을 가지기 때문에 O(1)이나 마찬가지라고 볼 수 있다. 그러나 사용 되는 메모리 양은 하나의 글자를 저장하기 위해 최소 26배나 되는 메모리를 사용하게 된다.

 

 

6-9 스택, 큐, 딕셔너리

큐: FIFO(First In First Out) 방식. 배열이나 연결 리스트를 통해 구현 가능. 은행에서 줄을 설 때 먼저 줄을 선 사람이 먼저 업무를 처리하게 되는 방식

  

스택: LIFO(Last In First Out) 방식. 배열이나 연결 리스트를 통해 구현 가능. 뷔페에서 접시를 쌓아 뒀을 때 가장 위에 있는 접시를 가장 먼저 들고 나가는 방식. 메일, SNS는 스택구조로 데이터가 쌓인다.

 

딕셔너리: 키와 값이라는 요소로 이뤄져있다. 키에 해당하는 값을 저장하고 읽어오는 것. 학번에 따라 학생이 결정되는 방식이고 일반적으로 해시 테이블과 동일한 개념이라고 볼 수 있으며 키를 어떻게 정의할 것인지가 중요하다.