오늘의 강좌에서는 절댓값 힙을 구현하는 방법에 대해 상세히 알아보겠습니다. 절댓값 힙은 주어진 숫자의 절댓값을 기준으로 최소값 또는 최대값을 찾는 데이터 구조로, 일반적인 힙과 유사하지만 절댓값을 기준으로 동작합니다. 이 강좌에서는 문제 정의부터 시작하여, 알고리즘 설계 및 구현 단계까지 설명하겠습니다.
문제 정의
주어진 정수들에 대해 절댓값을 기준으로 정렬하기 위해, 우리는 다음과 같은 작업을 수행하는 프로그램을 작성해야 합니다:
- 절댓값 힙은 정수값을 삽입할 수 있습니다.
- 최소값을 반환하고 제거할 수 있습니다.
입력값은 다음과 같이 주어집니다:
- 입력 첫 줄에는 수행할 연산의 수
N이 주어집니다. - 이후
N개의 줄에 걸쳐 정수X가 주어집니다. 이때,X는 0이면 최소값을 반환하고 힙에서 제거합니다.
예제 입력
9
1
-1
0
-2
0
2
0
-3
0
예제 출력
1
-1
2
-2
-3
문제 해결 전략
이 문제의 가장 중요한 점은 정수 값을 삽입할 때, 절댓값에 따라 정렬해야 한다는 점입니다. 따라서 우선 정수 값을 삽입할 때, 기본적으로 파이썬의 heapq 모듈을 사용하여 최소 힙(min-heap)을 구현할 수 있습니다. 그러나 직접 절댓값을 기준으로 힙을 관리할 필요가 있습니다.
다음 전략을 사용할 수 있습니다:
- 입력값을 두 개의 요소를 가진 튜플로 변환하여 힙에 삽입합니다: (절댓값, 원래값).
- 힙에서 최소값을 가져올 때, 절댓값이 동일한 경우 원래값의 순서에 따라 반환합니다.
- 입력이 0일 때, 힙에서 최소값을 제거하고 반환합니다.
구현 단계
이제 위와 같은 전략을 기반으로 절댓값 힙을 구현해보겠습니다. 다음과 같은 코드를 사용하여 문제를 해결할 수 있습니다:
import heapq
import sys
input = sys.stdin.readline
def absolute_heap():
heap = []
N = int(input())
for _ in range(N):
X = int(input().strip())
if X != 0:
# 절댓값과 원래값을 쌍으로 힙에 삽입
heapq.heappush(heap, (abs(X), X))
else:
# 0이 입력되었을 때, 최소값을 꺼냄
if heap:
print(heapq.heappop(heap)[1])
else:
print(0)
if __name__ == "__main__":
absolute_heap()
코드 설명
1. heapq: 파이썬의 내장 힙 모듈입니다. 이를 통해 기본적으로 최소 힙을 쉽게 사용할 수 있습니다.
2. input: sys.stdin.readline을 이용해 입력을 빠르게 받을 수 있습니다.
3. heap: 절댓값과 원래 값을 쌍으로 저장하기 위한 리스트입니다.
4. 각 정수 X를 읽고, X가 0이 아닐 경우에는 그 값의 절댓값과 원래값을 쌍으로 힙에 삽입합니다.
5. X가 0일 경우에는 힙에서 최소값을 꺼내고 원래값을 출력합니다.
복잡도 분석
이 알고리즘의 시간 복잡도는 다음과 같습니다:
- 힙에 원소를 삽입할 때의 시간 복잡도는
O(log N)입니다. - 힙에서 원소를 꺼낼 때의 시간 복잡도도
O(log N)입니다.
따라서 전체 알고리즘의 시간 복잡도는 O(N log N)입니다.
결론
이번 강좌에서는 절댓값 힙의 개념을 이해하고, 이를 파이썬으로 구현하는 방법에 대해 알아보았습니다. 절댓값 힙을 구현하는 과정에서 중요한 것은 원래값과 절댓값을 잘 관리하는 것입니다. 오늘 배운 내용을 바탕으로 다양한 문제를 풀어보시기를 바랍니다.
추가 문제
아래의 문제를 풀어보며 절댓값 힙에 대한 이해를 더욱 깊이 있게 해보세요:
문제: 절댓값 힙을 사용하여 주어진 수의 합을 구하는 프로그램을 작성하세요. 절댓값 힙을 통해 최소값을 찾아내고, 모든 입력이 처리될 때까지 반복합니다.
위 문제를 해결하기 위해서는 힙에서 제거한 값을 누적하여 합계를 기록하면 됩니다. 직접 코드를 작성해보시고, 이번 강좌에서 배운 원리를 적용해보세요.
참고 자료
감사합니다. 다음 강좌에서 만나요!