[Data] 자료 구조란?(4) : 추상 자료형, 리스트, deque, 큐, 스택, 딕셔너리, 세트, 해시 테이블

 

 

💡 추상 자료형 Abstract Data Type

먼저 기능과 구현의 차이에 대해 알아보자.

• 기능 : 연산이 '무엇'을 하는지에 관한 내용
• 구현 : 기능을 ' 어떻게' 하는지에 관한 내용

삽입 연산 insert operation 의 기능과 구현은 뭘까?

• 삽입 연산 기능 : 순서 데이터에서 원하는 위치에 데이터를 저장
• 삽입 연산 구현
  • 동적 배열 삽입 : 데이터를 메모리에 순서대로, 연속적으로 저장하기에 중간에 삽입할 경우 데이터를 한 칸씩 미뤄서 저장
  • 링크드 리스트 삽입 : 더블리 링크드 리스트는 각 노드가 앞, 뒤 노드에 대한 레퍼런스를 저장해 순서를 유지하기에 앞 뒤 레퍼런스를 수정해 저장

그럼 추상화란?

• 추상화 : 구현을 몰라도 기능만 알면 사용할 수 있게 해주는 것, 추상화를 하면 이미 쓴 코드를 재활용하고 협력하기 쉬워진다.
• 추상 자료형 : 자료 구조를 추상화한 것, 데이터를 저장/사용할 때 기능만 생각 ↔️ 자료 구조(구현까지 생각)
• 자료 구조 대신 먼저 추상 자료형을 생각하면 코드의 흐름에 집중할 수 있다. 큰 틀에 먼저 집중!

추상 자료형 ➡️ 핸드폰 : 휴대가 편하고 전화가 가능한 기계

자료 구조 ➡️ 아이폰 16 pro : 특정 방식에 의해 전화, 문자를 보내거나 받을 수 있는 핸드폰

 

추상 자료형 ➡️ 리스트 : 데이터간 순서 관계 유지와 접근/탐색/삽입/삭제 연산이 가능한 추상 자료형

자료 구조 ➡️ 동적 배열 : 데이터를 메모리에 순서대로 그리고 연속적으로 저장, 특정 방식으로 접근/탐색/삽입/삭제 연산을 수행

 

추상 자료형 VS 자료 구조, 어떤 게 더 중요한가?

그저 서로 다른 개념일 뿐 더 중요한 것은 없다.

기능을 중점적으로 얘기하고 싶거나, 흐름을 생각할 때와 같이 구현에 집중할 필요가 없을 땐 추상 자료형을,

코드의 성능을 분석하거나 최적화 시켜야 될 때, 성능을 끌어올려야할 때, 자료 구조를 중심적으로 생각하면 된다.

 

❗️자료 구조 A 를 추상 자료형 B 로 사용할 수 있을 때 A 로 B 를 구현할 수 있다고 말한다.

 

💡 리스트 List  : 데이터 간 순서를 유지하는 추상 자료형

파이썬의 리스트는 내적으로 동적 배열로 구현되어 있다.

더블리 링크드 리스트와 시간 복잡도를 비교해보자.

	동적 배열	e.g.	더블리 링크드 리스트
접근	O(1)	lst[0], lst[0] = 5	O(n)
탐색	O(n)	'a' in lst	O(n)
길이 확인	O(1)	len(lst)
접근 + 삽입	O(n)	lst.insert(3, 'c')	O(n)
접근 + 삭제	O(n)	lst.pop(3)	O(n)
맨 앞 삽입	O(n)	lst.insert(0, 'a')	O(1)
맨 앞 삭제	O(n)	del lst[0] lst.pop(0)	O(1)
맨 뒤 삽입	분할 상환 O(1)	lst.append(2)	O(1)
맨 뒤 삭제	분할 상환 O(1)	lst.pop()	O(1)

 

➡️ 접근을 많이 한다면 동적 배열을, 맨 앞이나 맨 뒤 데이터에 관한 연산을 많이 한다면 더블리 링크드 리스트를 사용하는 것이 효율적이다.

 

💡 큐 Queue : 데이터 간 순서를 유지하는 추상 자료형

FIFO First In First Out

