[내일배움캠프 18일차 TIL] 백준 1927번 최소힙

최소힙 문제 모듈 사용 안하고 풀려니까 너무 어렵다.......

라이브러리가 존재함에 다시 한 번 감사하게 된다😂

 

---

어제부터 끙끙 앓으면서 풀던 최소 힙

물론 파이썬은 heapq라는 모듈 통해 힙을 쉽게 구현할 수 있지만

현재 나는 자료구조를 이해하고 어떻게 동작하는지 알아야 하기 때문에 직접 구현해보기로 했다

물론 스쿼드 숙제에서 직접 구현해서 풀어보고 heapq를 사용해서 풀어보라고 했다

 

 

힙은 완전이진트리의 형태를 가지며 부모노드와 자식노드간에 대소관계가 있다.

내가 구현할 최소힙은 부모노드 <= 자식노드를 만족해야 한다

 

내가 만들 힙에는 데이터를 삽입하는 메소드와, 데이터를 추출하는 메소드를 만들어야 한다

기본적인 틀은 다음과 같다

class MyHeap:
	def __init__(self):
    	pass
        
    def insert(self, data):
    	pass
        
    def remove(self):
    	pass

 

 

먼저 힙을 리스트로 구현하기 위해 리스트를 만들어준다

def __init__(self):
	self.arr = [None]

 

리스트의 인덱스를 사용해서 부모노드와 자식노드를 비교하기 위해 첫 번째 요소는 None으로 설정해준다

 

 

insert 메소드 구현

 

힙에서 데이터를 삽입할 때는 다음의 과정을 거친다

1. 힙의 가장 마지막에 데이터 삽입
2. 부모 노드와 비교하여 부모노드가 더 큰 경우 현재 노드와 자리를 바꾸어준다
3. 다시 현재의 위치에서 부모노드가 현재 노드보다 작을 때까지 2번 과정을 반복한다

이것을 코드로 작성해보자

def insert(self, data):
    self.arr.append(data) # 힙의 가장 마지막에 데이터 추가
    now_idx = len(arr)-1 # 현재 위치 : 힙의 가장 마지막
    parent = now_idx//2 # 부모노드 = 현재노드//2
    
    while parent > 0:
    	# 현재 노드의 값이 부모 노드의 값보다 작은 경우
    	if self.arr[parent] > self.arr[now_idx]: 
            # 두 값의 위치를 바꾸어준다
            self.arr[parent],self.arr[now_idx] = self.arr[now_idx],self.arr[parent]
            now_idx = parent # 현재 노드는 부모노드가 되고
            parent = now_idx//2 # 부모 노드도 업데이트 해 준다
        # 만약 현재 노드가 부모노드의 값과 같거나 크다면
       	else: # 반복문 종료
        	return

 

이렇게 데이터를 삽입하고 최소힙에 맞게 정렬을 할 수 있다

 

 

remove 메소드 구현

 

사실 이 메소드를 구현하는데 가장 애를 먹었다...

무한루프가 돌거나 오류가 나서 정말 힘들었다...

머리로는 이해했는데 막상 생각한 내용을 코드로 옮기니 제대로 작동을 하지 않았던 것이다,,,

 

 

힙에서 데이터를 추출할 때는 다음과 같은 과정을 거친다

1. 힙의 첫 번째 요소와 마지막 요소의 자리를 바꾼다
2. 힙의 마지막 요소를 꺼낸다
3. 첫 번째 요소와 자식 요소들을 비교하여 자식요소가 더 크면 둘의 자리를 바꾼다
4. 힙의 조건을 만족할 때까지 3번의 과정을 반복한다

이것을 코드로 작성해보자

 

def remove(self):
    # 첫 번째 요소와 마지막 요소의 자리를 바꾼다
    self.arr[1], self.arr[-1] = self.arr[-1],self.arr[1]
    root = self.arr.pop() # 가장 마지막 요소를 꺼낸다
    
    # 노드를 재정렬한다
    now_idx = 1 # 첫 번째 노드부터 시작
    l = len(self.arr)-1 # 노드의 길이 - 인덱스 비교를 위해 1을 빼줌
    
    while now_idx//2 <= l # 자식 노드가 있을 수 있는 가장 마지막 부모노드?
        left = now_idx*2 # 왼쪽 자식 노드
        right = now_node*2+1 # 오른쪽 자식 노드
        compare_node = now_idx # 비교할 노드
        
        # 자식 노드가 없는 경우 -> 반복문 종료
        if left > l:
            break
        # 왼쪽 자식만 있는 경우
        if left == l:
            compare_node = left # 비교할 자식 노드는 왼쪽노드
        # 자식이 둘 다 있는 경우
        else:
            # 왼쪽 자식이 오른쪽 자식보다 작거나 같은 경우
            if self.arr[left] <= self.arr[right]:
                compare_node = left
            # 오른쪽 자식이 왼쪽 자식보다 작은 경우
            else:
                compare_node = right
                
        # 현재 노드와 자식 노드를 비교
        # 현재 노드가 자식 노드보다 작거나 같으면
        if self.arr[now_idx] <= self.arr[compare_node]:
            break # 반복문 종료
        # 현재 노드가 자식노드보다 크다면
        else:
            # 둘의 자리를 바꾸어 준다
            self.arr[now_idx], self.arr[compare_node] = self.arr[compare_node], self.arr[now_idx]
            now_idx = compare_node # 현재 노드의 인덱스는 비교인덱스(자식 노드)로 업데이트
            
    # 정렬이 끝나면 최상단에 있었던(가장 작은 값을 가진)노드 리턴
    return root

 

 

 

---

힙을 직접 구현한 후에는 파이썬의 heapq 모듈을 사용해서 문제를 풀었다

 

import sys
from heapq import heappush, heappop

my_heap = []

for _ in range(int(input())):
    n = int(sys.stdin.readline())
    if n == 0:
        if len(my_heap) == 0:
            print(0)
        else:
            print(heappop(my_heap))
    else:
        heappush(my_heap, n)

 

다시한번 파이썬이 많은 모듈을 제공하는 것에 감사하게 되는 하루였다... 😮‍💨

 

전체 코드는 여기서!

 

 

---

 

머리로 로직만 이해하는거랑 실제로 구현하는 것에 갭을 느끼고 꽤나 좌절했지만,

그래도 해야지 어쩌겠어...

좌절 할 수 있지만 포기는 하지 말자!!

 

공주같은 마인드로 살기 1일차