스택, 큐 알아보기

이유 모르고 코테 준비를 하면서 쓰게된 스택, 큐에 대해 정확히 공부하려 포스팅합니다. :)

 

우선 대강이나마 알고 있던 사실을 두서없이 쓰면

 

1. 스택 -> 후입선출

2. 큐 -> 선입선출

3. 스택과 큐 모두 자료 입출력에 O(1)의 시간복잡도를 가짐.

queue의 경우

Python에서 List에서 pop(0) 을 하게 될 경우 O(n) 시간 복잡도를 가지기 때문에 collections deque 모듈을 사용해서 구현해야하고, ( dequeue -> 선입 선출, 선입 후출 모두 가능 ) Swift에서 removefirst 를 할 경우도 O(n) 의 시간 복잡도를 가지기 때문에 따로 클래스를 구현해서 사용 해야함. 

 

구현 내용은 Swift 언어로 코테를 준비하면서 정리한 내용에 정리해놓음 ( dequeue 검색. )

https://www.notion.so/1d735dc9fbee422f94dd2bed5cee6750

코테용으로 준비함

4. bfs ( 넓이 우선 탐색) 를 활용하기 위해선 큐 구조가 필요함. ( 차후 포스팅 :0 )

예제문제 및 풀이

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

프로그래머스

from collections import deque

dx = [1,-1,0,0]
dy = [0,0,1,-1]
answer = []
def bfs(maps, n , m, x, y):
    global dx, dy, answer 
    value = int(maps[y][x])
    maps[y][x] = "X"
    q = deque()
    q.append((x,y))
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if ny >= m or ny < 0 or nx >= n or nx < 0 or maps[ny][nx] == "X":
                continue
            q.append((nx,ny))
            value += int(maps[ny][nx])
            maps[ny][nx] = "X"
    return value
   
def solution(maps):    
    global answer
    n = len(maps[0])
    m = len(maps)
    graph = list(map(list,maps))
    for y in range(len(graph)):
        for x in range(len(graph[0])):
            if graph[y][x] != "X":
                answer.append(bfs(graph, n , m, x, y))
    answer.sort()
    if len(answer) == 0 :
        return [-1]
    return answer

 

 

 

5. Python 에서 스택을 list로 구현하는데

element in , del, reverse, min, max, count, index, pop(x) 모두 시간 복잡도가 O(n)임.

( 반면 딕셔너리의 key in 의 경우 O(1) 시간 복잡도라서 코딩테스트에서 단순히 Dictionary Comprehension을 통해 List 를 변환해 탐색할 경우 풀리는 경우도 꽤나 많음. )

컴프리헨션의 경우 문범우란 분께서 엄청 잘 정리해놓은 글이 있어서 링크 남김

https://doorbw.tistory.com/174

 

정도 였습니다.

 

그럼 다음은 이번에 공부한 내용에 대해 정리합니다.

1. Python 의 경우 고정길이의 스택을 생성하는 경우가 드물지만. C의 경우 스택의 크기를 미리 정하고 만듬. ( 잘 모는데 맞나요?)

 

2. 스택은

stk (스택 배열) -> List형 배열

capacity (스택 크기) -> 스택의 최대 크기

ptr (스택 포인터) -> 스택에 쌓여있는 데이터의 개수를 나타내는 정수값

등으로 구성됨

 

3. Python collections deque모듈의 주요 함수 

append(x) 추가

appendleft(x) 왼쪽 추가

clear() 전체 삭제

count(x) 개수 카운트

extend(iterable) 배열 붙임

extendleft(iterable) 왼쪽으로  배열 붙임

index(x[, start [ ,stop]]) deque 안의 원소 위치 반환

insert(i,x) 원하는 위치에 원소 추가

pop() 원소 삭제

popleft() 왼쪽 원소 삭제

remove(value) value 가 일치하는 첫번째 원소삭제

reverse() 원소 역순 정렬

rotate(n = 1) 원소를 오른쪽으로 밀어냄 (음수의 경우 왼쪽으로 밀어냄)

 

4. 큐 알아보기

큐에 데이터 추가 작업 -> 인큐(enqueue), 데이터 꺼내는 작업 -> 디큐(dequeue)

큐 데이터 꺼내는 쪽 -> 프런트(Front), 데이터 넣는 쪽 -> 리어(Rear)

 

5. 우선순위큐

인큐 시 데이터의 우선순위를 부여하여 추가하고, 디큐시 우선순위가 가장 높은 데이터를 꺼내는 방식

Python에서 heapq의 heappush, heappop 모듈로 간단하게 구현 가능

heappush(heap, data), heappop(data)

예제문제 및 풀이

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

from heapq import heappop, heappush

def solution(n, k, enemy):
    heap = []
    for idx in range(len(enemy)):
        heappush(heap, -enemy[idx])
        n -= enemy[idx]
        if n < 0 and k == 0:
            return idx
        elif n < 0 and k > 0:
            k -= 1
            n -= heappop(heap)
    return idx + 1

 

6. 링버퍼 ( 원형 큐 )

디큐 시 배열 안의 원소를 옮기지 않는 큐를 구현할 때 사용

언제 필요한지에 대해선 Edward 란 분이 너무 잘 정리해 놓으셔서 링크남김.

 

https://openstory.tistory.com/29

링버퍼란? 그리고 사용 이유는?

https://charang.tistory.com/13

avr serial통신하다가 버퍼의 필요성을 느끼고 찾은 자료