강좌 : 부스트캠프 모두를 위한 컴퓨터과학(cs50 2019)
4. 자료구조
- ide.cs50.io 사이트 이용
✍해시테이블
- 배열과 연결리스트를 조합한 것
- 각 값들은
해시함수라는 맞춤형 함수를 통해서 어떤 바구니에 담기는 지가 결정
해시함수
- 해시함수가
이름의 가장 첫 글자인 경우 알파벳 개수에 해당하는 26개의 포인터들이 있을 수 있으며 각 포인터는 그 알파벳을 시작으로 하는 이름들을 저장하는 연결리스트를 가리키게 된다 - 만약 해시함수가 이상적이라면 각 바구니에는 단 하나의 값들만 담기게 되고 검색시간은
O(1)이 된다 - 그렇지 않을 경우 해시충돌로 인해 단 하나의 바구니에 모든 값들이 담겨
O(n)이 될 수도 있다
✍트라이
트리형태의 자료구조- 각 노드가
배열로 이루어져 있다 - 값을 검색하는데 걸리는 시간은
문자열의 길이에 의해 한정 - 일반적인 영어 이름의 길이를 n이라고 했을 때 검색시간은
O(n)이 되지만, 대부분의 이름은 그리 크지 않은 상수값이기 때문에O(1)이나 마찬가지 - 해시테이블에 비해 탐색시간이 빠르지만 각 노드가 배열을 가지고 있기 때문에 많은 메모리가 필요
✍스택, 큐, 딕셔너리
스택
- 값이 위로 쌓이는 구조
- 갑을 넣고 뺄 때
후입 선출즉LIFO방식 - push(입력) pop(출력)
큐
- 값이 아래로 쌓이는 구조
- 값을 넣고 뺄 때
선입 선출즉FIFO방식 - enqueue(입력) dequeue(출력)
딕셔너리
- 해시테이블과 동일한 개념
키와값이라는 요소로 이루어짐
코린이