스택·큐로 문제 해결

본문

본문

교무실 프린터에 문서가 평소 한 시간에 40개쯤 들어온다. 프린터는 한 시간에 50개를 출력할 수 있다. 이때 대기열에는 평균 4개쯤의 문서가 쌓여 있다. 그런데 시험 기간에 문서가 한 시간에 45개로, 고작 12% 늘었는데 대기열은 9개로 두 배 넘게 길어졌다. 왜 조금 바빠졌을 뿐인데 줄이 이렇게 크게 늘어날까? 그리고 큐와 스택 같은 자료 구조로 이런 문제를 어떻게 다룰까?

이용률 ρ (도착 ÷ 처리)

그림 1. 문서가 무작위로 도착하고 출력 시간도 무작위인 대기열(M/M/1 모형)에서, 이용률에 따른 대기열 속 평균 문서 수. 이용률이 1에 다가가면 줄이 끝없이 길어진다.

먼저 알아야 할 것스택과 큐(스택과 큐의 구현), 확률과 평균(수학).

2.2.1큐로 대기열 흉내 내기

인쇄 대기열은 먼저 들어온 문서를 먼저 출력하는 큐이다. 프로그램으로 흉내 내려면 시간을 조금씩 흘려 보내며, 문서가 도착하면 큐에 넣고, 프린터가 비면 큐 앞에서 문서를 꺼내 출력한다. 도착 간격과 출력 시간을 무작위로 정하면 실제 대기열과 비슷한 모습이 나온다. 이런 시뮬레이션으로 줄이 얼마나 길어지는지, 문서 하나가 얼마나 기다리는지 잴 수 있다. 중요한 문서를 먼저 출력해야 한다면, 우선순위가 높은 것부터 꺼내는 우선순위 큐를 쓴다.

정리 2.2.1 대기열의 평균 길이

문서가 평균 도착률 \(\lambda\)로 무작위로 오고, 프린터가 평균 처리율 \(\mu\)로 무작위 시간에 출력하면, 이용률 \(\rho = \lambda/\mu\)에서 시스템 안의 평균 문서 수는 \[L = \frac{\rho}{1 - \rho}\]이다. 문서 하나가 시스템에 머무는 평균 시간은 출력 시간의 \(\dfrac{1}{1 - \rho}\)배이다.

그림 1에서 이용률을 바꾸어 보자. 이용률 0.8이면 평균 4개, 0.9이면 9개, 0.95이면 19개가 쌓인다. 0.8에서 0.9로 12% 바빠졌을 뿐인데 줄은 두 배 넘게 길어진다. 도착과 출력이 무작위라서, 잠깐 문서가 몰리면 프린터가 따라잡을 여유가 거의 없기 때문이다. 그래서 대기열을 설계할 때는 처리 능력을 도착률보다 넉넉하게, 이용률이 0.7~0.8을 넘지 않게 잡는다.¹

2.2.2스택으로 괄호 검사하기

스택은 짝을 맞추는 문제에 알맞다. 수식이나 코드의 괄호가 바르게 닫혔는지 검사하려면 문자를 왼쪽부터 읽으며, 여는 괄호를 만나면 스택에 넣고, 닫는 괄호를 만나면 스택 맨 위의 여는 괄호를 꺼내 짝이 맞는지 확인한다. 짝이 다르거나 스택이 비어 있으면 틀린 식이고, 끝까지 읽은 뒤 스택이 비어야 바른 식이다. 가장 나중에 연 괄호가 가장 먼저 닫혀야 한다는 규칙이 바로 스택의 후입 선출이다. 웹 브라우저의 뒤로 가기, 편집기의 실행 취소도 같은 원리이다.

그림 2. 무엇을 먼저 꺼내야 하는지가 알맞은 자료 구조를 정한다.

2.2.3예제 풀이

예제 2.2.2

프린터가 한 시간에 문서 50개를 출력한다. 문서가 한 시간에 40개 올 때와 45개 올 때, 대기열 속 평균 문서 수와 문서 하나가 시스템에 머무는 평균 시간을 구하여라. 문서 하나의 평균 출력 시간은 1.2분이다.

