🤯Algorithm3 최소 최대 힙, 트리 관련 알고리즘 강의 필기 힙은 완전 이진트리 자료구조의 일종. 힙에서는 항상 루트노드를 제거하는 방식으로 작동 최소힙 - 루트노드가 가장 작은값 최대힙 - 루트노드가 가장 큰값 원소가들어올때. 최소힙 구성함수, min-heapify -새로운 데이터가 들어왔을때 heapify 함수가 동작하면 오름차순,내림차순 등으로 힙성질을 유지하도록 유지해줌. -최악의 경우에도 log n 의 시간복잡도를 가짐 원소가 제거될때 그냥 빈자리에 가장 마지막 자식을 넣으면 자동으로 heapify 가 수행되고, 다시 힙의성질이 만족되는 형태로 구성이된다. 따라서 힙에서 원소를 넣거나뺄때 로그n의 일관적인 시간복잡도를 유지할수있다는 장점. - 가계도같은 계층적 구조를 표현할때 쓰는 자료구조 -이진탐색이 동작할수 있도록 고안된 효율적인 탐색이 가능한 트리의.. 2021. 11. 3. 크루스칼 알고리즘 (최소스패닝트리,cut property, disjoint set 에 기반하여.) 크루스칼 알고리즘은 최소스패닝 트리를 구하는 알고리즘 중 하나이다. 우선 스패닝 트리에 대해알아보자. 스패닝트리 : 그래프의 모든 노드를 포함하는 트리. -> 즉 한붓그리기 가능하면 그 한붓을 스패닝트리 라고함. 한가지 그래프가 있으면 여러개의 스패닝트리가 존재한다. 스패닝트리의 weight = 그 스패닝트리의 가중치합. 스패닝 트리들 중에 weight 가 최소인거 : 최소스패닝 트리. -> 즉 최소스패닝트리 : 그래프의 모든 노드를 포함하는 트리중에 간선 가중치의 합이 최소인 트리. 최소스패닝 트리 구하는 알고리즘중 하나인 크루스칼 알고리즘, 이제좀 감이 잡힌다. 배워보려고 하는데 여기서 우선, 컷정리(cut property) 를 알아야 크루스칼 알고리즘을 배울수있다. 컷 프로퍼티란? 컷.. 2021. 5. 20. 다익스트라 알고리즘 -1 다익스트라 알고리즘은 무엇이고 어떤 용도로 쓰는가? 가중치가 있는 그래프에서 최단거리를 구할 때 쓴다. 여기서 잠깐!! 무방향 인접 그래프에서 최단거리에 관련된 알고리즘은 다음과 같이 대표적으로 3가지 종류가 있음. 1.다익스트라 알고리즘 - 하나의 정점에서 모든 정점까지 최단거리를 다구함 (1 : n) - 간선의 가중치가 양수일때만 사용가능 2.플로이드 알고리즘 -모든 정점에서 모든 정점까지 최단거리를 다구함 ( n : n, 물론 1보다 오래걸림) 3.벨만포드 알고리즘 - 하나의 정점에서 모든 정점까지 최단거리를 다 구함 (1 : n) - 간선의 가중치가 양수,음수 상관없이 사용가능 우선, 모오오오든 최단경로문제를 관통하는 키포인트는 이것이다. 정점 x에서 y까지 최단거리로 가려면 그 직전(y-.. 2021. 5. 20. 이전 1 다음 반응형