알고리즘 - 3주차 [스택, 큐, 해쉬]

 

Stack

: 한쪽으로만 자료를 넣고 뺄 수 있는 자료 구조. Last In First Out (LIFO)

 

• 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_node = Node(value)
        self.head.next = self.head
        self.head = new_node
        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

stack = Stack()
stack.push(3)
print(stack.peek())     # 3
stack.push(4)
print(stack.peek())     # 4
print(stack.pop().data) # 4
print(stack.peek())     # 3
print(stack.is_empty()) # False

 

 

스택 문제 - 탑

top_heights = [6, 9, 5, 7, 4]


def get_receiver_top_orders(heights):
    answer = [0] * len(heights)     # [0, 0, 0, 0, 0]
    while heights:  # heights 배열이 빈 상태가 아닐 때 까지
        height = heights.pop()  # 리스트의 마지막 인덱스 뽑아서 저장
        for idx in range(len(heights)-1, 0, -1):  # 남은 리스트의 오른쪽부터 비교해야하므로 인덱스번호는 (총길이 - 1)번째 부터
            if heights[idx] > height:   # pop 요소 보다 idx번째 위치한 요소가 더 크다면
                answer[len(heights)] = idx + 1    # 인덱스 값이 아닌 n번째 위치를 저장하는 것이므로 +1
                break # 저장되면 다음요소로
    return answer


print(get_receiver_top_orders(top_heights))  # [0, 0, 2, 2, 4] 가 반환되어야 한다!

print("정답 = [0, 0, 2, 2, 4] / 현재 풀이 값 = ",get_receiver_top_orders([6,9,5,7,4]))
print("정답 = [0, 0, 0, 3, 3, 3, 6] / 현재 풀이 값 = ",get_receiver_top_orders([3,9,9,3,5,7,2]))
print("정답 = [0, 0, 2, 0, 0, 5, 6] / 현재 풀이 값 = ",get_receiver_top_orders([1,5,3,6,7,6,5]))

 

 

 

큐Queue

한쪽으로 자료를 넣고, 반대쪽에서는 자료를 뺄 수 있는 선형구조이다.

FIFO (First In First Out)

순서대로 처리되어야 하는 일에 필요하다.

tail 속성이 추가로 필요하다.

 

• 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    # head 에 new_node를
            self.tail = new_node    # tail 에 new_node를 넣어준다.
            return
        self.tail.next = new_node   # 먼저 추가된 노드를 기존 tail 뒤로 붙여준다.
        self.tail = new_node        # tail 을 바꿔준다.
        return

    def dequeue(self):
        if self.is_empty():
            return "Queue is Empty"
        delete_head = self.head     # head 값을 저장해두고
        self.head = self.head.next  # head.next 값을 head에 넣어준다.

        return delete_head.data  # 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())  # 3
print(queue.peek()) # 4
print(queue.is_empty()) # False

 

 

 

해쉬

컴퓨팅에서 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료 구조이다.

해시 테이블은 해시 함수를 사용하여 색인(index)을 버킷(bucket)이나 슬롯(slot)의 배열로 계산한다.

데이터를 다루는 기법 중에 하나로 데이터의 검색과 저장이 아주 빠르게 진행된다.

딕셔너리를 해쉬 테이블이라고 부르기도 합니다.

 

해쉬 함수 

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

 

딕셔너리 구현

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

    def put(self, key, value):  # key와 value를 입력받아 배열에 저장하는 기능
        # key 값을 hash 하여 배열의 길이로 나누면 나머지 값이 인덱스 번호가 된다.
        index = hash(key) % len(self.items)
        self.items[index] = value

    def get(self, key): # key 값을 입력받아 해당하는 value 값 가져오기
        index = hash(key) % len(self.items)
        return self.items[index]


my_dict = Dict()
my_dict.put('test',3)
print(my_dict.get('test'))

 

충돌 collision

해쉬 값이 같거나 해쉬값을 배열의 길이로 나눈 나머지가 똑같은 숫자가 되면 같은 배열의 인덱스로 매핑이 되어서 데이터가 덮어씌이게 되어 충돌(collision) 이 일어난다.

 

충돌을 해결하는 방법 중 하나로 링크드 리스트를 사용하는 방식이다. 연결지어서 해결한다고 해서 체이닝(chaining)이라고한다.