1. 개요 수열이 계속 변화할때, 이 수열의 중앙값을 어떻게 빠르게 구할 수 있을까 매번 정렬해서 중간의 값을 찾아야하는가? 최대 힙과 최소 힙을 이용하면 중앙값을 아주 쉽게 찾을 수 있다 결론부터 말하자면, (크기와는 무관하게) 항의 순서대로 수열이 주어질때 최대힙에 들어간 원소의 수와 최소힙에 들어간 원소의 수가 서로 같을 때는 최대힙에 수를 넣어주고 최대힙의 원소의 수가 최소힙의 원소의 수보다 1개 더 많을때는 최소힙에 수를 넣어준다 즉 항상 최대힙 > 최소힙 > 최대힙 > 최소힙 >.. 으로 번갈아가면서 수를 넣어준다. 힙은 완벽하게 정렬해주지는 않지만, 루트에는 최소힙이면 힙에 들어간 원소들 중 최솟값이, 최대힙이면 힙에 들어간 원소들 중 최댓값이 온다는건 확실하다 최대힙에 원소를 넣으면 최대힙..
1. 개요 다익스트라 알고리즘을 간단히 구현하면 시간 복잡도가 $O(V^{2})$이지만 이제부터 배울 구현 방법을 이용하면 최악의 경우에도 $O(ElogV)$를 보장하여 해결할 수 있다. 여기서 V는 노드의 개수이고 E는 간선의 개수이다. 간단한 다익스트라 알고리즘은 "최단 거리가 가장 짧은 노드"를 찾기 위해 매번 최단 거리 테이블을 선형적으로 (모든 원소를 앞에서부터 하나씩) 탐색해야 했다. 이 과정에서만 O(V)의 시간이 걸린다. 하지만 최단 거리가 가장 짧은 노드를 단순히 선형적으로 찾는 것이 아니라 더욱 더 빠르게 찾을 수 있다면 어떨까? 개선된 다익스트라 알고리즘에서는 힙 자료구조를 사용한다. 힙 자료구조를 이용하면 특정 노드까지의 최단 거리에 대한 정보를 힙에 담아 처리하므로, 출발 노드부터..
1. 개요 가중치가 있는 무방향 그래프에서 최소 신장 트리를 찾는 대표적인 알고리즘 중 하나이다. 크루스칼 알고리즘이 간선들을 선택해가면서 최소 신장 트리를 구성하는 반면에 프림 알고리즘은 정점을 선택하고, 인접한 정점 중에서 최소 비용을 가지는 간선을 하나씩 선택해가면서 최소 신장 트리를 구성하는 일종의 그리디 알고리즘이다. 다익스트라 알고리즘과 사실상 동일한 알고리즘이다. 참고로 다익스트라 알고리즘은 음수 가중치에서는 동작하지 않지만, 프림 알고리즘은 음수 가중치에서도 동작한다고 한다 2. 알고리즘 2-1) 임의의 정점을 하나 선택해서 최초의 트리를 구성 2-2) 선택한 정점과 트리에 포함된 정점들과 인접한 정점중 최소 비용의 간선이 존재하는 정점을 선택한다 2-3) 모든 정점이 선택될 때까지 위 과..
1. 문제 https://programmers.co.kr/learn/courses/30/lessons/42626 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같 programmers.co.kr 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다. 섞은 음식의 스코빌 지수=가장 맵지 않은 음식의 스코빌 지수+(두 번째로 맵지 않은 음식의 스코빌..
최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전이진트리 트리는 root node에서 밑으로 가지를 뻗어나가는 형태의 자료구조로 binary tree인 이진 트리는 최대 2개까지만 자식 노드를 가진다 최소힙은 부모 node가 자식 node보다 항상 작은 binary tree 최대힙은 부모 node가 자식 node보다 항상 큰 binary tree heap은 배열로 구현되며 파이썬에서는 list로 만들어진다 import heapq를 통해 파이썬에서 heapq 관련 함수 사용가능 기존 리스트를 heapq로 만들려면 heapify()를 이용 heap2 = [50,10,20] heapq.heapify(heap2) print(heap2) [10,50,20] 혹은 빈 리스트를 생생한 후에 heappush..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
