[파이썬 코테 6기] 2주차 세션 정리

이 글은 프로그래머스에서 진행하는 코딩테스트와 실무 역량 모두 잡는 알고리즘 스터디(Python반) 6기를 참여하면서 일주일에 한 번(매주 수요일) 진행되는 세션에서 배운 내용을 정리하는 글이다.

오늘은 2주차 세션(2021년 08월 04일 진행)에서 배운 내용을 정리해보려고 한다.

https://programmers.co.kr/learn/courses/12441

[스터디/6기] 코딩테스트와 실무 역량 모두 잡는 알고리즘 스터디(Python반)

 

 

---

<세션을 통해 배운 점>

1. Heap

이번 주차에는 힙(heap)에 대한 문제를 풀면서 프로그래머스 스쿨에서 읽을거리로 제공하는 자료로 힙에 대해 알 수 있었다.

힙은 기본적으로 이진 트리로 구성된 자료구조로 우선순위가 높은 요소가 먼저 pop되는 특징을 가진다.

이러한 특징을 가지기 위해서 힙에 요소가 push될 때 우선순위에 맞춰 바로 정렬되어 push된다.

힙은 크게 힙에 있는 요소 중 가장 큰 값이 루트가 되는 max heap과 가장 작은 값이 루트가 되는 min heap이 있다.

 

 

 

 

1. _heapify_max

오늘 세션 중 가장 신기했던 함수 중 하나이다.

heapq모듈을 import하면 사용할 수 있는 함수인데 heapq모듈 공식문서에는 나와있지 않은 함수이다.

원래 heapq.heapify()를 사용하면 min heap으로 구현되는 것은 알고 있을 것이다.

그래서 max heap으로 구현하기 위해서는 요소를 (우선순위, 요소값)형식으로 push했어야 했다.

[heapq모듈에 대해 정리한 나의 글] https://straw961030.tistory.com/170

 

그리고 위 링크의 블로그 글을 쓸 때까지만해도 max heap을 구현하기 위해서는 (우선순위, 요소값)으로 push해야하는 방법만 있는 줄 알았다.

하지만, _heapify_max를 사용하면 자동으로 max heap으로 만들어준다.

직접 코드를 구현하여 실행시켜서 결과를 확인해보자.

import heapq

# heapify()를 사용한 경우
arr1 = [5, 4, 1, 2, 8, 9]
heapq.heapify(arr1)

print(arr1)
# 결과: [1, 2, 5, 4, 8, 9] (min heap으로 구현됨)


# _heapify_max()를 사용한 경우
arr2 = [5, 4, 1, 2, 8, 9]
heapq._heapify_max(arr2)

print(arr2)
# 결과: [9, 8, 5, 2, 4, 1] (max heap으로 구현됨)

결과에서 보여진 것처럼 간단하게 max heap을 구현할 수 있다.

하지만, _heapify_max()로 만든 max heap의 단점은 _heappush_max()가 없어 요소를 push할 때에 max heap으로 정렬되어 들어가지 않는다는 것이다.

_heappush_max() 에러 메시지

_heappop_max()함수는 있어 pop할 때에 최대값을 가져올 수는 있지만 push를 할 수 없어서 max heap에 push까지 해야하는 상황이라면 아쉽지만 _heapify_max()는 사용할 수 없다.

max heap에 push를 하고자한다면 heapify()으로 힙을 만들고 (우선순위, 키값)으로 요소를 push하여 max heap을 만들고 heappush((우선순위, 키값))으로 push를 해야한다.

 

---

<2주차 세션 회고>

2주차 세션은 정글에서 할 일이 많아 라이브로는 참여를 못하고 목요일에 쉴 수 있는 시간이 있어 그 때 녹화본을 보았다.

이번 주차는 큐와 힙에 대한 문제를 푸는 주였다.

큐는 어느 정도 알고 있는 상태였기에 어렵지 않게 풀었지만 힙에 대한 개념이 잡혀있지 않았다.

프로그래머스 스쿨에서 읽을거리로 제공하는 힙 내용을 읽고 코드를 실습해보며 힙에 대해 알고 다른 힙 문제를 풀어보며 어떻게 적용할 수 있을지 알아본 후에 과제를 풀기 시작했다.

파이썬에서 제공하는 heapq모듈이 잘 되어있어 편하게 힙을 쓸 수 있었고 세션을 통해 max힙을 간단한 함수를 통해 구현할 수 있다는 것을 알 수 있는 좋은 기회였다.

 

그리고 중간에 파라메트릭 서치로 문제를 풀고 파라메트릭 서치가 무엇인지 알려주셨는데 이 부분은 조금 더 개인적으로 공부를 해봐야할 것같다.

이번 주차도 얻어가는 것이 많았고 다음 주차는 내가 부족한 부분이기에 얼마나 좋은 정보를 얻어갈지 기대된다.