추상 자료형

1. 기능 vs 구현

기능(Design)

• 연산이 무엇을 하는지에 관한 내용

구현(implementation)

• 기능을 어떻게 하는지에 대한 구체적 설명

2. 추상화

추상화(Abstraction)

• 구현을 몰라도 기능만 알면 사용할 수 있게 해주는 것

추상 자료형(abstract data type)

• 추상화한 자료 구조
• 기능만으로 데이터를 다룰 수 있게 해준다.
• 추상 자료형을 구현할 수 있는 자료 구조는 여러 가지이다.
• 프로그램의 큰 틀을 짤 때, 자료 구조 대신 추상 자료형을 먼저 생각하면 코드의 흐름에 집중할 수 있다.

3. 리스트 개념

List

• 데이터 간 순서를 유지해 주는 대표적인 추상 자료형
• 접근, 탐색, 삽입, 삭제 연산 기능을 가지고 있어야 한다.

list (Python)

# 파이썬 리스트 생성
trending = []

# 특정 위치에 데이터 삽입
trending.insert(0, "연예인 A씨")
trending.insert(1, "잠실 콘서트")
trending.insert(2, "한국 휴일 ")
trending.insert(2, "추석 음식")

# 리스트 출력
print(trending)

# 괄호를 이용한 인덱스 접근
print(trending[0])
print(trending[1])

# 괄호와 지정 연산자를 이용한 데이터 수정
trending[2] = 4

print(trending)

# in을 이용한 탐색
print("연예인 A씨" in trending)
print("연예인 B씨" in trending)

# del을 이용한 삭제
del trending[0]

print(trending)

['연예인 A씨', '잠실 콘서트', '추석 음식', '한국 휴일 ']
연예인 A씨
잠실 콘서트
['연예인 A씨', '잠실 콘서트', 4, '한국 휴일 ']
True
False
['잠실 콘서트', 4, '한국 휴일 ']

5. 리스트 구현

동적 배열과 더블리 링크드 리스트의 시간 복잡도

리스트 구현

• 자주 사용하게 될 연산의 시간 복잡도를 기준으로 구현에 사용할 자료 구조를 정하면 된다.
• Python은 동적 배열로 list를 구현했다.

6. 큐 개념

큐(Queue)

• 데이터 간 순서를 유지해 주는 추상 자료형
• 먼저 저장된 데이터가 먼저 나오는 FIFO(First in First Out) 구조이다.
• 맨 뒤 데이터 추가, 맨 앞 데이터 삭제, 맨 앞 데이터 접근 연산을 할 수 있어야 한다.

deque (Python)

• doubly-ended-queue의 약자
• 맨 뒤 데이터 삭제 연산을 지원한다.

# deque는 파이썬 collections 모듈에서 가지고 온다
from collections import deque

# 파이썬 큐 생성
queue = deque()

# 큐의 맨 뒤에 데이터 삽입
queue.append("태호")
queue.append("현승")
queue.append("지웅")
queue.append("동욱")
queue.append("신의")

print(queue)  # 큐 출력

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

# 큐의 맨 앞 데이터 삭제
print(queue.popleft())
print(queue.popleft())
print(queue.popleft())

print(queue)

deque(['태호', '현승', '지웅', '동욱', '신의'])
태호
태호
현승
지웅
deque(['동욱', '신의'])

7. 큐 구현

동적 배열과 더블리 링크드 리스트의 시간 복잡도

큐 구현

• 더블리 링크드 리스트로 구현하는 게 더 효율적이다.
• 파이썬 deque는 더블리 링크드 리스트로 구현되어 있다.

8. 스택 개념

스택(Stack)

• 데이터 간 순서를 유지해 주는 추상 자료형
• 나중에 저장된 데이터가 먼저 나오는 LIFO(Last in First Out) 구조이다.
• 맨 뒤 데이터 추가, 삭제, 접근 연산을 할 수 있어야 한다.
• 파이썬의 list나 deque로 스택을 구현할 수 있다.

deque로 스택 구현

# deque는 파이썬 collections 모듈에서 가지고 온다
from collections import deque

# 파이썬 스택 생성
stack = deque()  # 리스트로 구현: stack = []

# 스택 맨 끝에 데이터 삽입
stack.append("T")
stack.append("a")
stack.append("e")
stack.append("h")
stack.append("o")

print(stack)  # 스택 출력

# 스택 맨 끝 데이터 접근
print(stack[-1])

# 스택 맨 끝 데이터 삭제
print(stack.pop())
print(stack.pop())
print(stack.pop())

