---

Reference

• 10818번 최소, 최대, Baekjoon online judge
• 2460번 지능형 기차 2, Baekjoon online judge
• 1999번 최대최소, Baekjoon online judge

---

1. 최소, 최대

최대 원소(greatest element): 모든 다른 원소들보다 큰 원소, 최대원
-Reference. Greatest element and least element, Wikipedia

최소 원소(least element): 모든 다른 원소들보다 작은 원소, 최소원
-Reference. Greatest element and least element, Wikipedia

1.1. 최소, 최대 알고리즘

최솟값, 최댓값을 구하는 알고리즘을 파이썬으로 구현하면 다음과 같다.

def get_max(nums: list) -> int:
	max: int = nums[0]
    for n in nums[1:]:
    	if n > max:
        	max = n
    return max

def get_min(nums: list) -> int:
	min: int = nums[0]
    for n in nums[1:]:
    	if n < min:
        	min = n
    return min

print(get_max([3, 5, 2, 6, 36, 42]))

>>> 42

print(get_min([3, 5, 2, 6, 36, 42]))

>>> 2

---

1.2. [백준 10818번] 최소, 최대

위의 1.1. 최소, 최대 알고리즘을 활용하여 다음과 같이 파이썬으로 문제를 풀이할 수 있다.

import sys

def get_max(nums: list) -> int:
	max: int = nums[0]
    for n in nums[1:]:
    	if n > max:
        	max = n
    return max

def get_min(nums: list) -> int:
	min: int = nums[0]
    for n in nums[1:]:
    	if n < min:
        	min = n
    return min

N = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))
print(get_min(nums), get_max(nums))

---

1.3. [백준 1999번] 최대최소

위의 1.1. 최소, 최대 알고리즘을 활용하여 다음과 같이 파이썬으로 문제를 풀이할 수 있다.

import sys

def get_max(nums: list) -> int:
	max: int = nums[0]
    for n in nums[1:]:
    	if n > max:
        	max = n
    return max

def get_min(nums: list) -> int:
	min: int = nums[0]
    for n in nums[1:]:
    	if n < min:
        	min = n
    return min

N, B, K = list(map(int, sys.stdin.readline().split()))
nums = []
questions = []

for _ in range(N):
    nums.append(list(map(int, sys.stdin.readline().split())))
for _ in range(K):
    questions.append(list(map(int, sys.stdin.readline().split())))
    
for q1, q2 in questions:
    sub_nums = [y for x in nums[q1 - 1:q1 + B - 1] for y in x[q2 - 1:q2 + B - 1]]
    print(get_max(sub_nums) - get_min(sub_nums))

하지만, 이 방법으로 풀이하면 시간 초과가 뜬다.

이 문제를 해결하기 위해서는 3. 우선순위 큐 알고리즘이 필요하다.

---

3. 우선순위 큐

우선순위 큐(Priority queue): 축약 자료형. 각 원소들은 우선순위를 가짐. 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리됨.
-Reference. Priority queue, Wikipedia

• 큐(Queue): 선입선출(First In First Out, FIFO) 자료구조
• 우선순위 큐(Priority Queue): 우선순위가 높은 데이터가 먼저 나가는 자료구조

3.1. 힙

힙(heap): 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조(tree-based structure). A가 B의 부모노드(parent node)이면, A의 키(key) 값과 B의 키 값 사이에는 대소관계가 성립.
-Reference. Heap (data structure), Wikipedia

• 최대 힙: 부모노드의 키 값 > 자식노드의 키 값
• 최소 힙: 부모노드의 키 값 < 자식노드의 키 값

구현 방법	삽입	삭제
순서 없는 배열	$O(1)$	$O(n)$
순서 없는 linked list	$O(1)$	$O(n)$
정렬된 배열	$O(n)$	$O(2)$
정렬된 linked list	$O(n)$	$O(1)$
heap	$O(log_2n)$	$O(log_2n)$

---

3.2. Python 라이브러리

• heapq: 힙(heap) 큐 알고리즘 구현
  heapq.heapify(list): list를 힙으로 변환
  heapq.heappush(heap, item): item을 heap에 push
  heapq.heapop(heap): heap에서 가장 작은 item을 pop

---

3.3. [백준 2460] 지능형 기차 2

위의 3. 우선순위 큐 알고리즘을 활용하여 다음과 같이 파이썬으로 문제를 풀이할 수 있다.

import sys
import heapq

import sys
import heapq

prev: int = 0
passengers = []
for _ in range(10):
    off, on = list(map(int, sys.stdin.readline().split()))
    prev += (on - off)
    heapq.heappush(passengers, -prev)
print(-heapq.heappop(passengers))

---

3.4. [백준 1999번] 최대최소

위의 3. 우선순위 큐 알고리즘을 활용하여 다음과 같이 파이썬으로 문제를 풀이할 수 있다.

import sys
import heapq

N, B, K = list(map(int, sys.stdin.readline().split()))

max_nums = []
min_nums = []
maxs = []
mins = []
questions = []
for _ in range(N-B+1):
    temp_max = []
    temp_min = []
    for _ in range(N-B+1):
        temp_max.append(0)
        temp_min.append(0)
    maxs.append(temp_max)
    mins.append(temp_min)

for i in range(N):
    row = list(map(int, sys.stdin.readline().split()))
    temp_max = []
    temp_min = []
    for j in range(N-B+1):
        max_heap = []
        min_heap = []
        for k in range(B):
            heapq.heappush(max_heap, -row[j+k])
            heapq.heappush(min_heap, row[j+k])
        temp_max.append(-heapq.heappop(max_heap))
        temp_min.append(heapq.heappop(min_heap))
    max_nums.append(temp_max)
    min_nums.append(temp_min)

for i in range(N-B+1):
    for j in range(N-B+1):
        max_heap = []
        min_heap = []
        for k in range(B):
            heapq.heappush(max_heap, -max_nums[j+k][i])
            heapq.heappush(min_heap, min_nums[j+k][i])
        maxs[j][i] = -heapq.heappop(max_heap)
        mins[j][i] = heapq.heappop(min_heap)

for _ in range(K):
    q1, q2 = list(map(int, sys.stdin.readline().split()))
    print(maxs[q1-1][q2-1] - mins[q1-1][q2-1])