기본 자료구조

지니🧸·2023년 8월 30일

알고리즘

목록 보기

5/43

이 게시글은 이 레포지토리를 공부하며 작성했습니다.

Stack

연산	시간복잡도
삽입	O(1)
삭제	O(1)

First in, Last out: 처음 들어간 것이 가장 마지막으로 나온다
- 삽입과 삭제가 같은 구간에서 일어난다
용도:
- 이전에 활용한 데이터에 대한 역추적
- 나중에 들어온 데이터가 빨리 나갈 때
구현:
- LifoQueue 구현체
- List의 pop() 사용: list.pop()는 끝 원소 삭제라서 시간복잡도가 O(1)이다

Queue

연산	시간복잡도
삽입	O(1)
삭제	O(1)

First in, First out: 처음 들어간 것이 처음으로 나온다
용어
- front: 맨 앞
- rear: 맨 뒤
- enqueue: 삽입 연산
- dequeue: 삭제 연산
용도:
- 순차적으로 진행되어야 하는 일
- 제거해야 하는 데이터의 위치가 맨 끝이 아닐 때
구현으로 List는 사용하지 말자
- 원소를 삭제할 때, 첫 원소부터 삭제하니까 list.pop(0)
- 삭제 후 모든 원소 이동하는데에 O(N)이 든다

Deque

연산	시간복잡도
삽입	O(1)
삭제	O(1)

Queue/Stack의 구조를 합친 구조
맨앞 & 맨뒤에서 삽입/삭제 가능

Queue vs. Deque

Queue

import queue

_queue = queue.Queue()
for i in range(5):
	_queue.put(i)


while _queue.qsize():
	print(_queue.get())


if _queue.empty():
	print("Queue is empty")

멀티스레드 환경에 적합
queue.Queue(): initialize queue
put(): 값 추가
qsize(): queue 크기
get(): 원소를 삭제하고 리턴한다
empty(): 큐가 비었는지 boolean 리턴

Deque

from collections import deque

dq = deque("1234")

dq.append("5")
dq.appendleft("10")

dq.rotate(1)

while len(dq):
	print(dq[0])
    dq.popleft()

append() - 오른쪽에 삽입
appendleft() - 왼쪽에 삽입
pop() - 오른쪽에 삭제
popleft() - 왼쪽에 삭제
dq = deque(range(1, n)) - 1~n 까지의 수를 가진 deque

Queue 연습문제

백준 2164

N장의 카드가 있을 때, 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 카드가 한 장 남을 때까지 맨 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래 있는 카드 밑으로 옮기는 행위를 반복한다. N이 주어졌을 때, 제일 마지막에 남는 카드를 구하는 프로그램을 작성하시오

import sys
from collections import deque
input = sys.stdin.readline

n = int(input())
deq = deque(range(1, n+1))

sol = 1
while len(deq) > 1:
    deq.popleft()
    deq.append(deq.popleft())
    sol = deq[0]
print(sol)

백준 10773

첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000). 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경우 해당 수를 쓴다.정수가 "0"일 경우에 지울 수 있는 수가 있음을 보장할 수 있다. 재민이가 최종적으로 적어 낸 수의 합을 출력한다. 최종적으로 적어낸 수의 합은 231-1보다 작거나 같은 정수이다.

import sys
from collections import deque
input = sys.stdin.readline

k = int(input())
nums = deque()
for i in range(k):
    n = int(input())
    if n == 0:
        nums.pop()
    else:
        nums.append(n)
print(sum(nums))

백준 5430

선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다. 함수 R은 배열에 있는 수의 순서를 뒤집는 함수이고, D는 첫 번째 수를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다. 함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. 예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 수를 버리는 함수이다. 배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램을 작성하시오.

import sys
input = sys.stdin.readline

t = int(input())
for i in range(t):
    p = input()
    n = int(input())
    arr = input().strip("[]\n")
    if p.count("D") > n:
        print("error")
        continue
    for j in range(len(p)):
        funct = p[j]
        if funct == "D":
            arr = arr[2:]
        elif funct == "R":
            arr = arr[::-1]
    print("["+arr+"]", flush=True)

이렇게 풀었더니 테케는 통과하지만 처참한 시간초과를 맛볼 수 있었다.

그래서 덱으로 다시 풀어봄!

import sys
from collections import deque
input = sys.stdin.readline

t = int(input())
for i in range(t):
    p = input()
    n = int(input())
    arr = input()
    deq = deque() if n==0 else deque(arr.strip("[]\n").split(","))

    br = False
    reverse_count = 0
    for j in p:
        if j == "D":
            if len(deq) == 0:
                br = True
                print("error")
                break
            elif reverse_count % 2 == 0:
                deq.popleft()
            else:
                deq.pop()
        elif j == "R":
            reverse_count += 1
    if reverse_count % 2 == 1:
        deq.reverse()
    if not br:
        print("[" + ",".join(deq) + "]")

백준 2841

상근이의 상상의 친구 외계인은 손가락을 수십억개 가지고 있다. 어느 날 외계인은 기타가 치고 싶었고, 인터넷에서 간단한 멜로디를 검색했다. 이제 이 기타를 치려고 한다. 보통 기타는 1번 줄부터 6번 줄까지 총 6개의 줄이 있고, 각 줄은 P개의 프렛으로 나누어져 있다. 프렛의 번호도 1번부터 P번까지 나누어져 있다. 멜로디는 음의 연속이고, 각 음은 줄에서 해당하는 프렛을 누르고 줄을 튕기면 연주할 수 있다. 예를 들면, 4번 줄의 8번 프렛을 누르고 튕길 수 있다. 만약, 어떤 줄의 프렛을 여러 개 누르고 있다면, 가장 높은 프렛의 음이 발생한다.
예를 들어, 3번 줄의 5번 프렛을 이미 누르고 있다고 하자. 이때, 7번 프렛을 누른 음을 연주하려면, 5번 프렛을 누르는 손을 떼지 않고 다른 손가락으로 7번 프렛을 누르고 줄을 튕기면 된다. 여기서 2번 프렛의 음을 연주하려고 한다면, 5번과 7번을 누르던 손가락을 뗀 다음에 2번 프렛을 누르고 연주해야 한다.
이렇게 손가락으로 프렛을 한 번 누르거나 떼는 것을 손가락을 한 번 움직였다고 한다. 어떤 멜로디가 주어졌을 때, 손가락의 가장 적게 움직이는 회수를 구하는 프로그램을 작성하시오. 첫째 줄에 멜로디에 포함되어 있는 음의 수 N과 한 줄에 있는 프렛의 수 P가 주어진다. (1 ≤ N ≤ 500,000, 2 ≤ P ≤ 300,000)
다음 N개 줄에는 멜로디의 한 음을 나타내는 두 정수가 주어진다. 첫 번째 정수는 줄의 번호이고 두 번째 정수는 그 줄에서 눌러야 하는 프렛의 번호이다. 입력으로 주어진 음의 순서대로 기타를 연주해야 한다. 줄의 번호는 N보다 작거나 같은 자연수이고, 프렛의 번호도 P보다 작거나 같은 자연수이다.

from collections import deque
import sys

input = sys.stdin.readline

n, p = map(int, input().split())
play = [[0] for _ in range(6)]
count = 0
for i in range(n):
    line, pret = map(int, input().split())
    line -= 1

    while play[line][-1] > pret:
        play[line].pop()
        count += 1
    if play[line][-1] == pret:
        continue

    play[line].append(pret)
    count += 1



print(count)