[야근 지수] - 최대힙 이용

어제 최대힙을 잠깐 공부했었는데, 오늘 공부를 하다가 또 최대힙을 발견하여 최대힙을 다시 정리하면서 넘어가고자 한다.

 

우선, 문제를 보자.

 

문제를 보면, 작업량과 남은 시간을 가지고 최소한의 야근 피로도를 계산하는 문제이다. 여기서 야근 피로도는 남은 작업 시간들의 제곱으로 구해지기 때문에, 남은 시간 n 동안 가능한 한 큰 작업을 최대한 줄여서 피로도를 최소화하는 게 목표이다.

 

예를 들어, 주어진 작업량이 [4, 3, 3]이고 남은 시간이 4라고 하면 이 경우, 가장 큰 값인 4를 먼저 줄이는 게 효율적이다. 그래서 4를 1만큼 줄이면 남은 시간은 3이 되고, 배열은 [3, 3, 3]이 된다. 이후에도 계속 최댓값을 찾아서 1씩 줄여주는 과정을 반복한다. 예를 들어, 3을 또 줄이면 배열은 [3, 3, 2]가 되고 남은 시간은 2가 되는 식으로 진행한다.

 

여기서 문제가 발생하는데:

 

1. 매 반복마다 최댓값을 찾아야 하는데, max() 함수를 반복적으로 호출하면 성능이 떨어진다.

2. max()를 피하기 위해 정렬된 배열을 사용하려고 해도, 매번 배열을 다시 정렬해야 해서 이 방법도 비효율적이다.

 

따라서 최댓값을 빠르게 찾아내면서도 효율적으로 값을 줄일 수 있는 방법을 고려해야 해.

 

이때, 최대, 또는 최소값을 빠르게 찾아내면서 계속 트래킹 할 수 있는 자료구조는 파이썬의 heap 이 있다.

 

힙(Heap)은 완전 이진 트리(Complete Binary Tree) 구조를 가지는 특수한 트리 기반의 자료구조로, 최댓값 또는 최솟값을 빠르게 찾아내기 위한 구조다. 힙은 크게 최소 힙과 최대 힙으로 나뉘며, 각각 특정 조건을 만족하는 이진 트리 형태로 값을 저장한다.

 

1. 최소 힙(Min Heap):

• 부모 노드가 자식 노드보다 작거나 같은 값을 가진다.

• 즉, 루트(root) 노드는 항상 힙에서 가장 작은 값이다.

• 이를 통해 매번 가장 작은 값을 빠르게 꺼낼 수 있다.

• 예를 들어, [1, 3, 5, 7, 9]가 최소 힙으로 구성되어 있다면, 1이 최솟값으로 가장 위에 자리잡는다.

2. 최대 힙(Max Heap):

• 부모 노드가 자식 노드보다 크거나 같은 값을 가진다.

• 즉, 루트 노드는 항상 힙에서 가장 큰 값이다.

• 이를 통해 매번 가장 큰 값을 빠르게 꺼낼 수 있다.

• 예를 들어, [9, 7, 5, 3, 1]이 최대 힙으로 구성되어 있다면, 9가 최댓값으로 가장 위에 자리잡는다.

 

힙의 핵심 특징:

 

• 시간 복잡도: 삽입(insert)과 삭제(remove)는 O(log N)의 시간 복잡도를 가진다. 이는 트리의 높이에 해당하는 연산이기 때문이다. 힙은 트리가 완전히 채워지므로, 트리의 높이는 log N에 비례한다.

• 실시간 트래킹: 반복적으로 최댓값 또는 최솟값을 요구하는 문제에서 매우 유용하다. 힙은 트리 구조를 유지하며 값을 삽입하거나 삭제하므로 매번 정렬할 필요 없이 효율적으로 최댓값이나 최솟값을 찾을 수 있다.

 

파이썬에서의 힙 구현:

 

• 파이썬의 heapq 모듈은 기본적으로 최소 힙을 제공한다. 즉, 이 모듈을 사용하면 항상 최솟값을 빠르게 찾을 수 있다.

