알고리즘 스터디 1주차 ( 스택, 큐 개념 + 백준 문제 풀이)

스택 (stack)?
- LIFO(Last In First Out) 후입선출
- Push&Pop 으로 자료를 넣고 꺼내는 작업을 할 수 있다.
- 파이썬은 스택 자료구조는 따로 제공하지 않는다. 다만 기본 클래스인 list를 통해 스택을 흉내 낼 수 있다.
Stack - push
스택에 원소를 넣을 때에는 append 메서드를 이용해 리스트의 가장 마지막에 원소를 넣도록 한다.

Stack - pop
스택에서 원소를 제거할 때에는 pop 메소드를 이용해 리스트의 가장 마지막 원소를 제거해준다. 이때, pop 메서드에 의해 제거한 원소를 리턴 받을 수 있다.

Stack - top
스택에서 원소를 제거하지 않고 가져오기만 할 때에는 [-1]을 이용하도록 한다.

 

https://www.acmicpc.net/problem/10828

10828번: 스택

import sys

stack = []

def push(x):
    stack.append(x)

def pop():
    if len(stack) > 0 :
        return stack.pop()
    else:
        return '-1'

def size():
    return len(stack)

def empty():
    if len(stack) > 0:
        return '0'
    else:
        return '1'
def top():
    if len(stack) > 0:
        return stack[-1]
    else :
        return '-1'

n = int(input())

for _ in range(n):
    #시간 초과로 인한 sys 내장 라이브러리 사용
    #띄어쓰기와 \n까지 포함하므로 split()을 이용하는 것이 좋다.
    #여러줄 입력 받고 싶다면 sys.stdin
    x = sys.stdin.readline()

    if 'push' in x:
        push(x.split()[1])
    elif 'pop' in x:
        print(pop())
    elif 'size' in x:
        print(size())
    elif 'empty' in x:
        print(empty())
    else:
        print(top())

https://www.acmicpc.net/problem/10773 제로

10773번: 제로

stack = []
n = int(input())

for _ in range(n) :
    x = int(input())

    if x != 0 :
        stack.append(x)
    else :
        stack.pop()


def add(length) :
    sum = 0
    for i in range(length) :
        sum += stack[i]
    return sum


print(add(len(stack)))

큐 (Queue)?
- FIFO(First In First Out) 선입선출
- 일렬로 줄 서 있는 자료 구조
- 데이터가 입력된 순서대로 처리해야할 때 필요가 있음.
- 선형과 환형이 있다.
- 파이썬에서는 collection 모듈의 deque로 큐를 구현할 수 있다.

 

https://www.acmicpc.net/problem/18258

18258번: 큐 2

from collections import deque
import sys

queue = deque()

def push(x):
    queue.append(x)
def pop():
    if len(queue) > 0 :
        return queue.popleft()
    else:
        return -1
def size():
    return len(queue)
def empty():
    if len(queue) > 0 :
        return 0
    else:
        return 1
def front():
    if len(queue) > 0 :
        return queue[0]
    else:
        return -1
def back():
    if len(queue) > 0:
        return queue[len(queue)-1]
    else:
        return -1


n = int(input())

for _ in range(n):
    command = sys.stdin.readline()
    if 'push' in command:
        push(command.split()[1])
    elif 'pop' in command:
        print(pop())
    elif 'size' in command :
        print(size())
    elif 'empty' in command:
        print(empty())
    elif 'front' in command:
        print(front())
    elif 'back' in command:
        print(back())

https://www.acmicpc.net/problem/2164

2164번: 카드2

from collections import deque

n = int(input())
q = deque()

# N장의 카드 생성
for i in range(1, n + 1):
    q.append(i)

for _ in range(n):
    if len(q) > 1 :
        q.popleft()

    if len(q) == 1:
        print(q.popleft())
        break
    else:
        q.append(q.popleft())

 더 좋은 풀이를 많이 보고 따라해봐야겠다.

for문을 고집하기보다 while에 적합한 경우가 있다면 while을 써보는 방법을 찾아봐야겠다는 생각을 했음.