40개이면 \(\rho = 0.8\)이므로 평균 \(0.8 \div 0.2 = 4\)개가 있고, 문서 하나는 출력 시간의 \(1 \div 0.2 = 5\)배인 6분을 머문다.

45개이면 \(\rho = 0.9\)이므로 평균 \(0.9 \div 0.1 = 9\)개가 있고, 문서 하나는 출력 시간의 10배인 12분을 머문다. 문서가 12.5% 늘었는데 기다리는 시간은 두 배가 되었다. 프린터를 한 대 더 두어 처리율을 두 배로 하면 이용률이 0.45가 되어, 문서가 평균 0.8개만 쌓인다. 즉 대기열은 이용률이 1에 가까울수록 아주 민감해진다. 그래서 시뮬레이션과 계산으로 이용률을 어림하면, 프린터를 언제 늘려야 할지 미리 판단할 수 있다.

아래 탐구 카드에서 괄호 검사기와 우선순위가 있는 인쇄 대기열을 스택과 큐로 직접 만들어 보자.

이 공식은 1909년 덴마크의 엔지니어 얼랑이 전화 교환기에 걸려 오는 통화를 분석하며 시작한 대기 이론에서 나왔다. 지금은 서버, 은행 창구, 고속도로 요금소의 설계에 두루 쓰인다.

마무리

큐는 먼저 온 것을 먼저 처리하는 대기열을, 스택은 나중에 연 것을 먼저 닫는 짝 맞추기를 자연스럽게 나타내며, 큐로 대기열을 시뮬레이션하면 줄의 길이와 기다리는 시간을 잴 수 있다. 무작위로 도착하고 처리되는 대기열의 평균 길이는 \(\rho/(1-\rho)\)로, 이용률이 1에 가까워질수록 폭발적으로 늘어난다. 그래서 처음 질문의 프린터는 이용률이 0.8에서 0.9로 올라가 여유가 거의 사라지면서, 대기 줄이 두 배 넘게 길어졌다.

탐구 1

괄호의 짝과 수식의 값을 스택 하나로 어떻게 판단할까?

스택 활용 · 괄호 짝 검사 · 후위 표기식 계산

입력 (직접 고쳐 써도 됩니다)

후위 표기식은 수와 연산자를 빈칸으로 띄어 쓴다(정수와 + − * /). 괄호 검사는 ( ) [ ] { }만 보고 나머지 글자는 건너뛴다.

