2024.04.11. 알고리즘

스택과 큐의 차이

스택 - 탑과 같음

입구가 하나 뿐이므로 들어온 놈이 다시 나가야 뒤에 있는 녀석들이 나갈 수 있음

LIFO(Last in First Out)

 

큐 - 파이프

들어온 게 가장 마지막에 나감

들어오는 구멍과 나가는 구멍이 다름

인풋 구멍과 아웃풋 구멍이 다름!

FIFO(First in First Out)

 

스택 알고리즘 문제

# 사용자로부터 수열의 길이를 입력받습니다.
N = int(input())
# 입력받은 길이 N에 맞게 리스트 A를 0으로 초기화합니다.
A = [0]*N

# 사용자로부터 N개의 수를 입력받아 리스트 A를 구성합니다.
for i in range(N):
    A[i] = int(input())

# 스택을 구현할 리스트를 초기화합니다.
stack = []
# 현재 스택에 추가해야 할 다음 숫자를 관리합니다.
num = 1
# 결과를 판단하기 위한 변수를 True로 초기화합니다. False일 경우 수열을 생성할 수 없음을 의미합니다.
result = True
# 수열 생성 과정을 나타낼 문자열을 초기화합니다.
answer = ""

# 입력받은 수열의 각 요소에 대하여 반복합니다.
for i in range(N):
    su = A[i]
    # 현재 수열의 요소가 num보다 크거나 같을 경우 스택에 숫자를 추가합니다.
    if su >= num:
        # su가 num보다 크거나 같을 때까지 스택에 숫자를 추가하고, "+" 연산을 기록합니다.
        while su >= num:
            stack.append(num)
            num += 1
            answer += "+\n"
        # 수열의 현재 요소에 도달했으므로, 스택에서 해당 요소를 제거하고 "-" 연산을 기록합니다.
        stack.pop()
        answer += "-\n"
    else:
        # 스택의 최상단 요소가 현재 수열의 요소보다 큰 경우 수열을 생성할 수 없으므로 "NO"를 출력하고 반복을 중단합니다.
        n = stack.pop()
        if n > su:
            print("NO")
            result = False
            break
        else:
            # 스택의 최상단 요소가 현재 수열의 요소보다 작거나 같은 경우, 정상적으로 "-" 연산을 기록합니다.
            answer += "-\n"

# 모든 반복이 성공적으로 완료된 경우(수열을 생성할 수 있는 경우), "+"와 "-" 연산의 순서를 출력합니다.
if result:
    print(answer)

 

으앙 어려워

책 74페이지

 

큐 코드 이해하기 알고리즘

# deque 모듈을 임포트하여 양방향 큐 기능을 사용할 수 있게 합니다.
from collections import deque
# 사용자로부터 카드의 총 개수 N을 입력받습니다.
N = int(input())
# deque 객체를 생성하여 myQueue라는 이름의 큐를 초기화합니다.
myQueue = deque()

# 1부터 N까지의 숫자를 큐에 차례대로 추가합니다. 이는 초기 카드 더미를 나타냅니다.
for i in range(1, N+1):
    myQueue.append(i)

# 큐의 길이가 1보다 큰 동안(즉, 카드가 1장 이상 남아 있는 동안) 반복합니다.
while len(myQueue) > 1:
    # 큐의 맨 앞(맨 위의 카드)을 제거합니다. 이는 카드를 버리는 동작을 나타냅니다.
    myQueue.popleft()
    # 큐의 맨 앞의 요소(이제 맨 위의 카드가 됨)를 제거한 후, 이 카드를 큐의 맨 뒤로 옮깁니다.
    myQueue.append(myQueue.popleft())

# 반복이 종료되면, 큐에는 마지막으로 남은 카드 한 장만이 남게 됩니다. 이 카드의 번호를 출력합니다.
print(myQueue[0])

 

슈도코드?

N(카드의 개수) myQueue(카드 저장 자료구조)

for 카드의 개수만큼 반복:
    큐에 카드 저장
    
while 카드가 1장 남을 때까지:
    맨 위의 카드를 버림: popleft()
    맨 위의 카드를 가장 아래의 카드 밑으로 이동: popleft() -> append()
    
마지막으로 남은 카드 출력