추상 자료형

기능과 구현

기능은 연산이 무엇을 하는지에 관한 내용이다. 삽입 연산 기능은 순서 데이터에서 원하는 위치에 데이터를 저장한다. 구현은 연산의 기능을 어떻게 만들지에 관한 내용이다.

추상화

추상화는 구현을 몰라도 기능을 알면 사용할 수 있게 해주는 개념이다.
자료구조를 추상화 한 것을 추상 자료형이라 한다. 데이터를 어떻게 저장/사용할지에 대한 구현방법을 생각하지 않고 기능만 알면 된다.

추상 자료형과 자료 구조

추상 자료형은 자료형을 추상화한 것이다. 리스트가 추상 자료형이다. 리스트는 데이터에 접근, 탐색, 삽입, 삭제를 하기 위한 기능을 가지고 있다. 이 것을 어떻게 구현할 것인지는 추상 자료형에 포함되지 않는다.

동적 배열이 자료 구조이다. 동적 배열은 접근, 탐색, 삽입, 삭제를 정확히 어떻게 구체적으로 구현할지를 포함한 내용이다.

동적 배열은 리스트의 모든 연산들을 갖고 있는 자료구조다. 추상 자료형인 리스트를 자료 구조인 동적 배열을 통해 구현하는 것이다. 또는 자료 구조인 링크드 리스트를 통해 구현할 수 도 있다.

코드를 작성할 때 추상 자료형(기능)을 먼저 떠올리고 어떤 자료 구조(구현)를 사용해 만들겠다고 생각하면 편하다. 기능을 중점으로 말하거나, 흐름을 생각할 때는 추상 자료형을, 코드의 성능을 분석하거나 최적화 시킬 때는 자료 구조를 중점적으로 생각하면 된다.

리스트

리스트는 데이터간 순서를 유지해주는 추상 자료형이다.

리스트의 기능은

• 접근 연산
  특정 위치에 있는 데이터를 가져오거나 수정한다.
• 탐색 연산
  특정 조건을 만족하는 데이터를 찾는다.
• 삽입 연산
  특정 위치에 새로운 데이터를 저장한다.
• 삭제 연산
  특정 위치에 있는 데이터를 지운다.

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

# 특정 위치에 데이터 삽입
char.insert(0, "A")
char.insert(1, "B")
char.insert(2, "C")
char.insert(3, "D")

# 괄호를 이용한 인덱스 접근
print(char[0])
char[2] = 4

# in을 이용한 탐색
print("A" in char)

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

리스트 구현

리스트를 구현하는 자료 구조에 동적 배열과 링크드 리스트가 있다.

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

어떤 자료 구조를 사용해 구현할지 정할 때 많이 사용할 연산들의 시간복잡도를 비교해 보면 된다.
파이썬 리스트는 동적 배열로 구현되어 있다.

큐

리스트와 마찬가지로 데이터간 순서를 약속하는 추상 자료형이다. 데이터를 삭제할 때는 가장 앞에서만 삭제하고 삽입할 때는 가장 뒤에서만 삽입한다.

큐의 기능은

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

파이썬에서는 deque자료형을 사용해서 큐를 사용할 수 있다. deque는 Doubly-ended-queue의 약자이며 해석하면 양면 큐 이다. 일반 큐는 한쪽으로 들어가고 한쪽으로 나가지만 deque는 양쪽으로 들어가고 나갈 수 있다. 맨 앞과 맨 뒤에 데이터를 삽입하고 삭제할 수 있게 해주는 자료형이다.

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

queue = deque()

# 큐의 맨 끝에 데이터를 삽입
queue.append("A")
queue.append("B")
queue.append("C")
queue.append("D")
queue.append("E")

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

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

popleft()는 데이터를 삭제하면서 동시에 리턴을 한다.

큐 구현

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

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

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

스택

데이터간 순서를 약속하는 추상 자료형이다. 데이터를 마지막에 저장하고 마지막 부터 가져온다. 가장 마지막에 들어온 데이터가 가장 먼저 삭제되는 것이다.

스택의 기능은

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

파이썬에선 큐를 사용할 때와 같이 deque를 사용해 스택을 사용할 수 있다.

from collections import deque

stack = deque()

# 스택 맨 끝에 데이터 추가
stack.append("A")
stack.append("B")
stack.append("C")
stack.append("D")
stack.append("E")

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

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

스택 구현

스택은 동적 배열과 링크드 리스트를 사용해 구현할 수 있다.

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

시간 복잡도 상으로 동적 배열이나 더블리 링크드 리스트나 뭘 고르든 상관없다.
위의 코드에서 stack = deque()대신 배열을 사용해 stack = [] 로 작성해도 그 아래의 코드들은 동일하게 작동한다.

딕셔너리

데이터간 순서 관계를 약속하지 않는다. 맵이라고도 한다.

딕셔너리의 기능은

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

grades = {}

# key - value 데이터 삽입
grades["A"] = 80
grades["B"] = 90
grades["C"] = 70

# 한 key에 여러 value 저장 시도
grades["A"] = 100  # 기존의 value가 교체된다

# key를 이용해서 value 탐색
print(grades["A"])

# key를 이용한 삭제
grades.pop("A")

딕셔너리 구현

해시 테이블을 사용해 구현하는게 효율적이다.

	해시 테이블
key-value 쌍 삽입	O(1)
key를 이용한 탐색	O(1)
key를 이용한 삭제	O(1)

파이썬 딕셔너리도 해시 테이블로 구현되어 있다.

세트

세트는 데이터간 순서 관계를 약속하지 않는다. 단순히 데이터를 저장, 탐색, 삭제를 하고 싶을 때 사용한다.

세트의 기능은

• 삽입
  데이터를 저장할 수 있다.(중복 X)
• 탐색
  데이터가 저장됐는지 확인할 수 있다.
• 삭제
  저장한 데이터를 지울 수 있다.

세트 구현

해시 테이블로 구현한다. 해시 테이블에서 키만 저장하고 값은 저장하지 않으면 된다.

	해시 테이블
삽입	O(1)
탐색	O(1)
삭제	O(1)