[Python 자료구조] 추상자료형

추상자료형이란?

CodeIt 자료구조 수업을 정리한 내용입니다.

기능

연산이 "무엇"을 하는지를 의미합니다.

삽입 연산 기능

• 순서 데이터에서 원하는 위치에 데이터 저장

구현

기능을 "어떻게" 작성 하는지를 의미합니다.

연산시 필요한 기능 자체를 코드로 작성하는 것을 말합니다.

추상화

어떻게 구현되어 있는지 몰라도 기능만 알아도 사용할 수 있는 것

추상 자료형

• 자료구조를 추상화 한 것
• 데이터를 저장/사용할 때 기능만을 고려
  • 리스트 사용

동적배열, 링크드리스트: 자료 구조

리스트: 추상 자료형

추상 자료형 vs 자료 구조

추상 자료형은 어떤 한 기능에 집중하여 구현이 필요 없으나 자료 구조의 경우 어떤 한 기능에

집중하려 한다면 코드 구현이 필요합니다.

추상 자료형을 생각하면 구현없이 코드의 맥락과 흐름에 더 집중할 수 있습니다.

리스트

데이터간 순서 관계를 유지할 수 있습니다.

기능

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

구현

news = []
# 삽입
news.insert(0, "코로나 바이러스 출몰") 
news.insert(1, "주식, 비트코인 열풍")
news.insert(2, "비대면 시대")
# 접근
print(news[1])

# 탐색
print("비대면 시대" in news) # True or False

# 제거
del news[0]
print(news)

큐

데이터간 순서 관계를 유지, 맨 앞과 뒤에 데이터를 삽입하고 삭제할 수 있게 해주는 자료형

기능

• 접근: 맨 앞 데이터 접근
• 삽입: 맨 뒤에 데이터 추가
• 삭제: 맨 앞에 데이터 삭제

구현

from collections import deque

queue = deque()

queue.append("지후")  # 삽입
queue.append("지호")
queue.append("지아")
queue.append("지구")
queue.append("지운")

print(queue[0])  # 맨 앞 접근
print(queue.popleft()) # 맨 앞 데이터 제거 (제거값 리턴)
print(queue)

스택

둘다 효율적이므로 아무거나 사용

기능

• 접근: 맨 뒤 데이터 접근
• 삽입: 맨 뒤에 데이터 추가
• 삭제: 맨 앞에 데이터 삭제

구현

from collections import deque

queue = deque() # [] 사용 가능

queue.append("지후")  # 삽입
queue.append("지호")
queue.append("지아")
queue.append("지구")
queue.append("지운")

print(queue[-1])  # 맨 뒤 접근
print(queue.pop()) # 맨 뒤 데이터 제거 
print(queue)

딕셔너리

데이터간 순서 관계를 약속하지 않음

기능

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

구현

clubs = {}

clubs["chelsea"] = "londen"
clubs["real"] = "madrid"
clubs["inter"] = "milan"
clubs["tottenham"] = "londen"

print(clubs)

# key를 이용해 탐색
print(clubs["chelsea"])

# key를 이용해 삭제
clubs.pop("tottenham")
print(clubs)

# key를 이용해 추가
clubs["liverpool"] = "liverpool"
print(clubs)

세트

데이터간 순서 관계를 약속하지 않고 중복을 허용하지 않음 (해시 테이블 사용)

인덱스 접근보단 in을 이용한 값 포함 확인용

기능

• 삽입 : 데이터 저장
• 탐색 : 저장된 데이터 확인
• 삭제 : 저장된 데이터 삭제

구현

finished_classes = set()

finished_classes.add("자료구조")
finished_classes.add("알고리즘")
finished_classes.add("객체지향")
finished_classes.add("객체지향")  # 중복 허용 x

print("객체지향" in finished_classes)  # 탐색

finished_classes.remove("객체지향")  # 제거

print(finished_classes)

)

자료형 선택의 중요성

리스트가 범용적이지만 무조건 리스트를 사용하면 효율적 프로그래밍을 하기 힘듭니다.

예를 들어 1,000,000개의 데이터를 탐색하는 코드를 작성하면 다음과 같습니다.

import time

example_list = [x for x in range(0, 1000000)]

t_0 = time.time()
999999 in example_list # 탐색
t_1 = time.time()

print(f"리스트 소요 시간: {t_1 - t_0}")

인덱스 접근보단 in을 이용한 값 포함 확인 (탐색) 이라고 적어놨던 세트를 사용한 코드는 다음과 같습니다.

import time

example_set = set([x for x in range(0, 1000000)])

t_0 = time.time()
999999 in example_set # 탐색
t_1 = time.time()

print(f"세트 소요 시간: {t_1 - t_0}")

세트 소요 시간: 2.86102294921875e-06 (0.00000286초)
리스트 소요 시간: 0.015595197677612305 (0.015초)

이렇게 차이가 나는 이유는 파이썬 리스트는 동적배열로 구현되어 있고 세트는 해시테이블로 되어 있기 때문입니다.

각각 탐색시 시간복잡도는 O(n)과 O(1)이 소요되기에 이런 차이가 발생합니다.

결국 내가 필요한 기능, 요구사항(탐색, 추가, 제거, 정렬)에 따라 효율적으로 해결하기 위해선

자료구조의 시간복잡도를 이해하고 그것을 어떻게 사용할지 고민하고 생각하는 훈련이 필요합니다.

Reference

• https://wiki.python.org/moin/TimeComplexity
• https://www.codeit.kr/courses/data-structures