자료구조 3주차_큐&해쉬

자료구조 3주차_큐&해쉬

---

큐

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
            return

        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()) #3
queue.enqueue(4)
print(queue.peek()) #3
queue.enqueue(5)
print(queue.peek()) #3
print(queue.dequeue())
print(queue.dequeue())
print(queue.peek()) #5
print(queue.is_empty()) #False
print(queue.dequeue())
print(queue.is_empty()) #True

---

해쉬

 

데이터의 검색과 저장이 아주 빠르게 진행!

 

📌 해쉬함수란?

Hash Function

임의의 길이를 갖는 메세지를 입력하여 고정된 길이의 해쉬값을 출력하는 함수

[View]-[Tool Windows]-[Python Console]

 

>>> items = [None]*8
>>> hash("fast")%8
3

>>> items[hash("fast")%8]="빠른"
>>> items[hash("slow")%8]="느린"
>>> items
[None, None, '느린', '빠른', None, None, None, None]

>>> items[hash("fast")%8]
'빠른'

임의의 index값으로 접근가능!

 

 

해쉬 구현

class Dict:
    def __init__(self):
        self.items = [None] * 8

    def put(self, key, value):
        index = hash(key) % len(self.items) # 0~7
        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"))

 

하지만, 해쉬로 접근하면 임의의 값이 할당되므로 index가 중복이 발생할 수 있다.

이럴 경우 충돌 발생!!!

 

📌 충돌을 해결한 방법 : chaining

링크드 리스트, 연결지어서 해결한다.

class LinkedTuple:
    def __init__(self):
        self.items = list()

    def add(self, key, value):
        self.items.append((key, value))

    def get(self, key):
        for k, v in self.items:
            if key == k:
                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)

 

📌 해쉬 알고리즘

암호화는 가능하지만, 복호화는 어려움

해쉬 알고리즘은 비밀번호를 DB에 저장할 때 주로 쓰인다.

---

📌 해쉬테이블

키와 데이터를 저장함으로써 즉각적으로 데이터를 받아오고 업데이트하고 싶을 때 사용하는 자료구조

 

📄 출석체크

all_students = ["나연", "정연", "모모", "사나", "지효", "미나", "다현", "채영", "쯔위"]
present_students = ["정연", "모모", "채영", "쯔위", "사나", "나연", "미나", "다현"]

def get_absent_student(all_array, present_array):
    student_dict = {}
    for key in all_array: # O(N)
        student_dict[key] = True

    # 출석한 학생들 하나하나 제거
    for key in present_array: # O(N)
        del student_dict[key]

    for key in student_dict.keys():
        return  key


print(get_absent_student(all_students, present_students))