알고리즘 썸네일형 리스트형 [알고리즘] 최소 스패닝 트리_ Kruskal & Prim 최소 스패닝 트리 (MST, Minimum Spanning Tree) 스패닝 트리란, 그래프에서 순환 없이 모든 정점을 잇는 부분 그래프를 의미한다. 최소 스패닝 트리란, 이러한 스패닝 트리 중에서 간선의 가중치의 합이 가장 작은 스패닝 트리를 의미한다. 이러한 최소 스패닝 트리를 구하는 알고리즘으로 크루스칼(Kruskal)과 프림(Prim) 알고리즘이 있다. 크루스칼 (Kruskal) 알고리즘 크루스칼 알고리즘은 모든 간선 중에서 가장 가중치가 작은 간선부터 연결해 주면서 최소 스패닝 트리를 만드는 알고리즘이다. 간선들을 연결하면서 순환이 발생한다면 해당 간선을 버리고 다음 간선을 선택하게 되는데 이 때, Union-Find 연산을 사용한다. 알고리즘 간선들을 가중치를 기준으로 오름차순으로 정렬한다. .. 더보기 [알고리즘] 최단 경로 문제_다익스트라 & 벨만포드 다익스트라 & 벨만포드 이 두 알고리즘은 그래프에서 최단 경로 문제를 해결할 때 사용되는 알고리즘이다. 최단 경로 문제? 최단 경로란 그래프에서 간선의 가중치의 합이 최소가 되는 경로를 찾는 문제이다. 최단 경로 문제를 푸는데 다양한 방법이 있지만, 다익스트라와 벨만포드를 정리해보려고 한다. 다익스트라 알고리즘(Dijkstra Algorithm) 다익스트라 알고리즘은 그래프에서 음의 가중치가 없을 때 최단 경로를 찾을 수 있다. V개의 정점과 양의 가중치를 가진 E개의 간선을 가진 그래프에서 출발 정점으로부터 모든 최단 경로를 찾을 수 있다. 알고리즘은 다음과 같이 진행된다. 현재 정점에 연결되어 있는 정점들을 모두 본다. 현재 정점과 연결되는 다음 정점으로의 거리와 시작 정점과 현재 정점까지의 최단 거.. 더보기 [알고리즘] 투 포인터 & 슬라이딩 윈도우 투 포인터 & 슬라이딩 윈도우 알고리즘 1차원 배열을 2회 이상 반복적으로 탐색을 해야할 경우 단순하게 한다면 O(N^2) 이상 시간 복잡도가 걸리지만 투 포인터와 슬라이딩 윈도우 알고리즘을 사용하게 된다면 부분 배열을 이용하여 시간 복잡도를 O(N)으로 줄일 수 있는 공통점이 있다. 투 포인터는 부분 배열의 길이가 변할 수 있지만, 슬라이딩 윈도우는 부분 배열의 길이가 고정적이라는 차이점이 있다. 투 포인터(Two Pointer) 투 포인터 알고리즘은 1차원 배열에서 각각 다른 원소를 가리키는 2개의 포인터를 조작해가면서 원하는 것을 얻는 알고리즘이다. 이러한 특성 때문에 투 포인터는 연속되고 길이가 가변적인 부분 배열들을 활용하여 특정 조건을 일치시키는 문제에 적용시킬 수 있다. 투 포인터로 해결해야.. 더보기 이전 1 다음