알고리즘 책 한 권만큼은 반드시 정복한다
지금은 지난 학기에 수강했던 알고리즘을 복습 중이다. 다음 학기에 누가 쓰지 않았으면 하는 마음에 어디 학교인지 밝힐 수 없다.

linked list와 circular list를 배우고 stack에 적용하는 예제

백준 9012

괄호가 제대로 닫히는 지 확인하는 문제

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class Stack:
    def __init__(self):
        self.top = None
        self.size = 0

    def push(self, data):
        node = Node(data)
        self.size += 1
        node.next = self.top
        self.top = node

    def pop(self):
        # empty stack
        if self.size == 0:
            return None

        idx = self.top.data
        self.top = self.top.next
        self.size -= 1
        return idx

    def peek(self):
        if self.size == 0:
            return None
        return self.top.data


def check_brackets(bracket):
    stack = Stack()

    for i in bracket:
        if i == '(':
            stack.push(i)
        elif stack.pop() is None:
            return False

    if stack.peek() is None:
        return True
    else:
        return False


n = int(input())
sl = []
for _ in range(n):
    sl.append(input())

for i in range(n):
    result = check_brackets(sl[i])
    if result:
        print("YES")
    else:
        print("NO")

스택의 경우 크게 어려운 것이 없었다. 다만 LIFO 을 활용하는 상황을 그리기 어렵다.

백준 2164번 카드 게임

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Queue:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

    def enqueue(self, data):
        node = Node(data)

        if self.size == 0:
            self.head = node
            self.tail = node
        else:
            self.tail.next = node
            self.tail = node
        self.size += 1

    def dequeue(self):
        self.size -= 1
        if self.size < 0:
            return None
        data = self.head.data
        self.head = self.head.next
        return data

# card game method
def card_game(que):
    if q.size == 1:
        print(q.dequeue())
    que.dequeue()
    que.enqueue(que.dequeue())

q = Queue()
n = int(input())

for i in range(n):
    q.enqueue(i+1)

for _ in range(n):
    card_game(q)
    if q.size == 1:
        print(q.dequeue())

역시 큐의 경우도 까다롭지 않다. 개인적으로 스택과 다르게 활용도가 직관적이라 생각한다. back tracking 문제만큼 까다로운 것은 없었다.