• 계산대 대기줄처럼(계산한 앞 사람이 사라짐) 데이터를 삭제할 땐 맨 앞, 삽입할 땐 맨 뒤에서만 삽입을 한다.
• 가장 먼저 들어온 데이터가 가장 먼저 삭제된다.

대표적인 세 개의 연산

• 맨 뒤 데이터 추가
• 맨 앞 데이터 삭제
• 맨 앞 데이터 접근

파이썬에선 deque 라는 자료형을 사용해 큐를 사용할 수 있다.

양면 큐 Double ended queue

• 맨 앞과 뒤에 데이터를 삽입하고 삭제할 수 있게 해주는 자료형

from collections import deque

queue = deque()

# 큐의 맨 뒤에 데이터 삽입
queue.append("a")
queue.append("b")

print(queue) # deque(["a", "b"])

# 큐의 맨 앞 데이터에 접근
print(queue[0]) # "a"

# 큐의 맨 앞 데이터 삭제
print(queue.popleft()) # "a" 삭제한 데이터 리턴
print(queue) # deque(["b"])

 

리스트와 마찬가지로 큐는 동적 배열과 링크드 리스트로 구현할 수 있다.

두 자료 구조 모두 데이터간 순서 유지가 가능하고, 특정 위치의 데이터에 접근하거나 삽입/삭제할 수 있기 때문

어떤 자료 구조가 큐 구현에 효율적일지 비교해 보자.

	동적 배열	더블리 링크드 리스트	e.g.
맨 앞 삭제	O(n)	O(1)	queue.popleft()
맨 뒤 삽입	분할 상환 O(1)	O(1)	queue.append('f')
맨 앞 접근	O(1)	O(1)
맨 앞 삽입		O(1)	queue.appendleft('a')
맨 뒤 삭제		O(1)	queue.pop()
길이 확인		O(1)	len(queue)

 

➡️ 더블리 링크드 리스트로 구현하는 것이 더 효율적

파이썬의 deque 도 내부적으론 더블리 링크드 리스트로 구현되어 있다.

 

💡 스택 Stack : 큐/리스트와 마찬가지로 데이터 간 순서를 유지하는 추상 자료형

stack : 물건이 차곡차곡 쌓여 있는 것

LIFO Last In First Out

• 쌓아 놓은 접시처럼 데이터를 삭제할 때도 맨위, 삽입할 때도 맨 위에서만 삽입을 한다.
• 가장 마지막에 들어온 데이터가 가장 먼저 삭제된다.

대표적인 세 개의 연산

• 맨 뒤 데이터 추가
• 맨 뒤 데이터 삭제
• 맨 뒤 데이터 접근

큐와 마찬가지로 파이썬 deque 자료형을 사용해 스택을 사용할 수 있다.

from collections import deque

stack = deque()

# 스택의 맨 뒤에 데이터 삽입
stack.append("a")
stack.append("b")
stack.append("c")

print(stack) # deque(["a", "b", "c"])

# 스택의 맨 뒤 데이터에 접근
print(stack[-1]) # "c"

# 스택의 맨 뒤 데이터 삭제
print(stack.pop()) # "c" 삭제한 데이터 리턴
print(stack.pop()) # "b" 삭제한 데이터 리턴
print(stack) # deque(["a"])

 

큐/리스트와 마찬가지로 스택은 동적 배열과 링크드 리스트로 구현할 수 있다.

둘 중 어떤 자료 구조를 사용하는게 효율적인지 알아보자.

	동적 배열	더블리 링크드 리스트
맨 뒤 삭제	분할 상환 O(1)	O(1)
맨 뒤 삽입	분할 상환 O(1)	O(1)
맨 뒤 접근	O(1)	O(1)

 

➡️ 두 자료 구조 모두 O(1) 의 시간 복잡도로 아무 자료 구조나 사용해도 상관이 없다.

stack = []
# 리스트를 사용해도 위 예시와 같다.

 

💡 딕셔너리 Dictionary (= Map): 데이터간 순서 관계를 약속하지 않은 추상 자료형

대표적인 세 개의 연산

• key - value 데이터 쌍 삽입
• key 를 이용한 데이터 탐색
• key 를 이용한 데이터 삭제

