CS50강 6강 자료구조

배열의 크기 조정하기

 

현재 배열 저장된 메모리 바로 옆에 이미 다른 데이터가 저장되어 있을 가능성 높음.

때문에 새로운 공간에 더 큰 크기 메모리 다시 할당한 후, 배열의 값을 하나씩 옮겨줘야 함.

+이전 메모리 해제

 

realloc 함수

ex) int *tmp = realloc(list, 4 * sizeof(int));

---

연결 리스트

 

데이터 구조, 자료구조 : 컴퓨터 메모리를 더욱 효율적으로 관리하기 위해 새로 정의하는 구조체(struct)

일종의 메모리 레이아웃.

 

연결 리스도 자료구조 중에 하나.

값과 함께 다음 값의 주소(포인터)를 저장함.

연결 리스트 정의 방법.

 

typedef struct node

{

   int number;

   struct node* next;

}

node

 

연결 리스트의 장단점

 

장점: 값을 옮기거나 복사하지 않고 배열의 크기 조절 가능.

단점: 임의 접근법을 할 수 없음.

 

search, input : O(n)

---

트리

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

연결리스트는 1차원적 노트 연결

트리는 2차원적 노드 연결. 각 노드에 포인터 2개 씩

 

typedef struct node

{

     int number;

     struct node *left;

     struct node *right;

}

node;

 

이진 탐색 트리 가능. (재귀)

다시 말해 메모리를 조금 더 사용(포인터 2개)함으로써 search, input을 다시 O(log n) 수준으로 내릴 수 있는 것.

 

---

해시 테이블

해시 테이블 : 연결리스트들의 배열.

해시 함수 : 어떤 값들이 배열에 어떻게 담길지 결정하는 맞춤형 함수

 

이상적인 해시 함수의 경우, 각 칸에 하나의 값만 담김.

search time =  O(1)

하지만 최악의 경우 단 하나의 칸에 모든 값들이 담겨 O(n)이 될 수 있음.

 

일반적으로 해시 함수를 고안하는 데 많은 노력을 들여 거의 O(1)에 가깝게 구현함.

---

트라이 (검색 'retrieval'의 줄임말)

트라이 : 각각의 노드가 배열로 이루어진 트리

 

 

search, insert : 상수 시간 O(1)

대신 기본적으로 메모리가 많이 듦. 저장하는 값 많아질 수록 (마치 경제학의 규모의 경제처럼) 효율적이게 되는 지도. 

---

큐, 스택, 딕셔너리

 

큐(queue) : FIFO (First In First Out, 선입선출)의 자료구조.

- enqueue 

- dequeue

 

스택(stack) : 식당 쟁반. FIFO 가 아니라, LIFO(Last In First Out, 후입선출)의 자료구조.

ex) Gmail 메일박스 (항상 최신 메일을 먼저 볼 수 있게)

- push

- pop

 

딕셔너리 : 해시테이블.키-값, 단어-값, 단어-페이지 넘버 등 다양한 쌍으로 이루어진 자료 구조.