[알고리즘] 자료구조 - 스택, 큐, 덱, 힙, 우선순위 큐

자료구조(Data Structure)

• 효율적인 접근 및 수정을 가능하게 하는 자료의 조직, 관리, 저장
• 데이터 값의 모임, 데이터 간의 관계, 데이터에 적용할 수 있는 함수나 명령
• 자료구조를 통해 효율적인 알고리즘을 사용할 수 있다.

 

구현에 따라

• 배열 - 일반적인 구조. 같은 타입형의 자료가 연속으로 저장된다.
• 튜플 - 둘 이상의 자료형을 묶음으로 다루는 구조
• 연결 리스트 - 노드를 단위로, 노드는 자료와 다음 노드를 가리키는 참조 값으로 구성되어 있따.
• 해시 테이블 - 개체가 해시 값에 따라 인덱싱

 

형태에 따라

• 선형 구조
  • 스택 - LIFO 구조, 먼저 저장된 것이 가장 마지막에 나온다. 파이썬의 리스트 사용
  • 큐 - FIFO 구조, 먼저 저장된 것이 제일 먼저 나온다. 파이썬 리스트를 사용해도 되지만, 리스트는 동적 배열로 큐의 연산을 수행하기에 효율적이지 않아 덱을 사용한다.
  • 덱 - 양쪽에서 넣고 빼고 할 수 있는 일반화된 선형 구조. 파이썬 deque 사용
    • BFS 문제
• 비선형 구조
  • 그래프 - 꼭짓점과 꼭짓점을 잇는 변으로 구성된다. 무향 그래프, 유향 그래프가 있다.
  • 트리 - 뿌리와 뿌리 또는 다른 꼭짓점을 단 하나의 부모로 갖는 꼭짓점으로 이루어진 구조. 부모 자식 관계는 간선으로 표시
    • 이진 트리 - 자식이 최대 두개
      • 힙(heap) - 이진트리의 일종으로 최대값과 최소값을 찾아내는 연산을 빠르게 하기 위해 완전 이진트리(complete binary tree) + 힙 속성(property)를 만족한다. 파이썬 heapq 사용 
        • 우선순위 큐(Priority Queue) : 먼저 저장된 데이터가 먼저 나오는 것이 아니라, 우선순위가 높은 순서대로 나가는 형태의 자료구조. 힙을 이용해서 구현한다.
        • 최소값, 최대값 문제
        • 다익스트라 문제
      • heap property : A가 B의 부모노드이면, A의 키 값과 B의 키 값에는 대소관계가 성립한다.

 

스택 문제 - 1874번 스택 수열

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

1874번: 스택 수열

#n = 8 # 정수의 개수, 최대 정수값
#arr = [4,3,6,8,7,5,2,1]
n = int(input())
stack = []
maxIdx = 1
answer = []
flag = False

# push 오름차순
for i in range(n):
    x = int(input())
    while maxIdx <= x:
        stack.append(maxIdx)
        answer.append('+')
        maxIdx += 1

    if stack[-1] == x:
        stack.pop()
        answer.append('-')

    else: #stack[-1] != x:
        flag = True
        break


if flag:
    print('NO')
else:
    for x in answer:
        print(x)

 

 

큐 문제 - 1158번 요세푸스 문제

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

1158번: 요세푸스 문제

from collections import deque
# n, k = 7, 3 # 사람 수, 제거하는 사람 위치
n, k = map(int,input().split())
queue = deque() # 덱으로 큐 생성
answer = '<'

# 요소 삽입
for x in range(1, n+1):
    queue.append(x)

while queue:
    for x in range(k-1):
        element = queue.popleft() # 맨 왼쪽에 있는 값 꺼내서
        queue.append(element) # 맨 뒤로 삽입
    answer += str(queue.popleft()) + ', '

print(answer[:-2]+'>')

 

큐 문제 - 1966번 프린터 큐

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

1966번: 프린터 큐

from collections import deque

tc = int(input()) # 테스트 케이스 수
for _ in range(tc):
    n, m = map(int, input().split()) # 문서 개수, 찾을 위치
    arr = list(map(int, input().split())) # 문서 중요도 배열
    pq = deque() # 덱으로 큐 생성

    # (인덱스, 중요도) 값으로 덱 요소 삽입
    for x in range(len(arr)):
        pq.append((x, arr[x]))
    importList = sorted(arr, reverse=True)  # 중요도 순서
    importIdx = 0
    cnt = 0
    while pq:
        element = pq.popleft()
        if importList[importIdx] == element[1]:  # 중요도 순서가 맞는 경우
            importIdx += 1
            cnt += 1
            if element[0] == m:  # 찾는 인덱스와 일치할 경우
                print(cnt)
                break
        else:
            pq.append(element)  # 맨 왼쪽 오른쪽에 삽입

 

덱 문제 - 2346번 풍선 터뜨리기

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

2346번: 풍선 터뜨리기

import sys
from collections import deque

n = int(input())
dq = deque(enumerate(map(int, input().split())))
answer = []

while dq:
    idx, nextIdx = dq.popleft()
    answer.append(idx+1)

    if nextIdx > 0:
        dq.rotate(-(nextIdx-1))
    else:
        dq.rotate(-nextIdx) # rotate = d.appendleft(d.pop()) : 오른쪽 끝값을 왼쪽 끝으로 보낸다.

print(*answer)

 

우선순위 큐 문제 - 11286번 절댓값 힙

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

11286번: 절댓값 힙

import heapq
import sys

n = int(input())  # 연산의 개수 18
# arr = [1, -1, 0, 0, 0, 1, 1, -1, -1, 2, -2, 0, 0, 0, 0, 0, 0, 0]  # 연산에 대한 정보
# 0 x : 배열에서 절댓값이 가장 작은 값 출력하고 값 제거
# 1 x : 값을 넣는 연산
heap = []

for i in range(n):
    x = int(sys.stdin.readline())
    if x != 0:  # 값 넣기
        heapq.heappush(heap, (abs(x), x))
    else:
        # 배열에서 절댓값이 가장 작은 값 출력하고 값 제거
        # 같은 값이 여러개면 가장 작은 수 출력
        # 배열이 비어있으면 0 출력
        if len(heap) == 0:
            print(0)
        else:
            element = heapq.heappop(heap) # heappop : 가장 작은 값 제거 + return
            print(element[1])

 

우선순위 큐 문제 - 1715번 카드 정렬하기

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

1715번: 카드 정렬하기

import heapq
n = int(input()) # 숫자 카드 묶음 개수
heap = []
answer = 0

for _ in range(n):
    x = int(input())
    heapq.heappush(heap, x)

while len(heap)!=1:
    a = heapq.heappop(heap)
    b = heapq.heappop(heap)
    answer += a + b
    heapq.heappush(heap, a+b)

print(answer)