[자료구조]기본5_추상자료형

 

 

기능 vs 구현

기능 : 연산이 "무엇"을 하는지

구현 : 연산의 기능을 "어떻게"하는지

 

추상화 : 복잡한 구현을 몰라도, 기능만 알면 사용가능하게 하는것(ex-python)

 

추상자료형(기능) vs 자료구조(구현)

추상자료형 : 자료구조를 추상화 함, 데이터를 저장/사용할때 기능만 생각함

자료구조 : 연산을 "어떻게"처리할지 구현까지 포함한 내용

출처 : 코드잇

📌 리스트라는 추상자료형을 동적배열 or 링크드리스트로 구현

 ❗  추상자료형을 생각하고 -> 필요할때 자료구조를 생각해서 코딩한다

 

추상자료형(기능 : 무엇을)	자료구조(구현 : 어떻게)

 

 

 

추상자료형1

리스트

#파이썬 리스트 생성(기능만 알고 사용할 수 있는 언어 : 파이썬)
trending = []

#특정 위치에 데이터 삽입
trending.insert(0, "라이언1호")
trending.insert(1, "네오1호")
trending.insert(2, "프로도1호")
print(trending)

# 괄호를 이용한 인덱스 접근
print(trending[0])
print(trending[1])
trending[2] = "어피치1호"     #내용변경가능
print(trending)

# in을 이용한 탐색, boolean값 리턴
print("라이언1호" in trending)   #true
print("라이언2호" in trending)   #false

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

 

리스트 구현

출처 : 코드잇

 

 

추상자료형2

큐(Queue) - 대기열

데이터 간 순서를 약속하는 추상자료형

FIFO(First-in-First-out) : 가장먼저들어온데이터가 가장먼저 삭제된다(데이터를 앞에서만 삭제, 뒤에서만 삽입)

추가(맨뒤), 삭제(맨앞), 접근가능(맨앞)

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

queue = deque()

#큐의 맨 끝에 데이터 삽입
queue.append("콘")
queue.append("무지")
queue.append("제이지")
print(queue)

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

#큐 맨 앞 데이터 삭제
print(queue.popleft())            #popleft() : 맨앞데이터 삭제되고, 삭제된데이터가 리턴됨
print(queue)

Queue 구현

동적배열 or 링크드리스트로 구현가능

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

출처 : 코드잇

 

 

 

추상자료형3

스택(Stack)

LIFO 추상자료형

추가(맨뒤), 삭제(맨뒤), 접근(맨뒤)

LIFO(Last-in-First-out) : 나중에들어온 데이터가 가장먼저 삭제된다

from collections import deque

stack = deque()

# 스텍 맨 끝에 추가
stack.append("T")
stack.append("O")
stack.append("M")
print(stack)

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

# 맨 끝 데이터 삭제 / 삭제시 삭제된 데이터 출력(리턴) 후 삭제처리
print(stack.pop())
print(stack.pop())
print(stack)

 

Stack구현

동적배열 or 링크드리스트로 구현가능

두가지 모두 효율적!

출처 : 코드잇

빈 데크를 만들어서 stack으로 사용	효율성은 비슷하니 deque대신 배열사용해도 무관

 

 

 

 

추상자료형4

딕셔너리(=map)

데이터 간 순서를 약속X

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

grades = {}

#key-value데이터 삽입
grades["라이언"] = 10
grades["네오"] = 20
grades["프로도"] = 30
print(grades)   #딕셔너리 출력

# 한 키에 여러 value저장할 시, 마지막 value값으로 덮어씌워짐

#key를 이용한 탐색
print(grades["라이언"]

#key를 이용한 삭제
grades.pop("프로도")

딕셔너리 구현

해시테이플 자료구조로 구현가능!

(둘 간의 연산테이블이 모두 일치하며, 시간복잡도도 O(1)으로 효율적

출처 : 코드잇

 

 

 

추상자료형5

세트(집합)

데이터 간 순서를 약속X (심플한 연산이 필요할 때 사용)

삽입(중복허용x)/탐색/삭제

finished_classes = set()

# 데이터 저장
finished_classes.add("자료구조")
finished_classes.add("알고리즘")
finished_classes.add("프로그래밍기초")
print(finished_classes)

# 중복 데이터 저장 시도
finished_classes.add("자료구조")    # 결과적으로 두번 저장되는것이아니고, 덮어써진다

# 데이터 탐색
print("알고리즘" in finished_classes) 		#true
print("코딩테스트" in finished_classes)     #false리턴

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

 

set구현

보통 해시테이블을 사용하여 구현

but 해시테이블은 key-value쌍으로 구현하는데 어떻게 set을 구현할까? key만 저장하는것으로 가능하다!

 

 

 

 

 

 

 

추상자료형 구분하기(feat.python)

추상자료형	list	queue	stack	dictionary(map)	set
순서	순서o	순서o	순서o	순서x	순서x
특징	특정위치에  연산가능	FIFO,  추가맨뒤 삭제맨앞	LIFO, 맨뒤	key-value  key로 탐색	해시테이블로구현 key만 저장!
생성하기	list = []	queue = deque()	stack = deque()	dic = {}	setset = set()
삽입	list.insert(0, "귤")	queue.append("귤")	stack.append("귤")	dic["귤"] = 10	setset.add("귤")
접근(+수정)	list[0]	queue[0]	stack[-1]	dic["귤"] = 10 중복저장시 덮임	setset.add("귤") 중복저장시 덮임
탐색	"귤" in list	-	-	dic["귤"]	"귤" in setset
삭제	del list[0]	queue.popleft()	stack.pop()	dic.pop("귤")	setset.remove("귤")

 

 

 

출처 : 코드잇(자료구조)