[자료구조] 추상자료형 (ft. 큐, 스택, 딕셔너리, 세트)

기능 : '무엇'을 하는지 (자료구조마다 하는 일은 같다.)

구현 : 그 '무엇'을 어떻게 (자료구조마다 다르다.)

 

추상 자료형이란 자료구조를 추상화하여 표현한 것으로서, 구현보다는 기능에만 초점을 맞춘 것이다.

ex) 리스트는 접근, 탐색, 삽입, 삭제의 기능이 있는 추상 자료형이다.

 

이를 '구현'하는 것에는 앞서 배운 동적 배열이나 링크드 리스트가 있다.

 

자료구조를 통해 복잡하게 생각하는 것보다는 기능에만 초점을 맞춘 추상화 자료를 떠올린다면, 보다 코드의 흐름을 이해하기 쉬워진다는 것이 추상자료형의 핵심가치이다. (물론 코드의 성능을 분석, 최적화할 때는 자료구조를 떠올려야 한다.)

---

구현할 때 동적 배열을 사용할 것인가? 링크드 리스트를 사용할 것인가?

 

동적 배열은 접근이 O(1)이지만 링크드 리스트는 O(n)이다.

링크드 리스트는 맨 앞과 맨 뒤에 삽입, 삭제하는 과정이 O(1)이지만 동적 배열은 O(n)이다.

장점과 단점이 각각 존재한다. 따라서 어떤 연산을 많이 수행할지에 따라 사용할 자료구조가 달라진다.

 

cf. 파이썬에서 리스트는 동적 배열을 사용하고 있다.

큐(Queue)

가장 먼저 들어온 데이터가 가장 먼저 삭제되는 FIFO(First In, First Out) 형식의 추상 자료형이다.

 

큐가 가져야 하는 기능에는 '맨 앞 데이터 접근', '맨 앞 데이터 삭제', '맨 뒤 데이터 추가'가 있다.

cf. 파이썬에서는 deque로 큐를 사용할 수 있다. deque란 doubley-ended-queue의 의미이다.

from collections import deque
a = deque()
a.append()
a.popleft()

from collections import deque로 불러오고, append, popleft 등을 사용할 수 있다.

 

큐 역시 동적 배열과 링크드 리스트로 구현이 가능한데, 큐는 주로 맨 앞과 맨뒤의 삽입 삭제 접근을 많이 다루고 있으니 더블리 링크드 리스트가 유리하다. (모두 O(1)의 시간 복잡도를 가진다.)

 

cf. 파이썬 deque는 더블리 링크드 리스트로 구현되어 있다.

스택(Stack)

가장 마지막에 들어온 데이터가 가장 마지막에 삭제되는 LILO(Last In Last Out) 방식의 추상 자료형이다.

 

맨 뒤의 데이터에만 접근, 추가, 삭제가 가능하면 된다. 따라서 스택을 만들 때는 링크드리스트를 사용해도 괜찮고 동적 배열을 사용해도 괜찮다. 맨 뒤 데이터에 접근(추가, 삭제)하는 동작의 시간 복잡도는 어차피 두 자료구조 모두 O(1)이기 때문이다.

딕셔너리(dictionary)

데이터 간의 순서는 존재하지 않는다. key-value 데이터 쌍을 넣을 수 있고, key을 이용한 데이터 접근(탐색, 삭제)이 가능한 추상 자료형이다.

 

해시 테이블을 통해 만드는 것이 적절하다. key와 value를 모두 가지고 있고, 접근 및 탐색, 삭제 그리고 삽입의 연산에서 시간 복잡도가 모두 O(1)이기 때문이다.

 

cf, 파이썬에서는 dic = {}와 같이 생성 가능하다.

세트(Set)

데이터 간의 순서는 존재하지 않는다. 단, 중복이 존재해선 안된다. 그 외엔 삽입, 탐색, 삭제의 기본적인 기능이 존재하는 되는 추상 자료형이다.

 

해시 테이블을 조금 변경해서, key로만 저장해서 사용한다. key만 저장한다면 value값이 존재하지 않기 때문에 데이터의 중복도 자연스럽게 방지될 수 있다.

 

cf. 파이썬에서는 st = set()와 같이 생성 가능하다.

시간 복잡도 정리

리스트 (동적 배열)

접근	O(1)
추가	O(1) (분할 상환)
맨 뒤 삭제	O(1) (분할 상환)
길이 확인	O(1)
삽입	O(n)
삭제	O(n)
탐색	O(n)

 

deque (더블리 링크드 리스트)

맨 앞 삭제	O(1)
맨 앞 삽입	O(1)
맨 뒤 삭제	O(1)
맨 뒤 삽입	O(1)
길이 확인	O(1)

 

딕셔너리 (해시 테이블)

탐색	O(1) (평균)
삽입	O(1) (평균)
삭제	O(1) (평균)
길이 확인	O(1)

 

세트 (해시 테이블)

탐색	O(1) (평균)
삽입	O(1) (평균)
삭제	O(1) (평균)
길이 확인	O(1)

---

자료구조를 잘 선택하는 것은 매우 중요하다. 파이썬에서 리스트는 범용성이 높아 다른 자료형을 사용해도 되는데 그냥 리스트를 사용하는 경우가 많다. 하지만 리스트와 세트에 둘 다 1~100000까지의 수를 넣고, 99999를 찾으려고 하면

리스트는 동적 배열을 사용하기 때문에 탐색 시간이 오래 걸리지만 세트는 해시 테이블을 사용하기 때문에 탐색 시간이 오래 걸리지 않는다.

 

적은 양의 데이터를 다룰 땐 괜찮지만, 데이터 양이 많아질수록 이 차이는 극명하게 드러난다.

---