[파이썬 코테 대비 동아리]_개념을 공부하자"스택/큐"편

즈_말 2022. 9. 27. 13:13

스택 / 큐는 ‘선형’ 자료구조 중 하나 이다. 대표적으로 비선형 자료구조에는 ‘트리’,’그래프’가 있다. 몇만 테라 이상의 데이터를 관리해야 되는 상황에서 자원을 효율적으로 사용하고 속도를 올리는 것이 매우 중요하기 때문에. 파이썬 자료구조에선 스택 ( stack )과 큐(Queue)를 사용한다.

스택( Stack )

: 나중에 넣은 데이터가 먼저 반환 되도록 설계한 메모리 구조이다. Last In First Out(LIFO)라고도 한다. 하노이 게임을 생각해보자.

스택 구조에서 데이터의 연산 목록은 push, pop, top, empty등이 있다.

push는 스택에 값을 넣고( 파이썬의 append기능), pop은 스택에서 자료를 빼고 top은 스택의 가장 위에 있는 자료를 반환하고 empty는 스택이 비어있는지 여부를 반환한다.

스택이 활용되는 예시

: 콜스택과 재귀함수 등에서 사용된다.

콜스택이란 컴퓨터 프로그램이 현재 실행중인 함수를 저장하는 역할이다.

재귀함수란 임시 데이터를 스택에 넣고 재귀함수를 빠져나와 퇴각 검색을 할 경우 스택에 넣어 두었던 임시 데이터를 뺀다.

스택 사용법

: 내장 함수를 사용한 방법과 클래스를 이용한 구현이 있다.

a_list.append(1): 괄호 안의 요소를 리스트 맨 뒤에 넣음

a_list = [1,2,3]
a_list.append(1)
# => [1,2,3,1]

a_list.pop() : 맨 뒤 요소를 꺼내고 리스트에서 삭제

a_list = [1,2,3]
a_list.pop()
==>[1,2]

print(a_list.pop())
==>2

클래스를 이용한 스택 구현

class stack:
	def __init__(self):
		self.items = []         #데이터 저장을 위한 리스트 준비
	def push(self,item):
		self.items.append(item) #데이터 저장
	def pop(self):
		try:
			return self.items.pop()   #스택 빼기
		except IndexError:
			print("Stack is empty")  #스택 비었을 경우 예외처리
	def top(self):
		try:
			return self.items[-1]
		except IndexError:
			print("Stack is empty")
	def __len__(self):
		return len(self.items)

stk = stack()
print(Stk)
print(stk.isEmpty())
stk.push(1)
stk.push(2)
print(stk.items)
print(stk.pop())
print(stk.peek())
print(stk.isEmpty())
print(stk.pop())
prrint(stk.isEmpty())

큐 ( Queue )

: 가장 먼저 입력된 데이터가 먼저 출력되는 선입선출 자료구조 ! First In, First Out으로 (FIFO)라고 부르기도 한다.

큐 에서는 Enqueue(인큐)와 Dequeue(디큐)가 있다.

Enqueue 는 큐에서 데이터를 입력하는 기능이고 Dequeue는 큐에서 데이터를 꺼내는 기능이다.

파이썬에서는 queue라는 내장 모듈이 있기 대문에 put()은 큐에 데이터를 넣을 때 사용하는 메서드, get()은 큐에서 데이터를 꺼내는 메서드이다.

아래는 큐의 예시이다.

import queue

#큐 모듈의 큐 클래스 객체 선언
data = queue.Queue()
print(type(data))

data.put(2)
data.put(5)
data.put(8)

print(data.get())
print(data.get())
print(data.get())

>>> <class 'queue.Queue>
2
5
8

큐와 스택을 알아보다보니 덱(Deque)라고 부르는 자료구조도 발견했다.

덱 ( Deque )

: 덱은 데크라고도 불린다. 스택이 LIFO(후입선출) 큐가 FIFO(선입선출)이면 덱은 앞과 뒤 모두에서 삽입과 삭제가 가능하다

append > 뒤에 삽입 기능이며 appendleft > 앞에 삽입 기능이다.

pop > 뒤에서 꺼내기 기능이며 popleft > 앞에서 꺼내기 기능이다.

left만 뒤에 붙여주면 그냥 앞에서 꺼내는 기능이되는거다 !

rotate > 오른쪽으로 밀어내기( ()안에 음수 입력하면 왼쪽으로 밀어낸다 )

from collections import deque

data = deque([1,2,3,4,5,6])

data.append(6) #뒤에 삽입
print(data)

print(data.popleft())  #앞에서 꺼내기
print(data)

data.appendleft(1) #앞에 삽입

print(data.pop())
print(data)

data.rotate(3)
print(data)

data.rotate(-2)
print(data)

예시 문제

https://school.programmers.co.kr/learn/courses/30/lessons/12906

같은 숫자는 싫어!

문제 설명

배열 arr가 주어집니다. 배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다. 이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다. 단, 제거된 후 남은 수들을 반환할 때는 배열 arr의 원소들의 순서를 유지해야 합니다. 예를 들면,

arr = [1, 1, 3, 3, 0, 1, 1] 이면 [1, 3, 0, 1] 을 return 합니다.
arr = [4, 4, 4, 3, 3] 이면 [4, 3] 을 return 합니다.

배열 arr에서 연속적으로 나타나는 숫자는 제거하고 남은 수들을 return 하는 solution 함수를 완성해 주세요.

제한사항

배열 arr의 크기 : 1,000,000 이하의 자연수
배열 arr의 원소의 크기 : 0보다 크거나 같고 9보다 작거나 같은 정수

입출력 예

입출력 예 설명

입출력 예 #1,2문제의 예시와 같습니다.

arr answer

[1,1,3,3,0,1,1]	[1,3,0,1]
[4,4,4,3,3]	[4,3]

def solution(arr):
    answer = []
    answer.append(arr[0])
    for i in range(1,len(arr)):
        if arr[i] != arr[i-1]:
            answer.append(arr[i])
    return answer

주식가격

문제 설명

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

제한사항

prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
prices의 길이는 2 이상 100,000 이하입니다.

입출력 예

입출력 예 설명

1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.

prices return

[1, 2, 3, 2, 3]

[4, 3, 1, 1, 0]

def solution(prices):
    answer = [0]*len(prices)
    for i in range(len(prices)):
        for j in range(i,len(prices)-1):
            if prices[i] <= prices[j]:
                    answer[i] += 1
            else:
                break
    return answer

도저히.. 스택과 큐로 못 풀겠다….

728x90