print(stack)

deque(['T', 'a', 'e', 'h', 'o'])
o
o
h
e
deque(['T', 'a'])

9. 스택 구현

동적 배열과 더블리 링크드 리스트의 시간 복잡도

스택 구현

• 스택을 구현하기에 동적 배열, 더블리 링크드 리스트 둘 다 효율적이다.
• 파이썬 list는 동적 배열, 파이썬 deque는 더블리 링크드 리스트로 구현되어 있기 때문에 스택을 list로 구현하는 것과 dequq로 구현하는 것에 시간 복잡도 차이가 없다.

10. 딕셔너리 개념

딕셔너리(Dictionary)

• key-value 데이터 쌍을 삽입, key를 이용한 데이터 탐색 및 삭제가 가능한 추상 자료형
• 데이터간 순서 관계를 약속하지 않는다.
• 맵(Map)이라고도 부른다.

dictionary (Python)

# 파이썬 딕셔너리 생성
grades = {}

# key-value 데이터 삽입
grades["현승"] = 80
grades["태호"] = 60
grades["영훈"] = 90
grades["지웅"] = 70
grades["동욱"] = 97

print(grades)  # 딕셔너리 출력

# value 데이터 수정
grades["태호"] = 100

print(grades)

# key를 이용해서 value 탐색
print(grades["동욱"])
print(grades["현승"])

# key를 이용한 삭제
print(grades.pop("태호"))
print(grades.pop("지웅"))

print(grades)

{'현승': 80, '태호': 60, '영훈': 90, '지웅': 70, '동욱': 97}
{'현승': 80, '태호': 100, '영훈': 90, '지웅': 70, '동욱': 97}
97
80
100
70
{'현승': 80, '영훈': 90, '동욱': 97}

11. 딕셔너리 구현

해시 테이블의 시간 복잡도

딕셔너리 구현

• 딕셔너리가 약속하는 연산들과 해시 테이블이 갖고 있는 연산들이 모두 일치한다.
• 모든 연산들을 평균적으로 O(1)으로 효율적이다.
• 파이썬 dictionary도 해시 테이블로 구현되어 있다.

12. 세트 개념

세트(Set)

• 삽입, 탐색, 삭제 연산이 있고, 중복된 데이터를 허용하지 않는 추상 자료형
• 삽입: 중복되지 않는 데이터를 저장할 수 있다
• 탐색: 데이터가 저장됐는지 확인할 수 있다.
• 삭제: 저장한 데이터를 지울 수 있다.
• 데이터간 순서 관계를 약속하지 않는다.

set (Python)

# 파이썬 세트 생성
finished_class = set()

# 데이터 삽입
finished_class.add("자료 구조")
finished_class.add("알고리즘")
finished_class.add("프로그래밍 기초")
finished_class.add("인터랙티브 웹")
finished_class.add("데이터 사이언스")

print(finished_class)  # 세트 출력

# 중복 데이터 저장 시도
finished_class.add("자료 구조")
finished_class.add("알고리즘")

print(finished_class)

# 데이터 탐색
print("컴퓨터 개론" in finished_class)
print("자료 구조" in finished_class)

# 데이터 삭제
print(finished_class.remove("자료 구조"))  # set는 데이터 삭제시 None을 리턴한다.
print(finished_class.remove("알고리즘"))

print(finished_class)

{'자료 구조', '알고리즘', '프로그래밍 기초', '데이터 사이언스', '인터랙티브 웹'}
{'자료 구조', '알고리즘', '프로그래밍 기초', '데이터 사이언스', '인터랙티브 웹'}
False
True
None
None
{'프로그래밍 기초', '데이터 사이언스', '인터랙티브 웹'}

13. 세트 구현

해시 테이블의 시간 복잡도

세트 구현

• key-value 쌍이 아닌 key 값만 저장하는 해시 테이블로 세트를 구현할 수 있다.
• 모든 연산들을 평균적으로 O(1)으로 효율적이다.
• 파이썬 set는 key만 존재하는 해시 테이블로 구현되어 있다.

Feedback

• 많이 사용되는 추상 자료형들을 찾아보자.
• 파이썬에서 사용되는 추상 자료형을 C와 다른 언어들로 구현해보자.
• 알고리즘을 풀 때 우선적으로 자료 구조와 추상 자료형을 고민해보자.

참고 자료

• 파이썬 set의 데이터구조부터 hashtable까지(갑분 C 등장)
• 기본 자료 구조들 - 알고리즘 · 자료구조 강의 | 코드잇