질문코드 편집기는 괄호 짝이 틀리면 곧바로 표시한다. 여는 괄호와 닫는 괄호의 개수만 세면 될까? ([)]는 개수가 맞는데도 틀린 식이다. 또 계산기는 (3 + 4) * 2에서 무엇을 먼저 계산할지 어떻게 정할까?
복원스택은 맨 위에서만 넣고 꺼내는 후입선출 구조이다. 보통 쓰는 수식(중위 표기)은 연산자가 두 수 사이에 있고, 곱셈이 덧셈보다 먼저라는 우선순위와 괄호로 계산 순서를 정한다.
설명괄호는 가장 나중에 열린 것이 가장 먼저 닫혀야 한다. 이 성질이 바로 후입선출이므로, 여는 괄호는 스택에 넣고 닫는 괄호를 만나면 맨 위를 꺼내 종류가 맞는지 본다. 중간에 짝이 틀리거나 스택이 비어 있으면 실패, 끝까지 읽은 뒤 스택이 비어야 성공이다. 후위 표기식은 연산자를 두 수 뒤에 쓴다. (3 + 4) * 2는 3 4 + 2 *가 된다. 수는 스택에 넣고, 연산자를 만나면 두 수를 꺼내 계산한 결과를 다시 넣는다. 괄호도 우선순위도 필요 없고, 왼쪽에서 오른쪽으로 한 번만 읽으면 된다.
연결두 알고리즘 모두 입력을 한 번씩만 읽으므로 걸리는 시간이 입력 길이에 비례한다. 계산기와 컴파일러는 중위식을 먼저 후위식으로 바꾼 뒤 이 방법으로 계산하는데, 이 변환에도 연산자를 잠시 쌓아 두는 스택이 쓰인다. HTML 태그의 짝, 함수 호출과 반환처럼 ‘안에 같은 구조가 들어 있는’ 것을 다룰 때 스택이 쓰인다.
적용([)]는 몇 번째 글자에서 실패하는가? ((a+b)*c는 언제 실패가 드러나는가? 후위식 8 2 / 3 -에서 연산자를 만날 때 먼저 꺼낸 수가 왼쪽인지 오른쪽인지 확인해 보자. 2 3 4 * +를 중위식으로 바꾸어 쓰고, 직접 만든 후위식으로 시험해 보자.
판단괄호가 한 종류뿐이면 개수를 세는 변수 하나로도 검사할 수 있다(중간에 음수가 되지 않고 끝에 0이면 성공). 여러 종류가 섞이면 어떤 괄호가 열려 있는지 순서까지 기억해야 하므로 스택이 필요하다. 또 이 함수는 print(')')처럼 문자열 안에 든 괄호까지 세어 틀렸다고 판정한다. 실제 편집기는 문자열과 주석을 먼저 구분한다. 후위식 코드도 마지막에 스택에 값이 정확히 하나 남았는지 확인해야 잘못된 식을 걸러 낼 수 있다.

확인조건이 달라지면

후위 표기식 6 2 - 3 *의 값은?

탐구 2

중요한 문서가 끼어드는 인쇄 대기열에서 내 문서는 몇 번째로 나올까?

큐 활용 · 시뮬레이션 · 큐 회전

문서 중요도 (1~9, 빈칸으로 구분, 최대 10개)

찾을 문서

popleft 횟수: 0
중요도 비교 횟수: 0
찾는 문서의 인쇄 순서: —

질문공용 프린터에 문서 여러 개가 줄 서 있다. 프린터는 맨 앞 문서를 꺼냈을 때 뒤에 더 중요한 문서가 있으면 인쇄하지 않고 줄 맨 뒤로 보낸다. 내 문서는 몇 번째로 인쇄될까?
복원큐는 앞에서 꺼내고 뒤에 넣는 선입선출 구조이다. 파이썬에서는 deque의 popleft()와 append()로 쓴다.
설명규칙을 그대로 따라 상태를 한 단계씩 바꾸며 결과를 알아내는 방법을 시뮬레이션이라 한다. 이 문제에서 필요한 연산은 두 가지뿐이다. 맨 앞을 꺼내고(popleft), 조건이 맞지 않으면 다시 맨 뒤에 넣는다(append). 꺼내서 뒤로 보내는 것을 되풀이하면 줄이 고리처럼 돌아가는데, 이것을 큐 회전이라 한다. 각 문서에 처음 위치 번호를 함께 담아 두어야 같은 중요도의 문서를 구별할 수 있다.
연결운영체제는 여러 프로그램에 처리 시간을 조금씩 나눠 주고, 다 끝나지 않은 프로그램을 대기열 맨 뒤로 보내는 방식(라운드 로빈)을 쓴다. 이것도 큐 회전이다. 순서를 지키며 기다리는 상황은 대부분 큐로 옮길 수 있다.
적용첫 예시에서 A는 몇 번째로 인쇄되는가? 찾을 문서를 바꾸어 예상한 뒤 실행해 확인해 보자. 중요도를 모두 같게 하면 어떤 순서가 되는가? ‘10개’ 예시의 비교 횟수를 6개 예시와 비교해 보자.
판단이 코드는 문서를 꺼낼 때마다 any()로 남은 문서를 훑는다. 문서가 n개면 꺼내기와 비교가 n²에 비례할 만큼 늘어날 수 있다. 문서가 많다면 중요도별 남은 개수를 세어 두거나 우선순위 큐(heapq)를 쓴다. 다만 우선순위 큐에서 같은 중요도의 문서가 들어온 순서를 지키려면 (−중요도, 들어온 번호)처럼 순번을 함께 저장해야 한다. 이 카드의 결과도 회전 규칙 때문에 단순히 “중요도 순, 같으면 들어온 순”과 다를 수 있다.

확인조건이 달라지면

중요도가 차례로 2 1 3 2인 문서 A, B, C, D가 있다. 같은 규칙에서 D는 몇 번째로 인쇄될까?