2주차 퀴즈의 주제는 Heap Sort와 Stack이었다.
1. Heap Sort로 정렬하기
💡 1 2 4 4 3 5 5 6의 입력이 heap_srot.py의 알고리즘에 주어질 때의 상태 그리기
heap_sort.py
# 힙 정렬 알고리즘 구현하기
from typing import MutableSequence
def heap_sort(a: MutableSequence) -> None:
"""힙 정렬"""
def down_heap(a: MutableSequence, left: int, right: int) -> None:
"""a[left] ~ a[right]를 힙으로 만들기"""
temp = a[left] # 루트 노드
parent = left
while parent < (right + 1) // 2:
cl = parent * 2 + 1 # 왼쪽 자식
cr = cl + 1 # 오른쪽 자식
child = cr if cr <= right and a[cr] > a[cl] else cl # 왼/오른 자식 중 큰 값을 선택한다.
if temp >= a[child]:
break
a[parent] = a[child]
parent = child
a[parent] = temp
n = len(a)
for i in range((n-1)//2, -1, -1): # step 1. 배열을 힙으로 만든다.
down_heap(a, i, n-1)
for i in range(n-1, 0, -1): # step 2. 힙 정렬을 수행한다.
a[0], a[i] = a[i], a[0]
down_heap(a, 0, i - 1)
if __name__ == '__main__':
print("힙 정렬을 수행합니다.")
num = int(input("원소 수를 입력하세요: "))
x = [None] * num
for i in range(num):
x[i] = int(input(f'x[{i}]: '))
heap_sort(x)
print("힙 정렬(오름차순) 결과입니다.")
for i in range(num):
print(f"x[{i}] = [{x[i]}]")힙 정렬의 전제 조건은 배열이 힙의 형태를 가지고 있어야 한다는 것이다.
따라서, 우선 step 1. 배열(리스트)를 힙으로 바꾼다!
힙으로 바뀐 결과는 다음과 같다.
최대 힙의 형태로 바뀐 리스트(힙)를 가지고 다음 단계로 이동한다.
step 2. 힙 정렬하기 (오름차순) 
2) 3) 리스트 a 원소들의 순서를 깜빡하고 반영하지 못했다. (귀찮아서 그런 건 절대 아니다.)
정정하자면,
2) a[5, 4, 4, 2, 3, 1, 5, 6] 3) [4, 4, 1, 2, 3, 5, 5, 6 ]이다.
앞선 두 단계에 거쳐 힙 정렬을 마친 결과는 아래와 같다.
2. 계산기 만들기 (Stack 활용)
💡 calculator.py의 함수를 적용할 때 1 + (1 + 7)/(2 * 2)의 계산 과정 도식화 하기
※ 단, 두자리 수 이상의 피연산자와 unary 연산자는 고려하지 않는다.
1) postfix(후위 표기식)으로 변환할 때 쓰는 convert_to_postfix 함수의answer와opstack의 상태
2) 후위 표기식에서 최종 결과를 계산할 때 쓰는 calculate 함수의stack의 상태
calculator.py
# 스택을 활용해 계산기 만들기
import sys
prec = {
'*': 3, '/': 3,
'+': 2, '-': 2,
'(': 1
}
def join_array(ints):
str_list = list(map(str, ints))
return "".join(str_list)
class ArrayStack:
def __init__(self):
self.data = []
def size(self):
return len(self.data)
def isEmpty(self):
return self.size() == 0
def push(self, item):
self.data.append(item)
def pop(self):
return self.data.pop()
def peek(self):
return self.data[-1]
def serialize(self):
return join_array(self.data)
def convert_to_postfix(S):
opStack = ArrayStack()
answer = ""
for w in S:
if w in prec:
if opStack.isEmpty():
opStack.push(w)
else:
if w == '(':
opStack.push(w)
else:
while prec.get(w) <= prec.get(opStack.peek()):
answer += opStack.pop()
if opStack.isEmpty():
break
opStack.push(w)
elif w == ')':
while opStack.peek() != '(':
answer += opStack.pop()
opStack.pop()
else:
answer += w
while not opStack.isEmpty():
answer += opStack.pop()
return answer
def caculate(tokens):
stack = ArrayStack()
for token in tokens:
if token == '+':
stack.push(stack.pop() + stack.pop())
elif token == '-':
stack.push(-stack.pop() + stack.pop())
elif token == '*':
stack.push(stack.pop() * stack.pop())
elif token == '/':
rv = stack.pop()
stack.push(stack.pop() // rv)
else:
stack.push(int(token))
return stack.pop()
# infix 수식에서 공백 제거
infix = sys.stdin.readline().replace("\n", "").replace(" ", "")
postfix = convert_to_postfix(infix)
print(f"postfix: {postfix}")
result = caculate(postfix)
print(f"result: {result}")수식을 표현하는 방법에는 infix / prefix / postfix 세 가지가 있다.
더 많이 사용하는 postfix를 사용해 스택 계산기의 동작 원리를 도식화 해 보았다.
제시된 수식을 postfix(후위표기법)으로 먼저 고치면 위와 같이 나와야 한다.
(스택으로 계산 과정을 진행하기 위해서는, infix를 postfix로 바꿔주어야 훨씬 수월하다.)
이제, 앞선 calcuator.py에 입력값이 주어진 경우, 어떻게 postfix로 전환하고, 계산하고, 정확한 결과값을 반환하는지 아래 도식을 통해 설명하겠다.
step 1. convert_to_postfix(S)
