큐(Queue)란?
- 큐(Queue)는 스택과 다르게 먼저 입력된 데이터가 먼저 출력되는 구조이다.
- 큐의 데이터 저장 방식은 데이터를 입력할 때 후단을 통해 전단으로 들어간다. 이후 출력할 때 전단에 있는 데이터를 먼저 출력하게 된다.
- 예를 들어, 3을 입력하고, 9를 입력하고, 출력을 1회 실시한다고 할때,
- 먼저 삽입된 3이 처음 들어왔고, 그 후 삽입된 9는 3 뒤에 있다.
- 이때 출력을 1회하면 처음 삽입된 3이 가장 먼저 출력된다.
- 큐 자료구조는 입력 데이터를 가장 먼저 출력하기 위해 만든 자료구조로써, 컴퓨터 속에서는 프린터, 선착순 프로그램 등이 있다.
- 큐를 통해 사용하는 기능은 크게 6가지 이다.
1. push : 데이터를 큐에 추가한다(큐의 전단부터 후단으로 차곡차곡 쌓는다).
2. pop : 큐의 가장 앞(전단) 데이터를 삭제한다.
3. size : 큐에 데이터가 몇 개 들어있는지 확인한다.
4. empty : 큐가 비어 있는지 확인한다(데이터가 없는지 확인한다).
5. front : 큐의 가장 앞(전단) 데이터가 무엇인지 확인한다.
6. back : 큐의 가장 뒤(후단) 데이터가 무엇인지 확인한다.큐를 사용하는 예제 1 - 큐 2
[문제]
정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 여섯 가지 이다.- push X : 정수 X를 큐에 넣는 연산이다. - pop : 큐에서 가장 앞에 있는 정수를 빼고 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다. - size : 큐에 들어있는 정수의 개수를 출력한다. - empty : 큐가 비어 있으면 1, 아니면 0을 출력한다. - front : 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다. - back : 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.[입력]
첫째 줄에 주어지는 명령의 수 N(1 <= N <= 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100.000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.
[출력]
출력해야 하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.
예제 입력 1 예제 출력 1 15 1 push 1 2 push 2 2 front 0 back 1 size 2 empty -1 pop 0 pop 1 pop -1 size 0 empty 3 pop push 3 empty front
해답코드
import sys
from collections import deque # 파이썬에서 큐를 사용하기 위해서 deque라는 라이브러리를 이용한다.
n = int(sys.stdin.readline())
queue = deque([])
for i in range(n):
command = sys.stdin.readline().split() # 명령어를 한 줄씩 입력받은 후
if command[0] == 'push': # 명령어가 push라면
queue.append(command[1]) # 큐에 숫자를 넣는다(append() 함수를 이용)
elif command[0] == 'pop': # 명령어가 pop이라면
if not queue: # 큐의 크기가 0이라면 -1을 출력한다.
print(-1)
else: # 큐의 크기가 0이 아니라면 큐의 전단을 출력하고 삭제한다(popleft() 함수를 이용)
print(queue.popleft())
elif command[0] == 'size': # 명령어가 size라면
print(len(queue)) # 큐의 크기를 출력한다.
elif command[0] == 'empty': # 명령어가 empty라면
if not queue: # 큐의 크기가 0이라면 1을 출력한다.
print(-1)
else: # 큐의 크기가 0이 아니라면 0을 출력한다.
print(0)
elif command[0] == 'front': # 명령어가 front라면
if not queue: # 큐의 크기가 0이라면 -1을 출력한다.
print(-1)
else: # 큐의 크기가 0이 아니라면 큐의 전단을 출력한다.
print(queue[0])
elif command[0] == 'back': # 명령어가 back라면
if not queue: # 큐의 크기가 0이라면 -1을 출력한다.
print(-1)
else: # 큐의 크기가 0이 아니라면 큐의 후단을 출력한다.
print(queue[-1])큐를 사용하는 예제 2 - 카드 2
[문제]
N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.
예를 들어 N = 4인 경우를 생각해 보자, 카드는 제일 위에서부터 1234의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.
N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.
[입력]
첫째 줄에 정수 N(1 <= N <= 500,000)이 주어진다.
[출력]
첫째 줄에 남게 되는 카드의 번호를 출력한다.
예제 입력 1 예제 출력 1 6 4
문제설명
- 1 ~ n 의 번호가 붙은 n장의 카드가 낮은 번호일수록 위에, 높은 번호일수록 아래인 상태로 있다, 이 상태에서,
1. 제일 위에 있는 카드를 바닥에 버린다.
2. 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.- 1 ~ 2의 과정을 순서대로 반복하여 카드가 한 장 남으면 그 숫자를 출력하면 되는 문제이다.
- 1번의 제일 위에 있는 카드를 바닥에 버리는 것은 큐의 전단을 삭제하는 것과 같으며, 2번의 제일 위에 있는 카드를 제일 아래에 있는 카드로 옮기기 위해서 큐의 전단을 큐의 후단으로 입력해주면 된다.
해답코드 _ 1
import sys
from cellections import deque
N = int(sys.stdin.readline())
queue = deque()
for i in range(N): # 큐의 후단에 1부터 n의 숫자를 삽입한다.
queue.append(i + 1)
while lne(queue) > 1: # 큐의 크기가 1보다 클 때, 큐의 전단을 삭제, 큐의 전단을 후단에 삽입을 반복한다.
queue.popleft()
queue.append(queue.popleft())
print(queue.pop()) # 큐에 남은 숫자를 출력한다.해답코드 _ 2
- 여기에 추가적으로 실용적으로 많이 쓰이는 디큐(deque)를 추가로 알아보자.
- 디큐는 스택과 큐의 기능을 합친 것이다.
- 1, 2, 3, 4, 5 와 같이 데이터 5개가 있을 때,
1) 디큐의 전단의 1을 삭제하는 데 시간복잡도는 O(1)이다. -> 2 3 4 5
2) 디큐의 후단의 5를 삭제하는 데 시간복잡도는 O(1)이다. -> 1 2 3 4
3) 디큐의 전단에 0을 삽입하는 데 시간복잡도는 O(1)이다. -> 0 1 2 3 4 5
4) 디큐의 후단에 0을 삽입하는 데 시간복잡도는 O(1)이다. -> 1 2 3 4 5 0- 디큐에는 위의 4가지 기능이 있으며, 실용적으로 쓰이는 자료구조이다.
- 파이썬 같은 경우 큐를 사용하기 위해 deque 라이브러리를 이용한다.
- 이를 적용하여 카드 2 문제의 코드를 조금 수정해 보면
import sys
from collections import deque
N = int(sys.stdin.readline())
queue = deque()
for i in range(N):
queue.append(N - i)
while len(queue) > 1:
queue.pop()
queue.appendleft(queue.pop())
print(queue.popleft())- 코드라인 8
queue.append(N - 1)을 통해 카드가 높을 수록 위에, 낮을수록 아래에 배치했다. - 예를 들어 n = 5 라면
5 <- 맨 위(전단)
4
3
2
1 <- 맨 아래(후단)의 상태이다.- 코드라인 11
queue.pop()에서 원래라면 1이 맨 위에 있어 전단을 삭제해야 했지만 순서를 바꿨으므로 후단에 있는 1을 삭제 한다. 이때queue.popleft()를 사용하고 시간복잡도는 O(1)이다. - 마찬가지로 코드라인 12
queue.appendleft(queue.pop())도 후단에 있는 값을 추가했다. 이때 전단에 데이터를 넣기 위해queue.appendleft(i + 1을 이용했다.
- queue.popleft() -> 디큐의 전단을 삭제한다.
- queue.pop() -> 디큐의 후단을 삭제한다.
- queue.append(데이터) -> 디큐에 후단에 데이터를 삽입한다.
- queue.appendleft(데이터) -> 디큐에 전단에 데이터를 삽입한다.큐를 사용하는 예제 3 - 뱀
[문제]
'Dummy'라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기 자신의 몸과 부딪히면 게임이 끝난다.게임은 N * N 정사각 보드 위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할 때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1이다. 뱀은 처음에 오른쪽을 향한다.
뱀은 매 초마다 이동을 하는 데 다음과 같은 규칙을 따른다.
- 먼저 뱀은 몸길이를 늘려 머리를 다음 칸에 위치시킨다. - 만약 이동한 칸에 사과가 있따면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다. - 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다, 즉, 몸길이는 변하지 않는다.사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.
[입력]
첫째 줄에 보드의 크기 N이 주어진다.(2 <= N <= 100) 다음 줄에 사과의 개수 K가 주어진다.
(0 <= K <= 100)다음 K개의 줄에는 사과의 위치가 주어지는데, 첫 번째 정수는 행, 두 번째 정수는 열 위치를 의미한다. 사과의 위치는 모두 다르며 ,맨 위 맨 좌측(1행 1열)에는 사과가 없다.
다음 줄에는 뱀의 방향 변환 횟수 L이 주어진다.(1 <= L <= 100)
다음 L개의 줄에는 뱀의 방향 변환 정보가 주어지는데, 정수 X와 문자 C로 이루어져 있으며, 게임 시작 시간으로부터 X초가 끝난 뒤에 왼쪽(C가 'L') 또는 오른쪽(C가 'D'(으로 90도 방향을 회전시킨다는 뜻이다. X는 10,000 이하의 양의 정수이며, 방향 전환 정보는 X가 증가하는 순으로 주어진다.
[출력]
첫째 줄에 게임이 몇 초에 끝나는지 출력한다.
예제 입력 1 예제 출력 1 예제 입력 2 예제 출력 2 예제 입력 3 예제 출력 3 6 9 10 21 10 13 3 4 5 3 4 1 2 1 5 2 5 1 3 1 3 5 3 1 4 1 2 3 1 5 1 6 3 D 4 1 7 15 L 8 D 4 17 D 10 D 8 D 11 D 10 D 13 L 11 D 13 L [문제출처] https://www.acmicpc.net/3190
문제설명
- 뱀이 이동하는 규칙은 아래와 같다.
1. 뱀은 처음에 맨 위, 맨 좌측에 위치하고 길이는 1이다. 뱀의 처음 이동방향은 오른쪽이다.
2. 먼저 뱀은 몸길이를 늘려 머리를 다음 칸에 위치시킨다.
3. 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
4. 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.
뱀이 이리저리 기어다니다가 벽 또는 자기 자신의 몸과 부딪히면 게임이 끝난다.해답코드
from collections import deque
def direction_change(d, c):
if c == 'L':
d = (d - 1) % 4
else:
d = (d + 1) % 4
return d
N = int(input())
K = int(input())
board = [[0] * N for _ in range(N)]
for _ in range(K):
a, b = map(int, input().split())
board[a - 1][b - 1] = 1
L = int(input())
times = {}
for i in range(L):
X, C = input().split()
times[int(X)] = C
dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]
direction = 1
time = 1
y, x = 0, 0
snake = deque([[y, x]])
board[y][x] = 2
while True:
y, x = y + dy[direction], x + dx[direction]
if 0 <= y < N and 0 <= x < N and board[y][x] != 2:
if not board[y][x] == 1:
delY, delX = snake.popleft()
board[delY][delX] = 0
board[y][x] = 2
snake.append([y, x])
if time in times.keys():
direction = direction_change(direction, times[times])
time += 1
else:
break
print(time)- 코드가 꽤 길기 때문에, 구간으로 나누어 해석해보자.
N = int(input())
K = int(input())
board = [[0] * N for _ in range(N)] # n과 k를 입력하고 board를 초기화해 둔 상태이다.
for _ in range(K): # 사과의 위치를 입력받고 사과가 있는곳은 board[a-1][b-1]=1처럼 board의 값을 1로 설정
a, b = map(int, input().split())
board[a - 1][b - 1] = 1
L = int(input())
times = {}
for i in range(L):
X, C = input().split()
times[int(X)] = C # L을 입력받고, 게임시작 시간 이후 방향을 바꿔야 하는 정보를 입력받는다.dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]
# 상, 하, 좌, 우를 나타내기 위한 방법이다.
# y=y+dy[0], x=x+dx[0] : y는 1 감소하고 x는 그대로이다. 위쪽으로 이동을 나타낸다.
# y=y+dy[1], x=x+dx[1] : y는 그대로이고 x는 1 증가한다. 오른쪽으로 이동을 나타낸다.
# y=y+dy[2], x=x+dx[2] : y는 1 증가하고 x는 그대로이다. 아래쪽으로 이동을 나타낸다.
# y=y+dy[3], x=x+dx[3] : y는 그대로이고 x는 1 감소한다. 왼쪽으로 이동을 나타낸다.
direction = 1 # 뱀의 현재 이동 방향이다. 오른쪽을 나타내기 위한 변수를 생성한다.
time = 1 # 게임이 진행된 시간을 저장하기 위한 변수를 생성한다.
y, x = 0, 0 # 뱀 머리의 현재 위치 저장을 위한 변수를 생성한다.
snake = deque([[y, x]])
# 뱀의 꼬리 위치를 큐의 형식으로 저장하기 위해 큐를 사용한다.
# 이동한 칸에 사과가 없다면 뱀의 마지막 부분인 꼬리를 제거해 두어야 한다.
# 이를 위해 큐를 이용한다면 가장 먼저 삽입된 끝 부분을 지우기 쉽다는 점이 있다.
board[y][x] = 2 # 뱀이 존재하는 곳은 board값을 2로 설정해두었다.def direction_change(d, c):
if c == 'L':
d = (d - 1) % 4 # 뱀의 방향을 왼쪽으로 회전한다.
else:
d = (d + 1) % 4 # 뱀의 방향을 오른쪽으로 회전한다.
return d- 위 함수에 대해서 추가적을 설명하자면
- direction값에 따라 이동하는 방향은 아래와 같다.
direction = 0 -> 위쪽
direction = 1 -> 오른쪽
direction = 2 -> 아래쪽
direction = 3 -> 왼쪽- 만약 direction이 0(위쪽)이고 뱀의 방향을 'L' 왼쪽으로 회전한다면 direction은 3(왼쪽)이 되어야 한다.
이를 위해 d가 0일 때,d = (d -1 ) % 4 = -1 % 4 = 33(왼쪽) 값을 얻게 해두었다.
while True:
y, x = y + dy[direction], x + dx[direction]
if 0 <= y < N and 0 <= x < N and board[y][x] != 2:
if not board[y][x] == 1:
delY, delX = snake.popleft()
board[delY][delX] = 0
board[y][x] = 2
snake.append([y, x])
if time in times.keys():
direction = direction_change(direction, times[times])
time += 1
else:
break
print(time)- 해답 코드의 핵심 알고리즘이다.
- 뱀이 이동하는 규칙을 다시 상기해보면
1) 먼저 뱀은 몸길이를 늘려 머리를 다음 칸에 위치시킨다.
2) 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
3) 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다, 즉, 몸길이는 변하지 않는다.
4) 뱀이 이리저리 기어 다니다가 벽 또는 자기 자신의 몸과 부딪히면 게임이 끝난다. y, x = y + dy[direction], x + dx[direction] # 1)을 위해 머리를 다음 칸에 위치시킨다.
if 0 <= y < N and 0 <= x < N and board[y][x] != 2:
# 4) 에 의해 벽 또는 자기 자신의 몸과 부딪히는지 확인한다.- board값이 2라면 자기 자신과 부딪히는 것이고, 범위를 초과하면 벽과 부딪히는 것이다.
- 벽 또는 자기 자신의 몸과 부딪히지 않는다면
if not board[y][x] == 1:
delY, delX = snake.popleft()
board[delY][delX] = 0
# 3)의 이동한 칸에 사과가 없다면 꼬리가 위치한 칸을 비워주어야 한다.
# 이를 위해 board에 큐의 전단 위치를 0으로 바꿔준다.
board[y][x] = 2
snake.append([y, x])
# 머리 위치는 board값을 2로 바꾸어 뱀이 존재하는 것을 나타낸다. 그 후 머리 위치도 큐에 넣는다.
if time in times.keys():
direction = direction_change(direction, times[times])
# 방향을 전환해야 한다면 코드라인 3~8에서 만든 함수를 통해 바꾼다.
time += 1
else:
break # 벽 또는 자기 자신의 몸과 부딪힌다면 while문에서 벗어난다.
print(time) # 정답을 출력한다.
데이터 사이언스 입문