[TIL] 05/16 항해99 8일 차 - 스택(Stack), 문제풀이

 

들어가며

오늘 알고리즘 문제는 문제를 이해하는 데에만 많은 시간이 걸렸다. 해설에도 시작부터 어려운 문제라고 하더라... 머리를 쥐어짜고 다른 수강생분들의 도움도 받아서 겨우 문제를 이해했지만 역시나 구현을 하질 못해서 해설을 봐야만 했다.

난 언제쯤 문제 하나를 스스로 풀 수 있게 될까... 뭐가 문제인걸까... 회의감이 드는 항해99 7일차.

 

오늘의 TIL은 스택의 개념의 정리와 오늘 푼 문제를 정리하고, 현재 하고 있는 고민인 앞으로의 항해99에 대해 작성해보고자 한다.

---

스택(Stack)

스택이란?

데이터를 일시적으로 저장하기 위해 사용하는 자료구조로, 데이터의 입력과 출력 순서는 후입선출(LIFO, Last In First Out)이다.

Stack의 사전적 의미를 살펴보면 “a pile of objects, typically one that is neatly arranged.” 즉, 잘 정돈 시켜서 쌓아올린 더미 정도가 된다.

스택하면 가장 먼저 떠오르는 게 스택 오버플로인데, 이 명칭은 꽉찬 스택에 요소를 삽입하고자 할 때 스택에 요소가 넘쳐서 에러가 발생하는 ‘스택 버퍼 오버플로(Stack Buffer Overflow)’에서 유래했다.

 

스택이 사용되는 예시?
되돌리기 (ctrl + z, cmd + z)의 기능이 대표적이다. 직전에 했던 행동을 되돌리려면 내가 한 행동을 순서대로 기억해야하기 때문에 스택을 사용한다.
그 외에도 여러가지가 있는데, 아래의 사진을 참고하자

 

자료를 제공해주신 호균님에게 압도적 감사!

 

 

연결리스트로 스택 구현해보기

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

class Stack:
    def __init__(self):
        self.last = None

    def push(self, item):
        self.last = Node(item, self.last)

    def pop(self):
        item = self.last.item # pop은 가장 마지막 item을 return해준다.
        self.last = self.last.next
        return item

 

사실 파이썬에서의 스택은 리스트와 크게 다르지 않기 때문에 이렇게 일일히 구현하지 않고, 리스트로 사용해도 된다고 한다. 하지만 직접 구현해보고 구조를 익숙해지는게 도움이 된다고 한다.

 

여러번 직접 따라쳐보고 자연스럽게 이해하고 구현할 수 있을 때까지 따라쳐보자.

 

 

문제풀이

[leetcode] 20. 유효한 괄호 (Valid Parentheses)

[leetcode] 20. 유효한 괄호 (Valid Parentheses)

나오는 개념 - 연산자의 우선순위

 

 

[leetcode] 316. 중복 문자 제거 (Remove Duplicate Letters)

[leetcode] 316. 중복 문자 제거 (Remove Duplicate Letters)

나오는 개념 - 사전식 순서, collections.Counter()

 

 

[leetcode] 739. 일일 온도 (Daily Temperatures)

[leetcode] 739. 일일 온도 (Daily Temperatures)

나오는 개념 - enumerate()

---

마치며

이렇게 계속 구현은 못하는 채로 지나가도 되는 걸까... 개념을 탄탄히 잡아간다는 데에 의의를 둬야하는 걸까...

내가 잘 하고 있는건지 의문이 든다. 

 

새벽 3시. 이 시간쯤 되니까 다 필요없고 배고프다.