힙하지 않은 힙

오늘은 힙과 해시 테이블에 대해 알아보았다.

 

왜 이렇게 진도가 빠른가 하면 나도 잘 모르겠다. 어찌되었든 내일은 더 어려운 것들이 나타날 것이기에..

 

어쨌든 힙이라 함은 다양한 곳에서 마주친 경험이 있는데,

 

이렇게 알고리즘으로 접근한 것은 이번이 처음이라 쉽지는 않았다.

---

 

 

힙이란..정해진 우선순위에 따라 원소를 추가, 삭제가 가능한 자료구조이다. 

정말 고맙게도 파이썬에서는 heapq 라이브러리를 지원하여 힙을 편리하게 사용할 수 있다.

 

최소, 최대 힙 같은 최소, 최대값과 관련하여 힙이 자주 등장하는듯 하다.

 

최소힙에 대한 기본 예제 같은것이 등장해서 한번 겪어볼 수 있었다.

 

import sys
from heapq import *

n = int(input())
nums = list(int(sys.stdin.readline().strip()) for _ in range(n))

heap = []
for i in range(n):
    if nums[i] == 0:
        if heap:
            print(heappop(heap))
        else:
            print(0)
    else:
        heappush(heap, nums[i])

 

뭐 인풋은 백준 특이니 넘어가고.. 다양한 정수들을 집어넣으면서 최소값을 찾아내는 그런 과정이었다.

 

주어진 heapq 라이브러리에 도움이 되는 내용이 많아서 생각보다 쉽게 구현할 수있다.

이러한 기본적인 내용들이 자꾸 응용이 되는 문제를 발견하기도 하니, 잘 알아두어야겠다.

 

백준vs프로그래머스..

 

그것은 참으로 어려운 문제이다..

하지만 프로그래머스도 조금씩 계속 풀어봐야겠다. 같은문제를 새로 작성해보는 것도 방법이겠다. 시간이 남으면 복습 차원으로 진행해봐야지!

 

오늘도 파이팅이었다. 

내일도 파이팅!!?????????