Algorithm/Algorithm for Beginner 썸네일형 리스트형 11. 최소 신장 트리(MST): 크루스칼 알고리즘(Kruskal's Algorithm) 최소 신장 트리 혹은 최소 스패닝 트리라고 불리는 MST(Minimum Spanning Tree)는 가중치가 포함된 무향의 그래프가 주어졌을 때, 모든 노드들이 포함되면서 비용은 최소가 되는 부분 그래프인 트리를 의미합니다. 이와 같은 조건을 만족하는 MST를 찾기위해 크루스칼 알고리즘(Kruskal's Algorithm)이나 프림 알고리즘(Prim's algorithm)을 사용합니다. 이 두가지 알고리즘은 동일한 시간복잡도를 갖고 있기 때문에 어느 알고리즘이 더 우월하다고 할 수 없으나, 크루스칼 알고리즘은 간선을 기준으로 구현되고, 프림 알고리즘은 노드 기준으로 알고리즘이 구현된다는 부분에서 차이를 갖고 있습니다. 이번에는 간선을 기준으로 한 크루스칼 알고리즘을 설명해보도록 하겠습니다. 크루스칼 알고.. 10. 유니온 파인드 (Union-Find) 유니온 파인드는 앞에서 공부한 최단 경로 탐색 알고리즘과 맥락을 달리하는 그래프 문제입니다. 최단 경로 탐색 알고리즘은 여러 노드와 간선 정보가 주어졌을 때 특정 노드에서 다른 노드로 이동하는데 얼마나 적은 비용으로 이동할 수 있는지 비용을 최소화 시키는 것을 목적으로 한다면 유니온 파인드 알고리즘은 노드간 연결 관계를 파악하고 특정 간선을 연결할 시 노드 연결관계가 어떻게 변화하는지 파악하는 알고리즘입니다. 예를 들어 설명하도록 하겠습니다. 어느 나라에 여러 도시들이 있었는데 도로가 하나도 안깔려있어서 서로 단절되어 있었습니다. 도시를 연결해야겠다고 생각한 한 사람이 도시 사이에 도로를 놓기로 했습니다. 하지만 어떤 도시들 사이에는 산이 있어서 직접 도로를 못 놓는 경우도 있었기 때문에 연결이 가능한 .. 9. 최단 경로 탐색: 벨만-포드 알고리즘(Bellman-Ford Algorithm) 벨만-포드 알고리즘은 다익스트라 알고리즘과 마찬가지로 최단 경로 탐색 알고리즘입니다. 노드와 가중치가 포함된 간선 정보를 이용하여 시작점과 도착점 사이의 최단 거리를 찾는 것이 이 알고리즘의 목적입니다. 설명만 들어서는 다익스트라 알고리즘과 일치합니다. 하지만 기본적인 최단 경로 탐색 알고리즘의 조건과 목적에 더하여 벨만-포드 알고리즘은 특정한 조건을 포함하고 있을 때 사용됩니다. 가중치에 음수가 포함된 경우입니다. 다익스트라 알고리즘은 기본적으로 가중치가 양수와 0으로 이루어져 있다는 것을 가정하고 있습니다. 그렇기 때문에 음수 가중치가 포함되어있다고 해도 알고리즘 자체에서 음수 가중치 부분을 처리할 수 없습니다. 벨만-포드 알고리즘의 원리는 다음과 같습니다. 우리가 특정 노드에서 다른 어떤 노드로 이.. 8. 최단 경로 탐색: 다익스트라 알고리즘(Dijkstra Algorithm) 다익스트라 알고리즘은 최단 경로 탐색 알고리즘중 가장 대표적인 알고리즘이라고 할 수 있습니다. 일반적으로 최단 경로 탐색 알고리즘 교육에서는 가장 첫 장으로 소개되기 마련이며, 최단 경로 탐색 알고리즘인 다익스트라 알고리즘, 벨만-포드 알고리즘, 플로이드-워셜 알고리즘 중에서 가장 시간복잡도가 낮습니다. 하지만 모든 최단 경로 탐색 문제에 다익스트라 알고리즘을 사용할 수 있는 것은 아닙니다. 다익스트라 알고리즘의 위키백과 정의를 살펴보겠습니다. 컴퓨터 과학에서, 데이크스트라 알고리즘(=다익스트라 알고리즘)(영어: Dijkstra algorithm)은 어떤 변도 음수 가중치를 갖지 않는 유향 그래프에서 주어진 출발점과 도착점 사이의 최단 경로 문제를 푸는 알고리즘이다. 이름은 네덜란드의 컴퓨터과학자 에츠허.. 7. 동적계획법(DP: Dynamic Programming)의 기초 동적계획법은 어떤 문제에서 최적해를 구해야할 때, 문제를 더이상 쪼갤 수 없는 단위로 쪼개서 제일 작은 부분부터 최적해를 누적해 나가는 방식으로 문제를 푸는 알고리즘을 의미합니다. 동적계획법이 가능한 것은 문제를 동일 형식의 연산이 반복될 수 있는 더 작은 문제로 쪼갤 수 있고, 작은 문제의 최적해를 이용해서 그보다 조금 더 큰 문제의 최적해를 도출할 수 있다는 것이 보장되기 때문입니다. 이러한 동적계획법의 풀이 방식에 근거하여 동적계획법 풀이는 크게 두가지가 핵심적으로 작동한다고 할 수 있는데 한 가지는 초기조건, 다른 한 가지는 점화식입니다. 초기조건은 말그대로 문제를 가장 작은 단위로 쪼개었을 때 연산없이 확정되어있는 최적해를 의미합니다. 동적계획법은 동일 연산을 가장 작은 크기의 문제부터 반복 적.. 6. DFS와 BFS 깊이 우선 탐색(DFS: Depth First Search)과 너비 우선 탐색(BFS: Breadth First Search)는 탐색방법 중 가장 기본이 되는 방식입니다. 이름에 어떠한 방식으로 탐색이 이루어지는지 압축적으로 제시된 것만큼 그 사용목적과 방법이 확실한 알고리즘이라고 할 수 있습니다. DFS는 말그대로 깊이를 우선하여 탐색하는 알고리즘입니다. 만일 격자 모양으로 구성된 하나의 그래프가 주어졌다고 생각해보겠습니다. 중간에 끊김없이 한칸한칸을 모두다 탐색해야한다고 했을 때 우리가 취할 수 있는 방법은 마치 한 손 그림을 그리듯 쭉 타고 가면서 하나씩 노드들을 방문하는 것입니다. 오른쪽으로 쭉타고 가다가 더이상 오른쪽으로 갈 수 없으면 밑으로 그리고 더이상 밑으로 갈 수 없으면 왼쪽으로 또 더이.. 5. Stack과 Queue Stack과 Queue는 앞에서 다루었던 Array나 List와는 다른 확실한 개성을 갖고 있는 자료구조입니다. Array와 List가 자료를 공간에 하나씩 배정하고 특정 공간을 지목하여 자료를 꺼내 사용하는 단순한 방식을 지향한다면 Stack과 Queue는 자료가 들어온 순서와 그 순서에 따라 자료를 꺼내는 방식을 취하고 있습니다. Array와 List처럼 특정 주소를 지목하여 값을 꺼낼 수 없고, 중간에 입력된 자료를 꺼내기 위해서는 그 자료 앞이나 뒤에 있는 모든 자료를 비워내었을 때 그 자료를 꺼낼 수 있는 것입니다. 사용하기에 불편할 것 같은 이 자료구조는 왜 그리고 어떻게 사용하는 것인지 알아보겠습니다. 먼저 Stack부터 설명하겠습니다. Stack은 쌓다라는 뜻을 갖고 있습니다. Stack은.. 4. Comparator를 이용한 Array와 List의 정렬 Java프로그램에서 Array나 List에 저장된 value를 정렬할 때 가장 많이 쓰는 방식은 Arrays class나 Collections class를 import하여 정렬하는 방식입니다. 빠른 정렬을 개발자가 직접 구현하여 사용하는 것도 가능하지만, Arrays나 Collections에서 구현된 sort 함수는 정렬방식 중 가장 시간 복잡도가 작은 방식으로 최적화되어 있기 때문에 시간을 더 줄일 수 있지 않을까 하는 생각으로 직접 구현할 필요는 없습니다. 하지만 일반적인 Arrays.sort()나 Collections.sort()를 이용하다보면 발생하는 문제가 있습니다. Array든 List든 값을 오름차순으로만 정렬한다는 것과 이차원 배열 등 다차원 배열의 정렬이 되지 않는다는 것입니다. Java.. 이전 1 2 3 다음