"이 글은 골든래빗 코딩 테스트 합격자 되기 파이썬 편 6, 7장의 써머리입니다."

06.스택

1) 스택 개념

스택(Stack) : 먼저 입력한 데이터를 제일 나중에 꺼낼 수 있는 자료구조
⇒ 선입후출(FILO$\tiny\bf{First In Last Out}$)

• 푸시(Push) : 스택에 삽입하는 연산
• 팝(Pop) : 스택에서 꺼내는 연산
  
  

2) 스택의 정의

ADT : 추상 자료형(Abstract Data Type), 인터페이스만 있고 실제로 구현은 되지 않은 자료형, 일종의 설계도

스택의 ADT

연산 정의

(1) push() : 스택에 삽입

(2) pop() : 스택에서 삭제

(3) isFull() : 스택이 가득 찼는지 확인

(4) isEmpty() : 스택이 비었는지 확인

(5) top : 최근에 삽입한 데이터의 위치 저장할 변수

if top = 0, 데이터가 1개 있는 것

스택 세부 동작에 대해 조금 더 자세히 알아보기

push(3) 호출 시 내부적으로

(1) isFull() 수행해 우선 data 배열에 데이터가 가득 찼는지 확인

(2) 아니면 top 1만큼 증가

(3) top이 가리키는 위치에 data[0]에 3 추가

pop() 함수 수행 시 내부적으로

(1) isEmpty() 함수를 우선 수행해 data 배열에 데이터가 없는 건 아닌지 확인

(2) 있다면 top 1만큼 감소

(3) 데이터 ‘3’ 반환

→ top이 가리키는 위치는 -1이므로, 실제 data 배열에 데이터가 남아 있더라도 스택은 비어 있다고 봐도 됨

스택 구현하기

스택 ADT 구현

stack = [] # 스택 리스트 초기화

# 스택에 데이터 추가
stack.append(1)
stack.append(2)
stack.append(3)

# 스택에서 데이터 꺼냄
top_element = stack.pop()
next_element = stack.pop()

# 스택의 크기를 구함
stack_size = len(stack)

# top_element : 3
# next_element : 2

3) 몸풀기 문제

문제 08) 괄호 짝 맞추기

열린 괄호나 닫힌 괄호가 마구 뒤섞인 문자열이 있을 때 소괄호가 정상적으로 열고 닫혔는지 판별하는 함수 구현 → 소괄호가 정상적으로 열고 닫혔다면 True, 아니면 False 반환

def solution(s):
  stack = []
  
  for i in s:
    if i == "(":
      stack.append(i)
    elif i == ")":
      if len(stack) == 0:
        return False
      else:
        stack.pop()
        
  if len(stack) == 0:
    return True
  else:
    return False

문제 09) 10 진수를 2 진수로 변환하기

10 진수를 입력 받아 2 진수로 변환하는 함수 구현

def solution(decimal):
  stack = []
  binary = ""
  
  while decimal > 0:
    stack.append(str(decimal % 2))
    decimal //= 2
  
  while stack:
    binary += stack.pop()
    
  return binary

4) 합격자가 되는 모의 테스트

문제 10) 괄호 회전하기

대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어짐, 이 s를 왼쪽으로 x칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 반환하는 함수 완성

def solution(s):
  x = 0
  s_len = len(s)
  
  for i in range(s_len):
    stack = []
    for j in range(s_len):
      c = s[(i + j) % s_len]
      
      if c == "{" or c == "[" or c == "(":
        stack.append(c)
      else:
        if not stack:
          break
        
      if c == ")" and stack[-1] == "(":
        stack.pop()
      elif c == "]" and stack[-1] == "[":
        stack.pop()
      elif c == "}" and stack[-1] == "{":
        stack.pop()
      else:
        break
        
    else:
      if not stack:
        x += 1
  
  return x

문제 11) 짝지어 제거하기

알파벳 소문자로 구성된 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾아 그 둘을 제거한 뒤 앞뒤로 문자열을 이어 붙임, 이 과정을 반복해서 문자열을 모두 제거하면 종료, 문자열 s가 주어 졌을 때 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수 완성

def solution(s):
    answer = 0
    stack = []
    length = len(s)
    
    for i in range(length):
        if stack and s[i] == stack[-1]:
            stack.pop()
        else:
            stack.append(s[i])
    
    if stack:
        answer = 0
    else:
        answer = 1
    
    return answer

07. 큐

1) 큐의 개념

큐(Queue) : 먼저 들어간 데이터가 먼저 나오는 자료구조
⇒ 선입선출(FIFO$\tiny\bf{First In First Out}$)

• 푸시 : 큐에 삽입하는 연산
• 팝: 큐에서 꺼내는 연산
  
  

큐의 특성을 활용하는 분야

