220921 병합정렬 & 스택 큐 해쉬

Merge sort 병합정렬

리스트를 분할을 연속해서 제일 작은단위까지 쪼갠다 -> 다시 합치면서 정렬시킴

시간복잡도는 O(N*log2N) / 데이터의 분포에 영향을 덜 받음

굉장히 빠른편임.

 

array = [5, 3, 2, 1, 6, 8, 7, 4]

 

다음과 같은 어레이가 있으면 진행 순서는

 

[5, 3, 2, 1]  [6, 8, 7, 4]

 

[5, 3]  [2, 1]  [6, 8]  [7, 4]

 

[5] [3] [2] [1] [6] [8] [7] [4]

 

여기서 부터 실제로 정렬이 일어남

[3, 5] [1, 2] [6, 8] [4, 7]

 

[1, 2, 3, 5] [4, 6, 7, 8]

 

[1, 2, 3, 4, 5, 6, 7, 8]

 

def merge_sort(array):
    if len(array) <= 1:
        return array
    mid = len(array) // 2
    left_array = merge_sort(array[0:mid])
    right_array = merge_sort(array[mid:])

    return merge(left_array, right_array)



def merge(array1, array2):
    result = []
    array1_index = 0
    array2_index = 0
    while array1_index < len(array1) and array2_index < len(array2):
        if array1[array1_index] < array2[array2_index]:
            result.append(array1[array1_index])
            array1_index += 1
        else:
            result.append(array2[array2_index])
            array2_index += 1

    if array1_index == len(array1):
        while array2_index < len(array2):
            result.append(array2[array2_index])
            array2_index += 1

    if array2_index == len(array2):
        while array1_index < len(array1):
            result.append(array1[array1_index])
            array1_index += 1

    return result

---

Stack 스택

쉽게말하면  ㄷ 모양이다. 한쪽 방향으로만 데이터가 출입한다. 

Last In & First Out

데이터 입력 =  push -> append()

데이터 출력 =  pop -> pop()

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):
        if self.is_empty():
            return "Stack is empty"
        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

---

Queue 큐

스택이 ㄷ 이면 큐는 I I 모양이다. 입구와 출구가 따로있음.

First IN & First Out 

데이터 입력 = push -> append()

데이터 출력 = get -> pop(0)

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.data

    def peek(self):
        if self.is_empty():
            return "Queue is Empty"
        return self.head.data

    def is_empty(self):

        return self.head is None

---

Hash 해쉬

해쉬테이블 = 딕셔너리 라고 생각해도 될듯

시간복잡도 O(1) 이라고해도 무방 / 아주빠름

# 원소를 넣거나 삭제, 찾는일이 많을 때 사용하는게 좋음 -> 원소의 개수새기 문제 등등

 

get / set / delete 등 사용하는 메소드가 있음

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

    def put(self, key, value):
        index = hash(key) % len(self.items)
        self.items[index] = value

        return

    def get(self, key):
        index = hash(key) % len(self.items)

        return self.items[index]

 

해쉬에서 충돌이 일어날 때가 있다.

해쉬를 통해 index를 지정할 때, key값이 다른데 같은 index를 지정할 수 있다. 이 때 먼저 지정된 값이 지워진다.

이러한 현상을 충돌이라고 함.

충돌을 해결하기 위한 방법

1. Chaining 체이닝

동일한 해쉬값을 가지는 정보를 동일한 list에 저장하되, linked list 형식으로 연결하는 방식임.

 

2. 개방 주소법