컴퓨터과학 CS50 2020 Lecture 5 : Data Structures

 

 

 

stack of swearters, plates. Eng

욕설, 접시 더미.

 

{"mean":["<dicbridgeLine>","오픈","<dicbridgeLine>","예제","<dicbridgeLine>","VLIVE 자막"],"word":"stack of swearters plates","basicWord":"stack of swearters plates","soundWord":"stack of swearters plates","phoneticSymbol":""}

<강의 필기>

 

 

 

data structure

struct
사용자가 정의한 데이터 유형을 만든다.

 

.

데이터 구조의 속성에 접근한다.

specific variable를 다룬다.

dot operator

*

메모리 구조 안의 pointer가 가리키는 particular address로 향한다.

asterisk

 

->

메모리 구조 안의 pointer가 가리키는 속성에 접근한다.

 

 

 

 

linked list

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

first chunk of memory = data
second chunk of memory = next data address
null = absence of adress
second chunk에 주소를 저장하는 것은 메모리의 낭비인가?

 

각 요소마다 2배의 메모리를 할당한다.

pointer를 따라 접근하기 때문에 pointer를 저장할 공간이 필요하기 때문이다.

 

 

 

 

node *list = null
list는 null에서 시작된다.
list->next->next = n;으로 iterate하는 과정을 거친다.
list = first node(variable + next address info) + second node(variable + next address info)

 

연결 리스트의 크기가 n 일때 그 실행 시간은 O(n)이 된다.
배열과 비교해서 연결 리스트는 새로운 값을 추가할 때 다시 메모리를 할당하지 않아도 된다는 장점이 있다.

다음 메모리 주소를 변경하지만 하면 된다.

 

 

...
list[0] = 1;
list[1] = 2;
list[2] = 3;
...
int *tmp = malloc(4 * sizeof(int));
...
list = tmp;

 

int 자료형 4개 크기의 tmp 라는 포인터를 선언하고 메모리를 할당한다.

 

 

 

 

binary search tree

typedef struct node
{
    int number;
    struct node *left;
    struct node *right;
}
node;

왼쪽과 오른쪽 방향이 Boolean logic으로 나뉘는 일정한 pattern이 있다.

 

 

Source :&nbsp;Wikipedia

 

running time이 O(logn)이라서 기본 linked list의 O(n)보다 빠른 편이다.
O(logn), O(n), O(n^2) 등 different cateogries of running times을 파악하는 것은

알고리즘의 효율성을 고려할 때 도움이 된다.

 

 

 

hash table
linked lists의 arrray이다.
변수가 속한 location을 따라 찾아간다.
예를 들면 First Letter가 H인 Location에 속한 변수가 있다.
Ha. Hb. Hc. Hd. He. Hf 등 여러 변수가 있다.
Hermione에서 시작하여 Harry와 Hagrid로 연결짓는 방법이 있다.

 

Source :&nbsp;Wikipedia

 

 

Card Deck으로 생각하면 된다.
Space. Diamond. Heart. Clover인 Location에서 13 particular card가 있다.

 

Source :&nbsp;Wikipedia

 

running time은 O(1)이다.

 

 

 

trie

여러 array로 구성된 tree 구조이다.
H location에서 새로운 노드 A, G, R, I, D를 더한다.

H-A-G-R-I-D로 Pointer가 구성된다.

 

 

Source :&nbsp;Wikipedia

 

running time은 이름의 길이에 따라 비례한다.

작업시간은 O(1)로 빠른 편이지만

많은 pointers와  boolean values를 저장해야 하는 memory 용량의 문제가 있다.

 

 

queue and stack

values를 copy할 때 그만큼의 공간이 필요하다.

사람들이 들어올 때 공간이 꽉차면 안에 있던 사람들이 뒤로 물러난다.

힐베르트 호텔이라는 가상의 공간에서는 무수히 많은 방이 있는 호텔에 손님이 가득 차 있을 때는

몇 명의 손님이 더 오더라도 손님들의 방을 재배열하여 새로운 손님이 투숙할 공간을 마련할 수 있다.

 

queue
FIFO(First in. First out) : 먼저 enqueue한 것이 먼저 dequeue 한다.

줄을 먼저 선 사람이 먼저 입장하는 것과 같다.

 

Source :&nbsp;Wikipedia

 

 

stack
LIFO(Last in. First out.) : 마지막에 push한 것이 먼저 pop한다.
옷장에서 스위터를 쌓는 것과 식당에서 접시를 쌓는 것과 같다.

 

Source :&nbsp;Wikipedia

 

 

 

 

 

dictionary
section 안에 element가 있다.

key - value mapping을 한다.

Source : Medium The Fellow

 

 

 

강의 자료

Week 4 - CS50

 

 

 

 

 

CS50 Sandbox 

CS50 Sandbox

 

 

 

 

Jack Learns the Facts About Queues and Stacks

 

 

 

Python Dictionaries

Python Dictionaries

 

 

 

힐베르트 호텔

힐베르트 호텔 - 위키백과, 우리 모두의 백과사전