Computer Science/Algorithm (16) 썸네일형 리스트형 [Algorithm] Prim's Algorithm (프림 알고리즘) 1. Prim's Algorithm 프림 알고리즘은 크루스칼과 달리 정점을 기준으로 MST를 구성하는 방법이다. MST에 포함된 정점 집합과 아직 포함되지 않은 정점 집합, 두가지를 가지고 수행되는 알고리즘이다. 매 순서마다 두 집합을 연결하고 있는 edge들을 모두 확인하여 가장 작은 가중치를 가지고 있는 edge를 선택하여 해당 edge와 연결되어 있는 정점을 MST에 포함시키는 방식으로 확장한다. 2. 프림 알고리즘 구현 1) MST에 포함된 정점을 저장할 집합을 선언하고 MST에 포함되어 있는 정점을 추가하여 초기화한다. 2) 각 정점의 거리를 표현하는 공간을 선언하고 MST에 포함된 정점은 0으로 나머지는 무한대로 초기화한다. 3) 아직 MST에 포함되지 않은 정점 중 가장 최단 거리를 가지고 .. [Algorithm] Kruskal's Algorithm (크루스칼 알고리즘) 1. Kruskal's Algorithm 크루스칼 알고리즘은 edge를 그리디하게 선택하여 MST를 구성하는 알고리즘이다. edge를 가중치 기준으로 오름차순으로 정렬한 후 가장 작은 edge부터 순서대로 subtree에 추가하여 MST를 구성한다. 이때 해당 edge가 cycle을 이루는지 확인을 해야하는데, 이때 union-find 알고리즘은 사용하는데, 각 정점에 index를 주어서 정점들이 연결될 때마다 해당 그룹의 정점들이 모두 같은 index를 가지도록 하여 이를 비교하여 같은 index를 가지는 경우 cycle로 인식한다. 2. 크루스칼 알고리즘 구현 1) 그래프의 간선을 오름차순으로 정렬한다. 2) 가장 작은 간선을 선택하여 cycle을 그리는지 확인한다. 3) cycle을 그리는 경우는 .. [Algorithm] Floyd-Warshall's Algorithm (플로이드-와샬 알고리즘) 1. Floyd-Warshall's Algorithm 플로이드 와샬 알고리즘은 모든 정점간의 최단 거리를 구하는 All pairs shortest path solving 알고리즘이다. 플로이드 와샬 알고리즘은 거쳐가는 정점을 기준으로 최단 거리를 구한다. 두 정점의 최단 거리를 구할 때 다른 모든 정점을 후보로 각 정점들을 거쳐갈 때의 거리를 비교하여 최소가 되는 경로를 찾는다. 소스 코드를 보면 가장 간단한 알고리즘이다. 2. 플로이드 와샬 알고리즘 구현 플로이드 와샬 알고리즘은 모든 정점 쌍에 대해서 다른 정점들을 중간 경로로 거치는 경로의 거리를 비교하여 최단 거리를 구한다. 1) 먼저 현재 그래프의 간선들을 기준으로 각 정점간의 거리를 저장할 행렬을 초기화한다. 2) 중간 경로가 될 정점을 선택한.. [Algorithm] Bellman-Ford Algorithm (벨만 포드 알고리즘) 1. Bellman-Ford Algorithm 벨만 포드 알고리즘은 다익스트라 알고리즘과 같이 한 정점으로부터 다른 모든 정점으로의 최단 경로를 찾는 알고리즘이다. 다익스트라 알고리즘과의 차이점은 음수 가중치를 가진 간선이 그래프에 존재해도 적용이 가능하다는 점이다. 그러나 음수 간선이 사이클을 이루는 경우에는 최단 거리를 찾을 수 없기 때문에 동작하지 않는다. 벨만 포드 알고리즘은 두 경로 사이의 최단 경로를 구할 때 모든 간선을 대상으로 edge relaxation을 수행한다. edge relaxation은 두 경로 사이에 더 가까운 경로가 있다면 해당 경로의 거리로 간선을 경감하는 작업이다. 그래프에서 s, u 두 정점 사이의 최단 거리 경로는 s -> u로의 바로 연결되는 간선을 통한 경로일 수도.. [Algorithm] Dijkstra's Algorithm (다익스트라 알고리즘) 1. Dijkstra's Algorithm 다익스트라 알고리즘은 한 정점으로부터 다른 정점으로의 최단 경로를 찾는 알고리즘이다. 매반복마다 현 시점에서 가장 가까운 정점을 찾아 해당 정점에 인접한 간선들을 통해 경로를 찾아 확장해 나가는 방식이다. 그래프의 방향 유무는 상관없으나 간선이 음수 가중치를 가지는 경우에는 사용할 수 없다. 2. 다익스트라 알고리즘 구현 1) 초기에 출발점으로부터 해당 정점으로의 거리를 저장할 공간과 방문여부를 저장할 공간을 선언한다. 2) 해당 배열에서 출발점은 0, 나머지 정점은 무한대로 초기화한다. 3) 최단 거리를 저장하는 배열에서 미방문 정점 중 가장 거리가 가까운 정점을 선택한다. 4) 해당 정점을 방문한 정점으로 저장한다. 5) 선택된 정점에 간선으로 연결된 인접한.. [Algorithm] Binary Search (이진탐색) 1. Binary Search (이진탐색) 이미 정렬되어 있는 배열에서 원하는 값을 찾을 때 사용하는 탐색 방법이다. 탐색 대상이 되는 리스트의 중간값을 기준으로 반으로 나눠 반복적으로 탐색을 진행한다. 찾고자 하는 타겟값이 중간값보다 작은 경우에는 왼쪽 리스트를 중간값보다 큰 경우에는 오른쪽 리스트를 탐색 대상으로 반복 탐색을 진행한다. 만약 타겟값과 중간값이 일치하는 경우 해당 위치를 반환하면 된다. 만약에 반복을 계속해서 서브 리스트의 크기가 0일 때까지 반복한다. 2. Binary Search 구현 import java.util.Arrays; import Algorithm.Search.Search; public class BinarySearch implements Search { private i.. [Algorithm] Counting Sort (계수정렬) 1. Counting Sort 계수 정렬은 배열의 원소의 개수를 세어 정렬하는 방식의 알고리즘이다. 특정 값을 가진 원소가 몇개인지를 세어 개수를 가지고 정렬을 진행하기 때문에 특정한 범위의 값들을 원소로 가질때 적합하다. 범위가 넓은 경우에는 원소들을 계수하기 위해 할당하는 배열의 크기가 커지는 문제가 발생한다. 2. Counting Sort 구현 배열의 원소들을 각각의 값에 따라 계수하기 위해서 원소들의 개수를 저장할 임시 배열을 할당한다. 이때 임시 배열의 크기는 배열에 저장된 값의 범위에서 가장 큰 값으로 한다. 임시 배열을 생성한 후에는 기존 배열을 처음부터 끝까지 탐색하면서 해당 원소의 값을 인덱스로 가지는 임시 배열의 원소의 값을 하나씩 더해준다. 기존 배열의 탐색이 끝난 뒤에는 임시 배열을.. [Algorithm] Quick Sort (퀵정렬) 1. Quick Sort (퀵정렬) 퀵 정렬은 병합 정렬과 같은 divide and conquer 기반의 알고리즘이다. 정렬시에 한 요소를 pivot으로 지정하고 pivot을 기준으로 배열을 두 부분으로 나눈다. 이때 pivot을 선택하는 방법은 여러가지가 있다. 첫번째 요소를 pivot으로 지정한다. 마지막 요소를 pivot으로 지정한다. 랜덤하게 pivot을 지정한다. 중간에 위치한 요소를 pivot으로 지정한다. 퀵 정렬은 정렬 알고리즘 중 가장 빠른 알고리즘으로 알려져 있지만, 배열의 정렬 상태와 pivot 선택 방법에 따라 worst case에 O(N^2)의 시간 복잡도를 가질 수 있다. 퀵 정렬의 핵심은 pivot을 중심으로 partition을 나누는 과정이다. pivot으로 지정된 요소의 값.. 이전 1 2 다음