Today I Learned(TIL) 21.08.03

오늘 공부한 것

• 모두를 위한 컴퓨터 과학(CS50 2019) 챕터6 자료구조
  

오늘 배운 것

• realloc : 메모리를 할당하고 값을 복사함.

• 이미 할당된 메모리의 크기를 조절할 때 임시 메모리를 새로 할당해줘야 하는 이유는?

  • 기존에 사용하고 있던 메모리 뒤에는 다른 데이터들이 담겨 있을 수 있고(공간이 없을 수 있음), 이 상태에서 데이터를 뒤에 더 쓴다면 데이터를 덮어쓰는 일이 발생할 수 있을 수 있다.

• 연결리스트

  • 각 값이 메모리상의 여러 군데 나뉘어져 있더라도 바로 다음 값의 메모리 주소만 기억하고 있다면 여전히 값을 연이어서 읽어들일 수 있다.
  • 각 인덱스의 메모리 주소에서 자신의 값과 바로 다음 값의 주소(포인터)를 저장한다.

    typedef struct node // 구조체 안에서 node를 사용하기 위해서 node를 명시해준다.
    {
       int number; // 각 node가 가지는 값
       struct node *next; // 다음 node를 가리키는 포인터
    }
    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를 추가하거나 삭제할 경우에(ex.1,2,4 사이에 3을 넣는 경우)
      3이 4를 먼저 가리키고 난 후 2가 3을 가리켜야 한다.

• 연결리스트 : 트리

  

  • 위 그림에 묘사된 트리는 이진 검색 트리
    - 하나의 노드는 두 개의 자식 노드를 가진다.
    - 왼쪽 자식 노드는 자신의 값 보다 작고, 오른쪽 자식 노드는 자신의 값보다 크다.
  • 이진 검색 트리가 기본 연결 리스트에 비해 가지는 장점과 단점
    - 장점 : 이진 검색 트리의 시간 복잡도는 O(log n)이므로 O(n)인 기본 연결 리스트에 비해 유리하다.
    - 단점 : 계속하여 한 노드에만 값을 추가하면 균형이 무너져서 이진 검색의 장점을 살리기 어렵고, 노드 하나 당 두개의 노드를 가리켜야 하기 때문에 메모리 사용량이 더 많다.

• 해시 테이블 : 연결 리스트의 배열(ex. 사람의 이름)

• 해시 함수 : 맞춤형 함수(ex. 이름의 가장 첫 글자)

• 트라이 : 트리형태의 자료 구조로 각 노드가 '배열'로 이루어져 있음.

  • 장점 : 트라이는 O(m)의 시간 복잡도를 보장하여(m=문자열 길이, 보통 상수) 해시 테이블에 비해 빠르다.
  • 단점 : 각 노드가 배열을 가져 아주 많은 메모리를 필요로 한다.

• 큐 (배열, 연결리스트)

  • 값이 아래로 쌓이는 구조
  • FIFO(First In Fist Out) : 선입선출, 가장 먼저 들어온 값이 가장 먼저 나간다.

• 스택 (배열, 연결리스트)

  • 값이 위로 쌓이는 구조
  • LIFO(Last In Fist Out) : 후입선출, 가장 나중에 들어온 값이 가장 먼저 나간다.

• 딕셔너리

  • '키'와 '값'이라는 요소로 이루어져 있음.
  • 일반적인 의미에서 '해시 테이블'과 동일한 개념.
  • '키'를 어떻게 정의할 것인지가 중요.

---

내일 할 일

• 드림코딩 by 엘리 자바스크립트 기초 강의