TIL_36 : 추상 자료형

🙄 기능 vs 구현

---

➡ 기능

• 연산이 "무엇"을 하는지
  ex) 삽입 연산 기능: 순서 데이터에서 원하는 위치에 데이터를 저장

➡ 구현

• 연산의 기능을 "어떻게" 하는지
  ex) 더블리 링크드 리스트 삽입은 저장하려는 위치 앞 노드에 접근한 후 앞뒤 노드들의 레퍼런스들을 수정

🙄 추상화

---

➡ 추상화

• 구현을 몰라도 기능만 알면 프로그래밍을 할 수 있게 해주는 개념
• 추상화를 하면 이미 쓴 코드를 재활용하고 개발자들끼리 협력하기 쉬워짐

➡ 추상 자료형 (Abstract Data Type)

• 자료 구조를 추상화 한 것
• 데이터를 저장/사용할 때 기능만 생각

➡ 추상 자료형 vs 자료 구조

• 기능을 중점적으로 얘기하고 싶을 때나, 흐름을 생각할 때와 같이 구현에 집중할 필요가 없을 때 추상 자료형을 중심적으로 생각
• 코드의 성능을 분석하거나 최적화 시켜야 될 때나, 성능을 최대로 끌어올리고 싶을 때 자료 구조를 중심적으로 생각

추상 자료형 : 리스트

• 데이터 간 순서 관계를 유지할 수 있다
• 접근 연산 : 특정 위치에 있는 데이터를 가지고 오거나 수정한다
• 탐색 연산 : 특정 조건을 만족하는 데이터를 찾는다
• 삽입 연산 : 특정 위치에 새로운 데이터를 저장한다
• 삭제 연산 : 특정 위치에 있는 데이터를 지운다

  👉 데이터에 무엇을 하고 싶은지, 연산의 기능들만 가지고 있음
  👉 연산들을 정확히 어떻게 구현할 건지에 대한 내용은 추상 자료형에 포함❌

자료 구조 : 동적 배열

• 데이터를 메모리에 순서대로 그리고 연속적으로 저장한다
• 접근 연산 : 인덱스 주소를 한 번에 계산해서 메모리에 접근한다
• 탐색 연산 : 가장 앞 인덱스부터 선형적으로 모든 데이터를 확인한다
• 삽입 연산 : 인덱스 뒤 데이터를 한 칸씩 뒤로 밀고, 데이터를 저장한다
• 삭제 연산 : 데이터를 지우고 뒤 인덱스들을 하나씩 앞으로 옮겨서 저장한다

  👉 정확히 데이터를 어떻게 저장할 건지, 데이터 간 관계를 어떻게 유지할 건지, 각 연산들을 구체적으로 어떻게 할지 모든 것을 묶어 놓은 개념

👉 자료 구조보다 추상 자료형을 생각하면 코드의 흐름에 집중할 수 있다
👉 기능을 먼저 생각하고 구현을 어떻게 할지 결정한다

🙄 큐 (Queue)

---

➡ 큐 개념

• FIFO : First-in-first-out
• 데이터 간 순서 관계를 유지할 수 있다

큐의 대표적 기능

1. 맨 뒤 데이터 추가
2. 맨 앞 데이터 삭제
3. 맨 앞 데이터 접근

# deque
# Doubly-ended-queue의 약자
# 맨 앞과 뒤에 데이터를 삽입하고 삭제할 수 있게 해주는 자료형

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

queue = deque()

# 큐의 맨 끝에 데이터 삽입
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(['찬휘'])

➡ 큐 구현

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

👉 큐는 더블리 링크드 리스트로 구현하는 것이 더 효율적
👉 실제 Python 내부적으로도 더블리 링크드 리스트로 구현되어 있다

🙄 스택 (Stack)

---

➡ 스택 개념

• LIFO : Last-in-first-out
• 데이터 간 순서 관계를 유지할 수 있다

스택의 대표적 기능

1. 맨 뒤 데이터 추가
2. 맨 뒤 데이터 삭제
3. 맨 뒤 데이터 접근

from collections import deque

stack = deque()

# 스택 맨 끝에 데이터 추가
stack.append("J")
stack.append("a")
stack.append("h")
stack.append("y")
stack.append("e")
stack.append("o")
stack.append("n")

print(stack)

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

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

print(stack)

# deque(['J', 'a', 'h', 'y', 'e', 'o', 'n'])
# n
# n
# o
# e
# deque(['J', 'a', 'h', 'y'])

➡ 스택 구현

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

👉 스택은 동적 배열, 더블리 링크드 리스트 둘 다 효율적

🙄 딕셔너리 (Dictionary)

---

• 데이터간 순서 관계를 약속하지 않음
• key-value 데이터 쌍 삽입
• key를 이용한 데이터 탐색
• key를 이용한 데이터 탐색

grades = {}

# key - value 데이터 삽입
grades["자현"] = 70
grades["정호"] = 90
grades["준규"] = 80
grades["찬휘"] = 100

print(grades)

# key 를 이용해서 value 탐색
print(grades["찬휘"])
print(grades["준규"])

# key 를 이용한 삭제
grades.pop("정호")
grades.pop("자현")

print(grades)

# {'자현': 70, '정호': 90, '준규': 80, '찬휘': 100}
# 100
# 80
# {'준규': 80, '찬휘': 100}

	해시 테이블
key-value 쌍 삽입	$O(1)$ (평균)
key를 이용한 탐색	$O(1)$ (평균)
key를 이용한 삭제	$O(1)$ (평균)
길이 확인	$O(1)$

👉 실제로 해시 테이블을 이용해서 구현되어 있는 딕셔너리

🙄 세트

---

➡ 세트 개념

• 데이터간 순서 관계를 약속하지 않음
• 삽입 : 데이터를 저장할 수 있다 (중복 데이터❌)
• 탐색 : 데이터가 저장됐는지 확인할 수 있다
• 삭제 : 저장한 데이터를 지울 수 있다

finished_classes = set()

# 데이터 저장
finished_classes.add("자료 구조")
finished_classes.add("알고리즘")
finished_classes.add("프로그래밍 기초")
finished_classes.add("인터렉티브 웹")
finished_classes.add("데이터 사이언스")

print(finished_classes)

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

print(finished_classes)

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

# 데이터 삭제
finished_classes.remove("자료 구조")
finished_classes.remove("알고리즘")

print(finished_classes)

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

➡ 세트 구현

	해시 테이블
key-value 쌍 삽입	$O(1)$ (평균)
key를 이용한 탐색	$O(1)$ (평균)
key를 이용한 삭제	$O(1)$ (평균)
길이 확인	$O(1)$

👉 실제로 해시 테이블을 이용해서 구현되어 있는 세트
👉 value는 저장하지 않고 key만 저장하는 해시 테이블
👉 순서를 저장할 팔요 없이 단순히 데이터를 삽입, 탐색, 삭제하고 싶을 때는 set