📍 스택
한쪽 끝으로만 자료를 넣고 뺄 수 있는 자료 구조, Last In First Out 데이터를 넣고 뽑기, 맨 위의 것만 뽑고 넣기
💡 스택의 구현
push(data) : 맨 앞에 데이터 넣기
pop() : 맨 앞의 데이터 뽑기
peek() : 맨 앞의 데이터 보기
isEmpty(): 스택이 비었는지 안 비었는지 여부 반환해주기
=> 링크드 리스트 사용!
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Stack:
def __init__(self):
self.head = None
def push(self, value):
# 어떻게 하면 될까요?
new_head = Node(value)
new_head.next = self.head
self.head = new_head
return
# pop 기능 구현
def pop(self):
# 어떻게 하면 될까요?
delete_head = self.head
self.head = self.head.next
return delete_head
def peek(self):
# 어떻게 하면 될까요?
if self.is_empty():
return "stack is empty"
return self.head.data
# isEmpty 기능 구현
def is_empty(self):
# 어떻게 하면 될까요?
return self.head is None
stack = Stack()
stack.push(3)
print(stack.peek())
stack.push(4)
print(stack.peek())
print(stack.pop().data)
📍 큐
한쪽 끝으로 자료를 넣고, 반대쪽에서는 자료를 뺄 수 있는 선형구조, First In First Out, 순서대로 처리되어야 하는 일에 필요
💡 큐의 구현
enqueue(data) : 맨 뒤에 데이터 추가하기
dequeue() : 맨 앞의 데이터 뽑기
peek() : 맨 앞의 데이터 보기
isEmpty(): 큐가 비었는지 안 비었는지 여부 반환해주기
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Queue:
def __init__(self):
self.head = None
self.tail = None
def enqueue(self, value):
# 어떻게 하면 될까요?
new_node = Node(value)
if self.is_empty():
self.head = new_node
self.tail = new_node
self.tail.next = new_node
self.tail = new_node
return
def dequeue(self):
# 어떻게 하면 될까요?
if self.is_empty():
return "queue is empty"
delete_head = self.head
self.head = self.head.next
return delete_head
def peek(self):
# 어떻게 하면 될까요?
if self.is_empty():
return "queue is empty"
return self.head.data
def is_empty(self):
# 어떻게 하면 될까요?
return self.head is None
queue = Queue()
queue.enqueue(3)
print(queue.peek())
queue.enqueue(4)
queue.enqueue(5)
print(queue.dequeue())
📍 해쉬
컴퓨팅에서 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료 구조,
데이터의 검색과 저장이 아주 빠르게 진행 = 딕셔너리
dict = {"fast" : "빠른", "slow": "느린"} 키를 통해 바로 데이터를 받아올 수 있으므로, 속도가 획기적으로 빨라집니다.
✏️ 해쉬 함수(Hash Function)는 임의의 길이를 갖는 메시지를 입력하여 고정된 길이의 해쉬값을 출력하는 함수이다
put(key, value) : key 에 value 저장하기
get(key) : key 에 해당하는 value 가져오기
💡 코드작성
class Dict:
def __init__(self):
self.items = [None] * 8
def put(self,key,value):
index = hash(key) % len(self.items)
self.items[index] = value
def get(self,key):
index = hash(key) % len(self.items)
# 같은 값이 나오는 경우? 충돌 발생, 연결리스트로 해결
return self.items[index]
my_dict = Dict()
my_dict.put("test",3)
print(my_dict.get("test"))
같은 어레이의 인덱스로 매핑이 되어서 데이터를 덮어 써버리는 결과가 발생합니다.
이를 충돌(collision)이 발생했다고 합니다.
충돌을 해결하는 첫번째 방법은 바로 링크드 리스트를 사용하는 방식입니다.
이 방식을 연결지어서 해결한다고 해서 체이닝(Chaining) 이라고 합니다!
class LinkedTuple:
def __init__(self):
self.items = []
def add(self, key, value):
self.items.append((key, value))
def get(self, key):
for k, v in self.items:
if k == key:
return v
class LinkedDict: #체이닝 기법
def __init__(self):
self.items = []
for i in range(8):
self.items.append(LinkedTuple())
def put(self, key, value):
index = hash(key) % len(self.items)
self.items[index].add(key,value)
def get(self, key):
index = hash(key) % len(self.items)
return self.items[index].get(key)
-
해쉬 테이블(Hash Table) : "키" 와 "데이터"를 저장함으로써 즉각적으로 데이터를 받아오고 업데이트하고 싶을 때 사용하는 자료구조
-
해쉬 함수(Hash Function) : 임의의 길이를 갖는 메시지를 입력하여 고정된 길이의 해쉬값을 출력하는 함수 (해쉬 테이블의 내부 구현은 키를 해쉬 함수를 통해 임의의 값으로 변경한 뒤 배열의 인덱스로 변환하여 해당하는 값에 데이터를 저장하여 즉각적으로 데이터를 찾고, 추가할 수 있다)
-
해쉬 값 혹은 인덱스가 중복되어 충돌이 일어난다면 체이닝과 개방 주소법 으로 해결할 수 있다
💡 해쉬 예제 - 출석체크
Q. 오늘 수업에 많은 학생들이 참여했습니다. 단 한 명의 학생을 제외하고는 모든 학생이 출석했습니다.
모든 학생의 이름이 담긴 배열과 출석한 학생들의 배열이 주어질 때, 출석하지 않은 학생의 이름을 반환하시오.
all_students = ["나연", "정연", "모모", "사나", "지효", "미나", "다현", "채영", "쯔위"]
present_students = ["정연", "모모", "채영", "쯔위", "사나", "나연", "미나", "다현"]✏️ 문제풀이
- 반복을 사용하면, 이중 for문으로 비효율적인 시간복잡도가 된다.
- 딕셔너리를 이용해 O(N)의 시간복잡도를 가진 코드 생성, 공간복잡도가 올라간다.
all_students = ["나연", "정연", "모모", "사나", "지효", "미나", "다현", "채영", "쯔위"]
present_students = ["정연", "모모", "채영", "쯔위", "사나", "나연", "미나", "다현"]
#반복 -> 비효율적
#딕셔너리 사용! -> 공간복잡도가 많아짐
def get_absent_student(all_array, present_array):
student_dict = {}
for key in all_array: # all_array 키를 하나씩 등록
student_dict[key] = True # 공간복잡도 O(N)
for key in present_array: # 비교대상 배열을 삭제시킨다
del student_dict[key]
for key in student_dict.keys(): # 남은 키를 반환
return key
print(get_absent_student(all_students, present_students))