DevLog

알고리즘/기술면접 완전 정복 올인원 패키지 Online 최소 신장 트리의 이해 2 - 참고_개선된 프림 알고리즘 최소 신장 트리의 이해 2 - 개선된 프림 알고리즘의 시간 복잡도 백트래킹 - 백트래킹 기법의 이해 시간 복잡도 최악의 경우, while 구문에서 모든 간선에 대해 반복하고, 최소 힙 구조를 사용하므로 O(𝐸𝑙𝑜𝑔𝐸ElogE) 시간 복잡도를 가짐 개선된 프림 알고리즘 간선이 아닌 노드를 중심으로 우선순위 큐를 적용하는 방식 초기화 - 정점:key 구조를 만들어놓고, 특정 정점의 key값은 0, 이외의 정점들의 key값은 무한대로 놓음. 모든 정점:key 값은 우선순위 큐에 넣음 가장 key값이 적은 정점:key를 추출한 후(pop 하므로 해당 정점:key 정보는 우선순위 큐에서 삭제됨), (e..

알고리즘/기술면접 완전 정복 올인원 패키지 Online 최소 신장 트리의 이해 2 - 프림 알고리즘이란 최소 신장 트리의 이해 2 - 프림 알고리즘 코드 작성 최소 신장 트리의 이해 2 - 프림 알고리즘 파이썬 코드 - 1 최소 신장 트리의 이해 2 - 프림 알고리즘 파이썬 코드 - 2 프림 알고리즘 (Prim's algorithm) 대표적인 최소 신장 트리 알고리즘 Kruskal’s algorithm (크루스칼 알고리즘), Prim's algorithm (프림 알고리즘) 프림 알고리즘 시작 정점을 선택한 후, 정점에 인접한 간선중 최소 간선으로 연결된 정점을 선택하고, 해당 정점에서 다시 최소 간선으로 연결된 정점을 선택하는 방식으로 최소 신장 트리를 확장해가는 방식 Kruskal's algorithm..