자료구조 | 덱(Deque), 해시테이블(Hashtable), 셋(Set) 추상 자료형

자료구조, 나한테 설명하며 공부해보자!

 

정성스러운 손 필기 ✍🏻 (클릭)

 

자료구조 - 덱(Deque)

데이터 삽입, 제거를 head, tail 2군데에서 자유롭게 할 수 있는 자료구조.

(스택, 큐의 특성이 합쳐졌다고 생각하면 된다.)

 

덱의 추상 자료형(JS)

추상 자료형(Abstract Data Type)?

구현하고자 하는 구조의 구체적 기능의 진행 과정을 언급하는 것이 아닌, 데이터의 연산 기능을 표기하는 것
(규칙의 나열이라고 보면 이해하기 쉽다)

예) 세탁기 : 탈수..

 

 

추상자료형	설명
printAll()	1. 테스트를 위해 리스트 모든 요소 출력
addFirst()	2. 리스트의 head에 데이터 삽입
removeFirst()	3. 리스트의 head에서 데이터 제거
addLast()	4. 리스트의 tail에 데이터 삽입
removeLast()	5. 리스트의 tail에서 데이터 제거
isEmpty()	6. 리스트가 비었는지 알려주기

 

스택과 큐의 특성이 합쳐졌기 때문에, 이 특성을 이용하면

덱으로 스택, 큐를 구현할 수도 있다.

 

stack 구현 : 데이터를 한 방향에서만 추가/제거한다 = 추상 자료형 2+3, 4+5로 구현

queue 구현 : 데이터를 한쪽으로만 흐르게 한다 = 추상 자료형 2+5, 3+4로 구현

 

 

자료구조 - 해시 테이블(Hashtable)

- Hash(함수) + Table

프로그래밍 언어에 따라 이름이 조금씩 다르다. (해시, 맵, 해시 맵, 딕셔너리 등)

 

- 표 (Table)

어떤 내용을 일정한 형식, 순서에 따라 나타낸 것

배열로 정리한다고 생각했을 때, 사전에 많은 공간을 마련해둬야 하고, 빈 공간이 생겨 메모리가 낭비될 수 있다.

 

인덱스(index)	데이터(value)
0
1	데이터
...
11	데이터
...

 

- 해시함수

특정 계산을 통해 표(table)의 메모리 낭비를 줄인다.

 

예) 위의 table 값을 10으로 나눈 나머지라는 해시함수를 이용해 새로운 표(table)를 구현해보자.

 

- Hashtable 구현

key(인덱스)만 알면 value(데이터)에 O(1)의 성능으로 읽기/삽입/수정/삭제가 가능하다.

데이터를 해시함수를 이용해서 인덱스에 맞게 정리를 하다 보니,

동일한 인덱스에 여러 자료를 넣어야 하는 데이터 충돌이 생길 수 있다.

 

예) 나머지가 같은 경우는 같은 인덱스에 어떻게 담을 것인가?

 

인덱스(key)	데이터(value)
0	(낭비)
1	충돌!!!
...
9	데이터

 

데이터 충돌을 막기 위해, 인덱스는 "연결 리스트"로 저장한다.

즉, 같은 인덱스에 담아야 하는 데이터는 덮어쓰는 것이 아닌 연결 리스트로 연결해두는 것이다.

 

해시 테이블은 데이터 참조를 위해

1) 해시함수를 거친 후

2) 연결 리스트를 뒤져 데이터를 참조한다. O(n)의 성능을 갖는다.

 

- 해시 테이블의 장점

 : 빠른 데이터 탐색, 삽입, 삭제가 가능하다.

- 해시 테이블의 단점

 : 메모리 낭비가 발생할 수 있다. 좋은 해시함수 구현이 필수적이다.

 

해시 테이블은, 데이터를 골고루 분배해주는 좋은 해시함수 구현이 대단히 중요하다.

(해시함수에 따라 한 쪽으로 데이터가 몰리게 되면 공간 낭비가 극대화되기 때문)

 

 

해시 테이블의 추상 자료형(JS)

추상 자료형(Abstract Data Type)?

구현하고자 하는 구조의 구체적 기능의 진행 과정을 언급하는 것이 아닌, 데이터의 연산 기능을 표기하는 것
(규칙의 나열이라고 보면 이해하기 쉽다)

예) 세탁기 : 탈수..

 

추상자료형	설명
set()	1. 해시테이블에 데이터 삽입
get()	2. 해당 key의 value 읽기
remove()	3. 해당 key의 value 제거

 

 

자료구조 - 셋(Set)

- 데이터 중복을 허용하지 않는 자료구조

중복을 하면 안 되는 값을 저장하고 싶을 때 이용한다.

해시 테이블을 이용하기 때문에 해시 셋(Hash Set)이라고도 불린다.

 

해시 테이블의 value 값을 사용하지 않고, key만 사용해서 구현한다.

key가 key 이면서 data라고 생각하면 된다.

 

셋의 추상 자료형(JS)

추상 자료형(Abstract Data Type)?

구현하고자 하는 구조의 구체적 기능의 진행 과정을 언급하는 것이 아닌, 데이터의 연산 기능을 표기하는 것
(규칙의 나열이라고 보면 이해하기 쉽다)

예) 세탁기 : 탈수..

 

추상자료형	설명
add(data)	1. 셋에 데이터 추가(삽입)
isContain(data)	2. 셋에 데이터가 있는지 체크 (있으면 true, 없으면 false 리턴)
remove(data)	3. 데이터 제거 (제거할 data를 매개변수로 이용) (= 해시테이블의 key를 제거한다)
clear()	4. 셋 비우기
isEmpty()	5. 셋 비었는지 검사
printAll()	6. 테스트 위해 셋의 모든 데이터 출력

 

 

다음 시간은 알고리즘 - 재귀(recursion)에 대해 알아보자

:D