알고리즘/개념24 최단 경로 알고리즘 - 플로이드 워셜(Floyd-Warshall) 플로이드 워셜 알고리즘이란? 모든 노드 간의 최단 경로를 구하는 알고리즘 벨만 포드 알고리즘과 동일하게 음수 간선이 있어도 최단 경로를 구할 수 있습니다. 음수 사이클이 존재할 때는 사용하지 못합니다. 알고리즘 복잡도 : O(V^3) 모든 경로를 구하다보니 V * V(노드 수,Vertex) 만큼의 메모리가 필요합니다. 플로이드 워셜 알고리즘 흐름 요약 임의의 노드 s에서 e까지 가는 데 걸리는 최단거리를 구하기 위해, s와 e 사이의 노드인 m에 대해 s에서 m까지 가는 데 걸리는 최단거리와 m에서 e까지 가는 데 걸리는 최단거리를 이용합니다. 우선 모든 노드들을 돌면서 최단경로 메모리에 직접적으로 연결되어있는 노드라면 가중치를, 아니라면 INF로 초기화합니다. 쉽게 말해서 모든 노드돌면서 연결된 인접한.. 2022. 6. 1. 다이나믹 프로그래밍 (DP,Dynamic Programming) 1. 다이나믹 프로그래밍이란? = 동적 계획법 큰 문제를 부분 문제로 나눈 후 문제를 해결하는 과정에서 나오는 계산된 결과를 기록하여 재활용하는 방법 한번 계산한 부분을 다시 계산하지 않기 때문에 속도가 빠르다 계산된 결과를 저장하기 위한 메모리가 필요하다 2. 다른 알고리즘과의 차이점 분할 정복 분할 정복은 부분 문제가 중복되지 않는다 DP는 부분 문제가 중복된다 분할 정복에서는 DP 사용불가 그리디 알고리즘 그리디 알고리즘은 근사치를 구하는 방식 DP는 모든 방법을 확인 후 최적해 구하는 방식 둘 다 적용이 가능하다면 그리디 알고리즘이 더 빠름 3. 다이나믹 프로그래밍 예시 피보나치 피보나치 같은 경우 아래의 그림과 같이 계산할 때 중복이 발생한다. 이를 처음 계산할 때 따로 저장해둔다면 계산을 여러.. 2022. 5. 29. 최단 경로 알고리즘 - 벨만-포드 (Bellman-Ford) 벨만-포드 알고리즘이란? 하나의 정점에서 모든 정점으로 가는 최단 거리를 구할 수 있습니다. 다익스트라와 달리 음수 간선이 포함되어 있어도 최단 경로를 구할 수 있습니다. 다만, 음수 사이클이 있을 땐 사용 X 매번 모든 간선을 확인하기 때문에 다익스트라에 비해 느립니다. 알고리즘 복잡도 : O(VE) 벨만-포드 알고리즘 흐름 1. 정점의 숫자만큼 모든 간선을 체크한다. (정점 * 간선 , VE) distance가 무한대인 경우, 뽑힌 변의 가중치를 더해봤자 무한대이기 때문에 continue 처리한다. 1의 노드에서 5의 노드로 가는 경우, 1의 최단 경로 값이 0이기 때문에 5번 노드로 가는 가중치 5를 더해준다. 위의 작업을 정점 별로 모든 간선을 체크해나가다보면 distance가 갱신된다. 2. 음.. 2022. 5. 11. 최단 경로 알고리즘 - 다익스트라 최단 경로 알고리즘이란? 가중 그래프 상의 두 노드를 연결하는 가장 짧은 경로를 찾는 방법 지도 경로 탐색, 네트워크 구축에 드는 비용을 최소화 하는데 사용 최단 경로 알고리즘 종류 다익스트라 벨만-포드 플로이드-워셜 다익스트라 알고리즘 (Dijkstra Algorithm) 출발점에서 목표점까지의 최단 경로를 구하는 알고리즘 한 노드에서 다른 모든 노드로의 최단 경로를 구할 수 있음 간선에 음의 가중치가 없어야 함. 하나라도 음의 가중치가 있다면 다익스트라 알고리즘을 사용할 수 없다. 그리디 + DP 형태 알고리즘 복잡도 : O(ElogV) * E = Edge , V = Vertex 다익스트라 알고리즘 흐름 1. 출발점으로부터의 최단경로를 저장할 노드만큼의 크기를 가진 배열을 만들고, 출발 노드에는 0을.. 2022. 5. 11. 최소 신장 트리 (MST) 최소 신장 트리 (MST, Minimum Spanning Tree) 란? 그래프 상의 모든 노드들을 최소 비용으로 연결하는 방법 종류 크루스칼 (Kruskal) 간선 중 최소 값을 가진 간선부터 순차적으로 연결 사이클 발생 시 다른 간선을 선택 사이클 발생 여부는 Union-Find를 통해서 체크 주로 간선 수가 적을 때 사용 시간복잡도 : O(ElogE) import java.util.Arrays; import java.util.Comparator; public class Kruskal { // Union-Find를 위한 배열 static int[] parents; public static int kruskal(int[][] data, int v, int e) { int weightSum = 0; //.. 2022. 5. 11. 그리디 알고리즘 (Greedy Algorithm) 그리디 알고리즘이란? 매 순간 현재의 기준으로 최선의 답을 선택해나가는 기법 빠르게 근사치를 계산할 수 있지만 결과적으로는 최적해가 아닐 수 있다. 그리디 알고리즘 적용 조건 탐욕적 선택 특성 (Greedy Choice Property) 지금 선택이 다음 선택에 영향을 주지 않을 경우 최적 부분 구조 (Optimal Substructure) 전체 문제의 최적해는 부분 문제의 최적해로 이루어짐 그리디 알고리즘 예제 Activity Selection Problem import java.util.ArrayList; import java.util.Collections; class Activity { String name; int start; int end; public Activity(String name, i.. 2022. 5. 10. Binary Search (이진 탐색) import java.util.Arrays; /** * Binary Search (이진 탐색) * 정렬된 상태의 데이터에서 특정 값을 빠르게 탐색하는 방법 * 찾고자 하는 값과 데이터 중앙에 있는 값을 비교 * - 찾고자 하는 값이 더 작으면 데이터 왼쪽 부분에서 이진 탐색 * - 찾고자 하는 값이 더 크면 데이터 오른쪽 부분에서 이진 탐색 * 시간 복잡도 : O(logn) * * 자바에서 기본적으로 제공하는 BT가 있다. Arrays.binarySearch(); */ public class BinarySearch { // 반복문 사용 public static int binarySearch(int[] arr, int target) { int left = 0; int right = arr.length - .. 2022. 4. 30. 정렬 알고리즘별 복잡도 정리 2022. 4. 30. Shell Sort (셸 정렬) /** * Shell Sort(셸 정렬) * - 삽입정렬은 오름차순 정렬 기준으로 내림차순으로 이미 정렬되어 구성된 데이터에 대해서는 * - 앞의 데이터와 하나씩 비교하며 모두 교환해야한다. * - 이러한 약점을 보완하는 방식이 Shell sort * - 이전의 모든 데이터와 비교하지 않고 일정 간격을 두어 비교 * - 간격 설정에 따라 worst case가 O(n^2) 지만 일반적인 산포 데이터 기준으로는 삽입 정렬에 비해 빠르다. */ public class ShellSort { public static void shellSort(int[] arr) { // 보통 간격은 배열 길이의 절반으로 시작함. int gap = arr.length / 2; // 절반씩 줄여나가면서 진행 for (int g = .. 2022. 4. 30. Counting Sort (계수 정렬) import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.HashMap; /** * Counting Sort(계수 정렬) * - 숫자끼리 비교하지 않고 카운트를 세서 정렬하는 방식 * - 카운팅을 위한 카운팅 테이블이 필요 * - Un-Stable sort * - 시간 복잡도 = O(n+k) (k는 정렬 대상 데이터 중 최대 값) * - * - [1,3,2,4,5] 이런 배열처럼 수의 분포가 좁다면 배열을 이용하는게 좋고 * - [1,24005,4,3] 이런식으로 수 자체는 적은데 수의 분포가 넓다면 해시맵을 이용하는게 좋다. */ public class CountingSort { /.. 2022. 4. 30. Radix Sort (기수정렬) 가장 작은 자릿수부터 정렬해나가다보면 결국에는 정렬이 되는 신기한 기수정렬 1의 자리 -> 10의 자리 -> 10의 자리 -> ,,,, 순으로 정렬을 해나가다보면 정렬이 되어있다. - 첫번째 자리수로 정렬(1의 자리) - 두번째 자리수로 정렬(10의자리) import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; /** * Radix Sort(기수 정렬) * - 낮은 자리 수부터 정렬하는 방식(1의자리 -> 10의자리 -> 100의자리) * - 각 원소 간의 비교 연산을 하지 않아 빠르지만, 기수 테이블을 위한 메모리가 필요하다. * - 시간 복잡도 = O(dn) (d는 최대자릿수) * - Stable sort * - .. 2022. 4. 30. Heap Sort (힙 정렬) /** * Heap Sort(힙 정렬) * - Heap 자료구조 기반 정렬 방식 * * - 이진 tree 자료구조 성질 이용 (0번 인덱스부터 시작한다는 기준) * - 1. 왼쪽 자식 노드 인덱스 = 부모 노드 인덱스 × 2 + 1 * - 2. 오른쪽 자식 노드 인덱스 = 부모 노드 인덱스 × 2 + 2 * - 3. 부모 노드 인덱스 = (자식 노드 인덱스 - 1) / 2 * - * - 장점 * - 부분 정렬을 할 때 효과적 * - 최악의 경우에도 시간 복잡도 = O(nlogn) * - * - 단점 * - 일반적인 O(nlogn) 정렬 알고리즘에 비해 성능이 조금 떨어진다. * - Stable sort 가 아니다. */ public class HeapSort { public static void heap.. 2022. 4. 30. Merge Sort(합병 정렬, 2-ways 합병 정렬) /** Merge Sort(합병정렬) - 배열을 절반으로 계속 분할해서 길이가 1이 되도록 만들고, 인접한 부분끼리 정렬하면서 합병하는 방식 (Divide & Conquer) - 장점 - 동일한 값의 경우, 들어온 순서대로 정렬되므로 Stable Sort 이다. - 최악의 경우에도 시간 복잡도 = O(nlogn) - 단점 - 추가적인 배열이 필요하므로 in-place Sort가 아니기 때문에 메모리 사용량이 많다. - 원본 배열에 추가적인 배열의 값을 복사하는 과정이 많은 시간을 소비하기 때문에 데이터가 많을 경우 시간이 많이 소요된다. */ public class MergeSort { public static void mergeSort(int[] arr, int[] tmp, int left, int r.. 2022. 4. 29. 빅오 표기별 커버 가능한 크기 알고리즘 별로 시간복잡도가 있는데 이 복잡도 별로 어느정도의 데이터량을 처리할 수 있는지 대략적으로 적어둔 것 이다! O(NlogN) -> 100,000 정도 O(N^2) -> 1,000 O(2^N) -> 100 이것보다 적은 시간복잡도는 언제써도 어느정도는 괜찮다고 한다. 2022. 4. 26. 이진 탐색 트리 (BST,Binary Search Tree) 규칙 왼쪽 자식 노드 한쪽으로 편향되어 있는 경우 In-order 순회를 하면 오름차순으로 된다. 탐색 (Search) 찾고자 하는 데이터를 root 노드부터 대소 비교 데이터가 작으면 왼쪽 이동 데이터가 크면 오른쪽 이동 찾는 데이터가 없으면 null 반환 어떤 데이터를 찾더라도 최대 트리의 높이 만큼의 탐색이 이루어짐 삽입 (Insert) 균형 고려하지 않을 시 삽입할 데이터를 root 노드부터 비교 (search와 동일) leaf 노드에 도달.. 2022. 4. 25. 이전 1 2 다음
