오늘은 크리스마스다~~~ 와아아아
크리스마스라고 스터디 팀원분이 크리스마스 선물이라는 알고리즘 문제를 내주셨다 ㅋㅋ
난이도는 높지않아서 한번에 성공은 했다.
import sys
input=sys.stdin.readline
n=int(input())
gifts=[]
for _ in range(n):
nums=list(map(int,input().split()))
if nums[0]==0:
if not gifts:
print(-1)
else:
gifts.sort()
print(gifts.pop())
else:
for i in range(1,nums[0]+1):
gifts.append(nums[i]) 그런데 시간이 1476ms만큼 걸려서 충분히 더 최적화 할수있는 방법이 있겠다 생각이들었다.
그래서 알고리즘 분류를 봤더니, 우선순위 큐(힙)을 사용하는 문제였다.
힙을 써본지가 오래되서 다시 문법을 찾아가며 코드를 수정했다.
import sys
import heapq
input=sys.stdin.readline
n=int(input())
gifts=[]
for _ in range(n):
nums=list(map(int,input().split()))
if nums[0]==0:
if gifts:
print(-heapq.heappop(gifts))
else:
print(-1)
else:
for gift in nums[1:]:
heapq.heappush(gifts,-gift) 우선순위 큐는 기본적으로 최소힙 방식으로 구현되어있어 최대를 빠르게 찾으려면 값에 - 를 붙인고 큐에 넣은뒤 뺄때 -를 다시 붙여 빼면된다.
이렇게 수정하니 정말 시간이 1/10 정도로 단축되었다..ㄷㄷ 힙의 힘!
힙 자료구조를 사용하는 경우
힙은 최대값이나 최소값을 효율적으로 유지하고 싶을 때 가장 적합합니다. heapq는 파이썬에서 최소 힙으로 구현되어 있으며, 최대값을 유지하려면 값을 음수로 변환하는 방식으로 활용합니다.
활용 사례
우선순위 큐: 작업의 우선순위를 관리해야 할 때.
예: CPU 작업 스케줄링, 네트워크 패킷 처리.
가장 높은 우선순위의 작업을 빠르게 찾고 처리할 수 있음.
K번째 최댓값/최솟값 찾기:
예: 데이터 분석에서 상위 K개 점수만 추출할 때.
힙의 크기를 제한하여 효율적으로 관리.
다익스트라 알고리즘:
그래프에서 최단 경로를 계산할 때 우선순위 큐로 활용.
예: 지도 앱에서 최단 거리 찾기.
실시간 스트림 데이터 처리:
예: 실시간 데이터 스트림에서 중간값(Median)을 계산할 때.
최대 힙과 최소 힙을 활용하여 효율적으로 중간값 유지.
스케줄 관리:
예: 우선순위에 따라 작업을 정렬하여 진행해야 하는 상황.
일정이 겹치지 않도록 조율하거나, 가장 빠른 일정만 유지.
힙 자료구조와 관련된 백준 문제들은 우선순위 큐, 최대/최소값 처리, 데이터 정렬과 관련이 있습니다. 아래는 추천 문제 리스트입니다:
기본 힙 활용 문제
-
11279 - 최대 힙
- 문제 링크
heapq를 활용하여 최대 힙을 구현하는 문제입니다.
-
11286 - 절댓값 힙
- 문제 링크
- 절댓값을 기준으로 힙을 구성해야 하는 문제로, 우선순위 큐의 활용을 배우기에 적합합니다.
-
1927 - 최소 힙
- 문제 링크
- 기본적인 최소 힙 문제입니다. 가장 작은 값을 효율적으로 반환하는 연습을 할 수 있습니다.
중급 힙 활용 문제
-
2075 - N번째 큰 수
- 문제 링크
heapq를 사용하여 N번째 큰 값을 효율적으로 찾아야 합니다.
-
13549 - 숨바꼭질 3
- 문제 링크
- 다익스트라 알고리즘과 힙을 활용해야 하는 문제로, BFS와 힙의 결합을 배울 수 있습니다.
-
1781 - 컵라면
- 문제 링크
- 데드라인이 있는 작업을 최대한 효율적으로 처리하기 위한 문제입니다. 힙을 활용한 스케줄링 연습이 가능합니다.
고급 힙 활용 문제
-
1655 - 가운데를 말해요
- 문제 링크
- 두 개의 힙(최대 힙, 최소 힙)을 사용해 실시간으로 중간값을 구하는 문제입니다. 힙 자료구조의 고급 활용법을 배우기에 적합합니다.
-
7662 - 이중 우선순위 큐
- 문제 링크
- 최대값과 최소값을 동시에 처리해야 하며, 힙을 두 개 사용하거나 다른 자료구조와 결합해야 합니다.
-
1202 - 보석 도둑
- 문제 링크
- 각 가방의 용량에 맞춰 보석의 가치를 최대화하는 문제로, 힙과 그리디 알고리즘의 결합을 학습할 수 있습니다.
-
13975 - 파일 합치기 3
- 문제 링크
- 최소 힙을 사용하여 최소 비용으로 파일을 합치는 문제입니다.
선택 팁
- 입문자:
1927,11279,11286과 같은 기본 문제로 시작하세요. - 중급자:
1655,1781,2075를 풀어보며 힙의 응용을 연습하세요. - 고급자:
7662,13549,1202같은 문제는 복합적인 알고리즘을 요구하므로 도전해보세요.
gpt가 추천해준 힙 연습 문제들도 틈틈히 공부해봐야겠다!