• 최대 힙은 별도로 제공되지 않으나, 음수 변환을 통해 간단히 구현할 수 있다. 값을 삽입할 때 음수로 변환하고, 값을 꺼낼 때 다시 양수로 변환하여 최대 힙처럼 동작하게 할 수 있다.

 

heapq 모듈 주요 함수:

1. heapq.heappush(heap, item): item을 힙에 추가한다.

2. heapq.heappop(heap): 힙에서 최솟값을 꺼낸다.

3. heapq.heapify(list): 주어진 리스트를 힙 구조로 변환한다.

 

최대 힙 예시 (파이썬에서 음수 변환을 통해 구현):

import heapq

# 최대 힙을 구현하기 위해 값의 부호를 반전

max_heap = []

heapq.heappush(max_heap, -10)  # 10을 최대 힙에 추가 (음수로)

heapq.heappush(max_heap, -30)  # 30을 최대 힙에 추가 (음수로)

heapq.heappush(max_heap, -20)  # 20을 최대 힙에 추가 (음수로)

# 최대값 꺼내기

print(-heapq.heappop(max_heap))  # 출력: 30 (음수로 저장했기 때문에 다시 양수로 바꿈)

 

힙의 용도:

• 우선순위 큐 구현: 항상 우선순위가 높은 작업을 먼저 처리해야 하는 경우.

• 정렬이 필요 없는 트래킹: 최댓값이나 최솟값을 자주 구하는 문제에서 매우 효율적.

• 작업 스케줄링: 작업 시간을 기준으로 우선순위를 정해 빠르게 처리를 해야 하는 스케줄링 문제에서 사용.

 

힙은 정렬이 반복적으로 필요할 때 매우 효율적이며, 특히 우선순위가 중요한 문제에서 자주 사용되는 자료구조이다.

 

그러면, 이 문제에 힙을 구현해 보자. 이 문제는, 최솟값이 아니라 최댓값을 실시간으로 트래킹 해야 하므로 최대힙을 사용해야 한다.

import heapq

def solution(n, works):
    res = 0
    works = [-x for x in works]
    heapq.heapify(works)
    
    while n > 0 and works[0] < 0:
        max_val = -heapq.heappop(works)
        max_val -= 1
        n -= 1
        heapq.heappush(works, -max_val)
    
    for i in works:
        res += pow(i, 2)
    return res

 

우선, import heapq를 사용해 힙을 가져온다.

 

그리고 최대힙을 구현하기 위해 주어진 works 배열의 각 요소를 음수로 변환한다. 이는 파이썬의 기본 힙이 최소 힙이기 때문에, 음수로 변환하여 최소 힙을 최대 힙처럼 사용할 수 있기 때문이다. 이후, heapq.heapify(works)를 사용해 음수로 변환한 works 배열을 힙 자료구조로 변환한다.

 

이제, while문에서:

 

먼저, heapq.heappop(works)를 사용해 works 힙에서 최댓값을 꺼낸다. 음수로 변환했기 때문에 음수 중 가장 작은 값이 나오지만, 우리는 이를 다시 양수로 바꿔 원래의 최댓값을 구한다.

 

다음으로, 꺼낸 최댓값을 1 감소시키고, 이를 다시 힙에 넣어야 한다. 이때, 다시 음수로 변환하여 넣어야 최대힙을 유지할 수 있으므로, heapq.heappush(works, -max_val)을 사용해 힙에 삽입한다.

 

이 과정을 반복하면, 매 반복마다 최대값이 유지되는 힙 구조를 통해 효율적으로 최댓값을 줄여 나갈 수 있다. 이 방식은 max()나 sort()를 반복해서 호출할 필요 없이 최댓값을 바로 꺼내고 수정한 뒤 다시 넣는 작업을 효율적으로 처리할 수 있다.

 

따라서, 최대값을 계속 유지하면서 실시간으로 값을 조정할 수 있는 장점을 이용하는 것이다.