PinguiOS

안녕하세요~ Ick입니다. 오늘은 최소 비용 신장 트리에 대해 알아본 글에 이어 최소 비용 신장 트리의 한 종류인 크루스칼 알고리즘을 직접 구현해보려고 합니다. 자세한 설명은 여기를 참고해주세요! 크루스칼 알고리즘 (Kruskal Algorithm) 위의 링크로 가시면 크루스칼 알고리즘에 대한 자세한 설명을 볼 수 있지만 간단하게 요약하면 이렇습니다. - 음수 가중치가 없는 무방향 그래프에서 모든 정점을 최소의 비용으로 연결하는 방법. - 이 때 사이클이 발생하면 안 된다. - 크루스칼 알고리즘은 가중치가 작은 간선부터 확인하는 알고리즘이다. 그런데 사이클이 발생한 것을 어떻게 알 수 있을까요?.? Union Find 여기서 사이클을 확인하는 방법에 사용되는 개념이 Union Find(합집합 찾기)라는 ..

안녕하세요! Ick입니다. 오늘은 가중치가 음수가 아닌 그래프에서 하나의 노드로부터 다른 노드들까지의 최단거리를 알 수 있는 다익스트라 알고리즘에 대해 알아보려고합니다. 다익스트라 알고리즘을 그냥 있는 그대로 나타내는 방법과 우선순위 큐를 사용하는 방법이 있는데요... 저는 우선순위 큐를 사용한 다익스트라 알고리즘을 이해하는데 정말 오래 걸렸습니다.ㅠ,ㅠ 그래서 다신 까먹지 않기 위해 글을 써보려고 합니다! 다익스트라 알고리즘 - Dijkstra 우선 다익스트라 알고리즘은 간선의 음수인 가중치가 없는 그래프에서만 사용할 수 있습니다. 여기서 방향 그래프, 무방향 그래프는 상관이 없습니다. 또한 하나의 노드에서 다른 모든 노드의 최단거리를 구하는 알고리즘이란 것을 기억해야 합니다!! 위의 그래프로 다익스트..

안녕하세요 Ick입니다. 오늘은 여러 정렬 알고리즘 중 힙 정렬에 대해 공부했고 그에 대한 내용을 정리해볼까 합니다! 힙 정렬 (Heap Sort) 우선 정렬 알고리즘에는 버블 정렬, 병합 정렬, 퀵 정렬 등 여러 방법이 있는데요, 힙 정렬은 그중 시간 복잡도 O(N*logN)의 성능을 보이는 정렬 알고리즘입니다! 이러한 힙 정렬을 이해하기 위해선 힙(Heap)이라는 개념을 이해하셔야 합니다. 가장 중요한 것은 완전이진트리구조를 갖는다는 것입니다. 힙에는 최대 힙, 최소 힙이 있는데 최대 힙은 부모 노드가 자식 노드보다 값이 큰 힙을 말하며, 최소힙은 부모 노드가 자식 노드보다 값이 작은 힙을 말합니다. 그림으로 힙을 살펴보면 위와 같습니다. 최대 힙같은 경우엔 부모 노드가 자식 노드보다 커야 하므로 자..

안녕하세요! Ick입니다. 최소 비용 신장 트리 - Minimum Cost Spanning Tree 오늘은 여러 알고리즘 중에서 최소 비용 신장 트리라고 불리는 알고리즘에 대해 알아보려고 합니다! 최소 비용 신장 트리, 최소 스패닝 트리라고 불리는 이 알고리즘은 가중치 무방향 그래프에서 모든 정점을 연결할 때 최소의 비용으로 연결할 수 있는 방법을 찾는 알고리즘입니다. 가중치 무방향 그래프는 무엇일까요? 위와 같이 그래프가 있을 때 정점 사이에 가중치가 있고 간선에 방향이 없는 그래프를 가중치 무방향 그래프라고 합니다. 예를 들어 위의 그래프에서 정점 1에서 정점 3으로 가고 싶다면 25의 가중치를 가진 간선을 사용하면 되는 것입니다. 이번 글에서 배울 최소 비용 신장 트리는 이러한 그래프에서 모든 정점..