대표적으로 여러 이벤트가 발생했을 때 발생한 순서대로 처리할 때 큐 활용

• 작업 대기열 : 네트워크 통신을 할 때, 다수의 클라이언트에서 서버에 작업 요청 시 서버는 요청이 들어온 순서대로 작업 처리
• 이벤트 처리 : 어떤 application이나 system에서 사용자의 이벤트(키보드 입력, 마우스 움직임)를 처리할 때 활용 가능
  
  

큐의 ADT

구분	정의	설명
연산	boolean isFull()	큐에 들어 있는 데이터 개수가 maxsize인지 확인
	boolean isEmpty()	큐에 들어 있는 데이터가 하나도 없는지 확인
	void push(ItemType item)	큐에 데이터 푸시
	ItemType pop()	큐에서 마지막에 푸시한 데이터를 팝하고, 그 데이터 반환
상태	int front	가장 마지막에 팝한 위치 기록 → 큐의 앞
	int rear	최근에 푸시한 데이터의 위치 기록 → 큐의 뒤
	ItemType data[maxsize]	데이터를 관리하는 배열

• 데이터를 넣지 않은 상태 → front = -1, rear = -1
  ⇒ 배열의 인덱스가 0부터 시작하므로 아무것도 넣지 않은 상황 표현을 위해 초깃값을 -1로 지정
  
  

큐의 세부 동작에 대해 조금 더 자세히 알아보기

01 단계> push()

(1) isFull() 연산으로 현재 큐가 가득 찼는지 확인

(2) 아니라면 rear += 1 ⇒ front = -1, rear = 0

(3) rear가 가리키는 위치에 3 push

02 단계> pop()

(1) isEmpty() 연산으로 큐가 비었는지 확인

(2) 비어있지 않다면 front += 1 ⇒ front = 0, rear = 0

(3) isEmpty() 연산 시 큐가 빈 것으로 처리되어 실제 배열의 데이터를 삭제하지 않고도 데이터를 삭제한 것처럼 관리 가능

03 단계> push()

(1) 5를 push하면 isFull() 연산을 수행해 큐가 가득 찼는지 검사, 아니라면 push

(2) 연거푸 6, 8를 push하면 front = 0, rear = 3

04 단계> isFull()일 때 push()

(1) rear가 3이므로 maxmize - 1과 같음

(2) isFull() 연산은 True이므로 push X

$\therefore$ 큐는 front의 다음부터 rear까지를 큐가 관리하는 데이터라고 생각해야 함

큐 구현하기

큐를 간단하게 구현하는 방식

(1) 리스트를 큐처럼 활용하기

queue = []

# 큐에 데이터 추가
queue.append(1)
queue.append(2)
queue.append(3)

# 큐의 맨 앞 데이터 제거
first_item = queue.pop(0)
print(first_item) # 1

# 큐에 데이터 추가
queue.append(4)
queue.append(5)

# 큐의 맨 앞 데이터 제거
first_item = queue.pop(0)
print(first_item) # 2

(2) 덱(Double Ended Queue)을 큐처럼 활용하기

양 끝에서 삽입이나 삭제를 할 수 있다는 특징 때문에 큐를 구현할 때는 덱을 사용하는 것이 좋음

from collections import deque

queue = deque()

# 큐에 데이터 추가
queue.append(1)
queue.append(2)
queue.append(3)

# 큐의 맨 앞 데이터 제거
first_itme = queue.popleft()
print(first_item) # 1

# 큐에 데이터 추가
queue.append(4)
queue.append(5)

# 큐의 맨 앞 데이터 제거
first_item = queue.popleft()
print(first_itme) # 2

2) 몸풀기 문제

문제 15) 요세푸스 문제

N명의 사람이 원 형태로 서 있음. 각 사람은 1번부터 N번까지 번호표를 가짐. 임의의 숫자 K가 주어졌을 때 다음과 같이 사람을 없앰

- 1번 번호표를 가진 사람을 기준으로 K번째 사람을 없앰
- 없앤 사람을 기준으로 다시 K번째 사람을 없앰

from collections import deque

def solution(N, K):
  queue = deque(range(1, N + 1))
  
  while len(queue) > 1:
    for _ in range(K - 1):
      queue.append(queue.popleft())
      
      queue.popleft()
      
  return queue[0]

3) 합격자가 되는 모의 테스트

문제 16) 기능 개발

배포 순서대로 작업 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지 반환하는 함수 완성

import math

def solution(progresses, speeds):
    answer = []
    length = len(progresses)
    
    days_left = [math.ceil((100 - progresses[i]) / speeds[i]) for i in range(length)]
    
    count = 0
    max_day = days_left[0]
    
    for i in range(length):
        if days_left[i] <= max_day:
            count += 1
        else:
            answer.append(count)
            count = 1
            max_day = days_left[i]
            
    answer.append(count)
    return answer