dic = {}

# key - value 데이터 삽입
dic['a'] = 10
dic['b'] = 20
dic['c'] = 30
dic['d'] = 40
dic['e'] = 50

print(dic) # {'a': 10, 'b': 20, 'c': 30, 'd': 40, 'e': 50}

# 한 key 에 여러 value 를 저장하면?
dic['b'] = 200
print(dic) # {'a': 10, 'b': 200, 'c': 30, 'd': 40, 'e': 50}

# key 를 이용해 value 탐색
print(dic['a']) # 10
print(dic['c']) # 30

# key 를 이용한 삭제
dic.pop('a')
dic.pop('c')

print(dic) # {'b': 20, 'd': 40, 'e': 50}

 

딕셔너리를 구현할 수 있는 자료 구조, 해시테이블(파이썬 딕셔너리도 해시테이블을 이용해 구현되어 있다.)

	해시 테이블	e.g.
key - value 쌍 삽입	O(1)	dic['f'] = 60
key 를 이용한 탐색	O(1)	dic['a']
key 를 이용한 삭제	O(1)	del dic['a'] dic.pop('a')
길이 확인	O(1)	len(dic)

 

💡 세트 Set : 데이터간 순서 관계를 약속하지 않은 추상 자료형

대표적인 세 개의 연산

• 삽입 : 데이터 저장 가능 (중복 데이터 ❌)
• 탐색 : 데이터가 저장되었는지 확인 간으
• 삭제 : 데이터 삭제 가능

set_lst = set()

# 데이터 저장
set_lst.add('a')
set_lst.add('b')
set_lst.add('c')
set_lst.add('d')
set_lst.add('e')

print(set_lst) # {'a', 'b', 'e', 'c', 'd'}

# 중복 데이터를 저장하면?
set_lst.add('a')
set_lst.add('b')

print(set_lst) # {'a', 'b', 'e', 'c', 'd'}

# 데이터 탐색
print('f' in set_lst) # False
print('a' in set_lst) # True

# 데이터 삭제
set_lst.remove('a')
set_lst.remove('c')

print(set_lst) # {'b', 'e', 'd'}

 

세트도 딕셔너리와 마찬가지로 주로 해시테이블을 이용해 구현한다.

하지만 해시테이블은 key - value 를 저장하는 자료 구조인데?

➡️ 인덱스에 key 만 저장해 세트 구현

	해시 테이블	e.g.
삽입	O(1)	set_lst.add('f')
탐색	O(1)	'a' in set_lst
삭제	O(1)	set_lst.remove('a') set.pop('a')
길이 확인	O(1)	len(set_lst)

 

✨ 파이썬 자료형을 잘 고른다는 것

리스트와 세트로 데이터를 탐색했을 때의 시간을 비교해 보자.

# List
# 예시를 위해 사용할 모듈 import
import time

# 데이터 List 에 저장
test_list = [x for x in range(0, 1000000)]

# 특정 항목이 List 에 있는지 확인할 때 걸리는 시간 파악
t_0 = time.time()
999999 in test_list # List 탐색
t_1 = time.time()

print(f"List 에서 특정 항목을 찾는데 걸린 시간: {t_1 - t_0}")
# List 에서 특정 항목을 찾는데 걸린 시간: 0.013087987899780273

# Set
# 데이터 Set 에 저장
test_set = set([x for x in range(0, 1000000)])

# 특정 항목이 Set 에 있는지 확인할 때 걸리는 시간 파악
t_0 = time.time()
999999 in test_set
t_1 = time.time()

print(f"Set 에서 특정 항목을 찾는데 걸린 시간: {t_1 - t_0}")
# Set 에서 특정 항목을 찾는데 걸린 시간: 3.0994415283203125e-06

	파이썬 리스트(동적 배열)	파이썬 세트(해시 테이블)
탐색 연산	O(n)	O(1)

 

➡️ 자료형을 잘 고른다는 것은 현재 자신이 데이터에 하고 싶은 연산들이 뭐가 있고 얼마나 걸릴지에 대해 잘 생각하는 것이다.

쓰려는 연산의 시간 복잡도를 고려해 효율적인 자료형을 선택할 수 있어야 한다.