Dev On The Coffee Dev On The Coffee

# 문제 내 풀이 import heapq def solution(scoville, K): answer = 0 # 최소 힙 생성하기 h = [] for i in scoville: heapq.heappush(h, i) while True: low1 = heapq.heappop(h) # 첫 번째 원소가 K보다 크거나 같다면, 루프를 탈출하고 최소 횟수 리턴 if low1 >= K: break # 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우, -1 리턴 if not h: return -1 low2 = heapq.heappop(h) # 가장 덜 매운 두 요소의 스코빌 지수가 0이라면, -1 리턴 if low1 == 0 and low2 == 0: return -1 mixed_s = low1 + 2 *..

# 최단 경로 알고리즘 (Shortest Path Algorithm) 최단 경로 알고리즘(Shortest Path Algorithm)이란 가장 짧은 경로를 찾는 알고리즘을 말한다. 최단 경로를 찾는 것은 여러가지 상황이 존재할 수 있는데, 대표적으로 (1) 한 지점에서 다른 한 지점까지의 최단 경로를 찾는 상황 (2) 한 지점에서 다른 모든 지점까지의 최단 경로를 찾는 상황 (3) 모든 지점에서 다른 모든 지점까지의 최단 경로를 찾는 상황을 생각해 볼 수 있다. 최단 경로 알고리즘은 일반적으로 그래프 자료구조를 기반으로 해 진행된다. 각 지점은 노드(Node)로 나타내고, 지점 사이를 연결하는 도로는 간선(Edge)으로 표현한다. 예를 들어, 노드는 도시, 마을, 국가 등으로, 간선은 도로, 통로 등으로..

# 우선순위 큐 (Priority Queue) 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조이다. 데이터를 우선순위에 따라 처리하고 싶을 때 사용한다. 우선순위 큐는 리스트(List), 힙(Heap) 두가지 방식으로 구현 가능하다. 리스트의 경우 데이터를 단순히 리스트의 뒤에 삽입하고 우선순위를 기준으로 선형탐색한다. 따라서 삽입시간은 시간복잡도가 O(1)이지만, 삭제시간은 선형탐색으로 인해 O(N)이 소요된다. 반면, 힙은 삽입시간, 삭제시간 모두 O(logN)의 시간복잡도를 보장한다. 힙의 또다른 특징은 단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업만으로도 정렬이 수행된다는 점이다. 이를 힙 정렬(Heap Sort)이라 하는데, 힙 정렬은 O(NlogN)의 시간 복..