[크래프톤 정글] 13일 - Stack

오늘 한 일🌴
- Stack 공부
- Algorithm 문제 풀이(2470, 11053, 1629, 10828, 10773, 9012, 17608, 2493)

Stack

데이터를 임시 저장할 때 사용하는 자료구조이다. 데이터의 입력과 출력 순서는 후입선출(LIFO: Last In First Out) 방식이다.

 

고정 길이 Stack

class FixedStack:
    """고정 길이 스택 클래스"""

    class Empty(Exception):
        """비어 있는 FixedStack에 팝 또는 피크할 때 내보낸다."""
        pass

    class Full(Exception):
        """가득 찬 FixedStack에 푸시할 때 내보내는 예외 처리"""
        pass

    def __init__(self, capacity):
        """스택 초기화"""
        self.stk = [None]*capacity  # 스택 본체
        self.capacity = capacity    # 스택의 크기
        self.ptr = 0                # 스택 포인터

    def __len__(self):
        """스택에 쌓여 있는 데이터 개수 반환"""
        return self.ptr

    def is_empty(self):
        return self.ptr <= 0

    def is_full(self):
        return self.ptr >= self.capacity

    def push(self, value):
        """스택에서 value를 푸시(데이터를 넣음)"""
        if self.is_full():          # 스택이 가득 차 있는 경우
            raise FixedStack.Full
        self.stk[self.ptr] = value
        self.ptr += 1

    def pop(self):
        """스택에서 데이터를 팝(꼭대기를 꺼냄)"""
        if self.is_empty():         # 스택이 비어 있는 경우
            raise FixedStack.Empty
        self.ptr -= 1
        return self.stk[self.ptr]

    def peek(self):
        """스택에서 데이터를 피크: 보기만 한다."""
        if self.is_empty():         # 스택이 비어 있는 경우
            raise FixedStack.Empty
        return self.stk[self.ptr - 1]

    def clear(self):
        """스택을 비움: 모든 데이터를 삭제"""
        self.ptr = 0

    def find(self, value):
        """스택에서 value를 찾아 인덱스를 반환: 없으면 -1 반환"""
        for i in range(self.ptr - 1, -1, -1):   # 꼭대기부터 선형 검색
            if self.stk[i] == value:
                return i
        return -1

    def count(self, value):
        """스택에 있는 value 개수를 반환"""
        c = 0
        for i in range(self.ptr):
            if self.stk[i] == value:
                c += 1
        return c

    def __contains__(self, value):
        """스택에 value가 있는지 판단"""
        return self.count(value) > 0

    def dump(self):
        """덤프: 스택 안의 모든 데이터를 바닥부터 꼭대기 순으로 출력"""
        if self.is_empty():
            print('스택이 비어 있습니다.')
        else:
            print(self.stk[:self.ptr])

Deque를 사용한 Stack

from typing import Any
from collections import deque

class Stack:
    """고정 길이 스택 클래스(collections.deque 사용)"""

    def __init__(self, maxlen):
        """스택 초기화"""
        self.capacity = maxlen
        self.__stk = deque([], maxlen)

    def __len__(self):
        """스택에 쌓여 있는 데이터 개수를 반환"""
        return len(self.__stk)

    def is_empty(self):
        """스택이 비어 있는지 판단"""
        return not self.__stk

    def is_full(self):
        """스택이 가득 차 있는지 판단"""
        return len(self.__stk) == self.__stk.maxlen

    def push(self, value):
        """스택에 value 푸시"""
        self.__stk.append(value)

    def pop(self):
        """스택에서 데이터 팝"""
        return self.__stk.pop()

    def peek(self):
        """스택에서 데이터를 피크"""
        return self.__stk[-1]

    def clear(self):
        self.__stk.clear()

    def find(self, value):
        """스택에서 value를 찾아 인덱스를 반환(찾지 못하면 -1을 반환)"""
        try:
            return self.__stk.index(value)
        except ValueError:
            return -1

    def count(self, value):
        """스택에 포함되어 있는 value의 개수를 반환"""
        return self.__stk.count(value)

    def __contains__(self, value):
        """스택에 value가 포함되어 있는지 판단"""
        return self.count(value)

    def dump(self):
        """스택 안에 있는 모든 데이터를 나열(바닥에서 꼭대기 순으로 출력한다.)"""
        print(list(self.__stk))

Algorithm

2470: 두 용액

2470번: 두 용액

계속 시간 초과나서 확인해보니 elif가 문제였다.
아래 부분에서 else 대신 elif로 판단하기 계속 시간 초과가 났다. 평소에 공부 차원에서 else 보다 elif로 구분하는 편인데, 알고리즘에서는 하지 않는게 좋겠다.

if abs(total) < answer:
    answer = abs(total)
    left_value = liquid[left]
    right_value = liquid[right]
    if answer == 0:
        break 
    # 양수이면
    if total > 0:
        right -= 1
    # 음수이면
    else:
        left += 1

11053: 가장 긴 증가하는 부분 수열

11053번: 가장 긴 증가하는 부분 수열

dp와 이진탐색 모두 풀이할 수 있는 문제다.
dp만 사용하면 n*n의 복잡도를 갖기 때문에 범위가 커지면 적절하지 않다. dp에 이진탐색을 사용하면 nlogn으로 풀이할 수 있다.
가장 인접한 원소 중에 큰 값을 찾는 과정에서 어제 공부한 인접한 원소 찾는 코드를 사용할 수 있었다.

1629: 곱셈

1629번: 곱셈

재귀 함수를 사용하면 된다.

10828, 10773, 9012, 17608

금방 풀 수 있는 문제라 생략!

2493: 탑

구현으로 하면 시간초과난다.
stack을 이용해서 처음에 데이터를 저장할 때부터 신경쓴다는 점이 인상깊었다. 새로운 원소를 넣을 때마다 앞에 값과 비교하여 원소를 추가하거나 아니면 빼면서 결과 리스트를 채워나간다.

---

오늘은 토요일이라서 푹~ 잤다. 그래도 아침먹고, 10시에 도착했다. 하지만 역시 피곤하다. 그래서 리프레시하려고 pycharm 에디터 색을 바꿨다.
오늘의 기쁨 모먼트라면 저녁 먹으면서 본 피겨 프리 경기에서 차준환 선수가 1위했다.🇰🇷🏅⛸️

 

내일 할 일👊
- 알고리즘 오답
- 알고리즘 문제 풀이: 2110, 6549, 10830, 2261, 10000, 2504, 2812
- main, python memory 공부하기
- 쿠키, 세션, jwt