반응형 분류 전체보기313 프림 알고리즘(Prim Algorithm) 이번에 배워볼 알고리즘은 크루스칼 알고리즘(Kruskal Algorithm)과 같이 최소 비용 신장 트리(MST)를 구하는 프림 알고리즘(Prim Algorithm)이다. 크루스칼 알고리즘은 간선 선택을 기반으로 하는 알고리즘이었다면, 프림 알고리즘은 정점 선택을 기반으로 하는 알고리즘이다. 또한, 크루스칼 알고리즘은 이전 단계에서 만들어진 신장 트리와는 상관없이 무조건 최소 간선만을 선택하는 방법이라면, 프림 알고리즘은 이전 단계에서 만들어진 신장 트리를 확장하는 방식이다. 프림 알고리즘은 그리디 알고리즘에 속한다. 그 이유는 추가할 새로운 정점을 선택할 때 최소 비용을 가지는 간선을 선택하기 때문이다. 프림 알고리즘의 동작 원리는 다음과 같다. 시작 정점을 선택한다. 현재 구성된 신장 트리에 속.. 2021. 7. 4. 크루스칼 알고리즘(Kruskal Algorithm) 최소 비용 신장 트리(MST)를 구하는 알고리즘은 크루스칼 알고리즘(Kruskal Algorithm)과 프림 알고리즘(Prim Algorithm)이 존재한다. 이번에 배워볼 알고리즘은 이전에 배운 합집합 찾기(Union Find)에서 언급한 크루스칼 알고리즘(Kruskal Algorithm)이다. 크루스칼 알고리즘은 그리디 알고리즘이라고 불린다. 그 이유는 추가할 새로운 간선을 선택할 때 최소 비용을 가지는 간선을 선택하기 때문이다. 우선 크루스칼 알고리즘을 배우기 전에 신장 트리가 무엇인지에 대해서 알고 넘어가자. 신장 트리란 그래프 내의 모든 정점을 포함하는 트리를 뜻한다. 신장 트리는 트리의 특수한 형태이므로 모든 정점들이 연결되어 있어야 하고 사이클을 포함해서는 안 된다. 따라서 신장 트리는 .. 2021. 7. 4. 백준 1525 : 퍼즐 https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net [ 문제풀이 ] bfs를 수행하여 0을 옮길 수 있는 모든 경우를 탐색해주면 된다. 퍼즐의 상태를 쉽게 관리하기 위해 3x3 배열이 아닌 1차원의 문자열 형태로 관리하였다. 퍼즐의 상태와 중복 방문을 관리해줄 방법만 생각해낸다면 쉽게 해결할 수 있을 것이다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStrea.. 2021. 7. 4. 합집합 찾기(Union Find) 이번에 배워볼 알고리즘은 합집합 찾기(Union Find) 알고리즘이다. 서로소 집합(Disjoint Set) 알고리즘이라고도 불리는 이 알고리즘은 그래프 상의 두 개의 노드가 같은 그래프에 속하는지를 판별하기 위해 사용되는 알고리즘이다. 다음에 배울 최소 비용 신장 트리(MST)를 구성하는 알고리즘 중 하나인 크루스칼(Kruskal) 알고리즘이 합집합 찾기 알고리즘을 응용한 알고리즘이다. 합집합 찾기 알고리즘의 원리는 다음과 같다. 자신의 부모 노드를 저장하는 1차원 배열을 선언 후 각 정점의 부모를 자신을 가리키도록 초기화한다. 두 개의 노드를 선택하여 Union 연산을 수행하면 두 개의 노드의 부모를 하나의 노드로 통일한다. 이때 더 작은 번호를 가리키도록 부모를 통일한다. 두 개의 노드를 선택.. 2021. 7. 3. 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm) 이번에 배워볼 알고리즘은 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)이다. 이전에 배운 다익스트라, 벨만-포드 알고리즘은 한 정점에서 다른 정점으로 가는 최단 경로를 구하는 알고리즘이었다면, 플로이드-워셜은 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘이다. 플로이드 워셜 알고리즘은 벨만-포드 알고리즘처럼 음의 간선이 존재하여도 모든 최단 경로를 구할 수 있다. 물론 음의 사이클이 존재하면 불가능하다. 또한, 이전에 저장해놓은 최단 경로를 이용해서 새로운 최단 경로로 갱신하는 과정에서 플로이드 워셜 알고리즘 역시 다이나믹 프로그래밍이라고 할 수 있다. 플로이드 워셜 알고리즘의 핵심은 간단하다. 이전에 다익스트라나 벨만 포드 알고리즘에서 정점 A에서 정점 C까지 가.. 2021. 7. 3. 벨만-포드 알고리즘(Bellman-Ford Algorithm) 이번에 배워볼 알고리즘은 벨만 포드 알고리즘(Bellman-Ford Algorithm)이다. 이 알고리즘 또한 이전에 배운 다익스트라 알고리즘처럼 그래프에서 한 정점에서 다른 모든 정점으로 가는 최단 경로를 구할 수 있는 알고리즘이다. 벨만 포드 알고리즘은 다익스트라 알고리즘보다 시간이 더 걸리지만 음의 간선이 존재해도 최단 경로를 찾을 수 있는 알고리즘이다. 벨만 포드 알고리즘은 다이나믹 프로그래밍이라고 할 수 있다. 그 이유는 매번 저장해놓은 최소 비용을 이용해서 새로운 최소 비용으로 갱신하기 때문이다. 벨만 포드 알고리즘이 다익스트라 알고리즘보다 시간이 오래 걸리는 이유는 다익스트라는 최소 비용을 가지는 간선만 우선적으로 뽑으면서 경우의 수를 줄여가며 비용을 갱신하였다. 하지만 벨만 포드 알고리즘.. 2021. 7. 3. 다익스트라 알고리즘(Dijkstra Algorith) 이번에 배워볼 알고리즘은 그래프에서 최단 경로를 찾기 위한 알고리즘 중 하나인 다익스트라 알고리즘(Dijkstra Algorith)이다. 다익스트라 알고리즘은 한 정점에서 나머지 모든 정점으로 가는 최단 경로를 구할 수 있는 알고리즘이다. 단, 그래프 내에 음의 간선(경로)이 존재한다면 다익스트라 알고리즘을 적용할 수가 없다. 다익스트라 알고리즘은 다이나믹 프로그래밍, 그리디 알고리즘으로 분류된다. 이전에 구했던 최단 경로 정보를 이용하기 때문에 다이나믹 프로그래밍이라고 불리며, 가장 최단 경로인 간선을 선택하기 때문에 그리디 알고리즘이라고 불린다. 다익스트라 알고리즘의 동작원리는 다음과 같다. 시작 정점을 선택한다. 시작 정점을 기준으로 다른 정점으로 가는 비용을 저장한다. 현재 방문하지 않는 정점.. 2021. 7. 3. 백준 16437 : 양 구출 작전 https://www.acmicpc.net/problem/16437 16437번: 양 구출 작전 2, 3, 5번에 사는 모든 양들은 1번 섬으로 갈 수 있지만 7번 섬에 사는 양들은 1번 섬으로 가기 위하여 6번 섬을 거쳐야 하는데 6번 섬에 사는 늑대들의 수가 7번 섬에 사는 양들의 수보다 많으므로 www.acmicpc.net [ 문제풀이 ] 골드 2 난이도 치고는 굉장히 간단한 문제이다. "각 섬에서 1번 섬으로 가는 경로는 유일하다"라는 문장 때문에 모든 섬을 연결한 상태는 그래프가 아닌 트리라는 것을 알 수 있다. 따라서 1번 노드를 기준으로 dfs를 수행하며 말단 노드부터 거슬러 올라오면서 양 or 늑대인 경우를 처리해주면 쉽게 해결할 수 있다. 주의해야 할 점은 정답의 범위가 int 범위를 넘.. 2021. 7. 3. 너비 우선 탐색(Breadth First Search) : BFS 이번에 배워볼 알고리즘은 너비 우선 탐색(Breadth First Search)이다. 줄여서 흔히 BFS라고 부른다. 깊이 우선 탐색은 깊이를 우선시하였다면 너비 우선 탐색은 너비를 우선시하는 탐색 방법이다. 또한, 노드에서 다른 노드로 가는 최단 경로를 구할 때 깊이 우선 탐색은 한 노드의 끝까지 탐색하기 때문에 최단 경로를 보장해 주지 않지만 너비 우선 탐색은 항상 같은 깊이 내에 있는 모든 노드들을 탐색하기 때문에 최단 경로를 보장해 준다는 장점이 있다. 깊이 우선 탐색은 스택(Stack)을 이용하여 구현하였다면, 너비 우선 탐색은 큐(Queue)를 이용해서 구현한다. 너비 우선 탐색의 원리는 다음과 같다. 큐에서 노드 하나를 꺼낸다. 큐에서 꺼낸 노드에 인접한 노드들 중 아직 방문하지 않은 .. 2021. 7. 2. 이전 1 ··· 29 30 31 32 33 34 35 다음 반응형
