[CS][CS50] 자료구조 - 트라이 / 스택 / 큐 / 딕셔너리

boostcource
모두를 위한 컴퓨터 과학 (CS50 2019) : David J. Malan
www.boostcourse.org/cs11
실습환경 : CS50 Sandbox & CS50 IDE

모두를 위한 컴퓨터 과학 (CS50 2019)

 

트라이

트라이는 각 노드가 배열로 이루어진 트리 형태의 자료 구조이다.

 

 

예를 들어 알파벳으로 이루어진 문자열 값을 저장한다고 하면 노드들은 a-z 값을 가지는 배열이 된다.

그리고 배열의 각 요소(알파벳)은 다음 층의 노드(a-z 배열)을 가리킨다.

 

아래는 Hermione, Harry, Hagrid 세 문자열을 트라이에 저장한 형태이다.

[출처] 모두를 위한 컴퓨터 과학 (CS50 2019) 6-8

 

트라이에서 값을 검색하는데 걸리는 시간은 문자열의 길이에 의해 한정되기에

일반적으로 시간 복잡도를 O(1)에 가깝다고 계산하며, 해시 테이블과 비교해 빠른 편이다.

하지만 많은 메모리를 사용한다는 단점을 갖고 있다.

 

 

 

---

큐

큐는 값이 아래로 쌓이는 자료 구조이다.

[출처] https://gohighbrow.com/stacks-and-queues/

 

값을 넣고 뺄 때 FIFO 방식을 따른다.

FIFO란 First In First Out, 가장 먼저 들어온 값이 가장 먼저 나감을 의미한다. (선입선출)

 

배열이나 연결 리스트를 통해 구현이 가능하다.

 

 

 

---

스택

스택은 큐와 반대로 값이 위로 쌓이는 자료 구조이다.

[출처] https://gohighbrow.com/stacks-and-queues/

 

값을 넣고 뺄 때 LIFO 방식을 따른다.

LIFO란 Last In First Out, 가장 나중에 들어온 값이 가장 먼저 나감을 의미한다. (후입선출)

 

역시 배열이나 연결 리스트를 통해 구현 가능하다.

 

 

 

---

딕셔너리

딕셔너리는 해시 테이블로 구현할 수 있는 구조로 "키"와 "값" 이라는 요소로 이루어져 있다.

[출처] https://www.datacamp.com/tutorial/python-dictionaries

 

"키"에 해당하는 "값"을 저장하고 읽어오는 형태이기에

"키"를 어떻게 정의할 것인지가 중요하다.

 

앞서 설명한 해시 테이블과 유사하며 키를 해시 함수의 역할로 해석할 수 있다.

 

 

 

---

복습 퀴즈

Q1. 길이가 10인 영어 문자열이 있다. 알파벳으로 이루어진 문자열 값을 저장하는 영어 문자열 트라이에 저장하는 경우 몇 개의 노드를 이어줘야 할까?

답: 10

알파벳을 기준으로 하기 때문에 문자열의 길이 만큼 이어 줄 node의 개수가 존재한다.

 

 

Q2. 값을 넣고 뺄 때 "선입선출" 또는 "FIFO(First In First Out)"의 방식을 따르는 자료구조는?

① 스택(stack)

② 큐(queue)

③ 딕셔너리(dictionary)

④ 트리(tree)

답: ② 큐(queue)

스택은 값을 넣고 뺄 때 후입선출(LIFO)의 방식을 따르는 자료구조이다.

 

 

Q3. 프로그램에 이름과 전화번호를 저장하려는 자료구조를 구현하려고 한다. 이때 반드시 고려해야할 점이 아닌 것은?

① 시간 복잡도

② 공간 복잡도

③ 메모리 주소 표기법

④ 데이터의 양

답: ③ 메모리 주소 표기법

프로그램의 성능을 항상 생각해야하는데, 프로그램의 수행 시간과 기억 공간의 소요량이 그 키워드가 된다. 시간/공간 복잡도와 데이터의 양과 달리 메모리 주소의 표기법은 고려해야 할 점이 아니다.