アルゴリズム3週目:スタック、キュー、ハッシュ

📍 スタック

データを1つの端点に配置して抽出できるデータ構造、最初のデータの挿入と抽出、上部からのみ抽出と挿入

💡 スタックの実装

Push(データ):データを一番前に置く
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)

📍 キュー

一方の端にデータを置き、他方の端からデータを移動するリニア構造、1回目の入力、順番に処理する必要がある

💡 キューの実装

Enqueue(データ):最後にデータを追加
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):valueをkeyに保存
get(key):keyに対応する値を取得する

💡 コードの作成

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"))
        

その結果、同じアレイにマッピングされたインデックスがデータを上書きします.
これを衝突(衝突)と呼ぶ.
競合を解決する最初の方法は、リンクリストを使用することです.
この方式を結びつけて解決して、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))