Algorithm
- Home /
- Categories /
- Algorithm
Permutation(순열)
- Algorithm
- 2021년 5월 28일
1. next_permutation c++에는 algorithm헤더에 매개변수의 배열/iterator의 다음 순열을 적용시켜 바뀌었다면 true/false를 반환해주는 메서드가 존재해서 이를 do~while문으로 쉽게 순열문제를 해결할 수 있다. 하지만, 자바는 존재하지 않기 때문에 다음과 같이 구현할 수 있다. public boolean next_permutation(int[] arr){ //뒤에서부터 탐색해서 내림차순이 깨...
Read More[APSP] Floyd Warshall 알고리즘
- Algorithm
- 2021년 4월 12일
벨만-포드 알고리즘과 다익스트라 알고리즘과 달리 모든 최단 경로를 구하는 알고리즘이다. (물론 두 알고리즘도 모든 정점에대해 수행하면 모든 최단 경로를 구할 수 있다.) 1. 특징 음의 가중치 허용 optimal substructure 개념 이용 배열을 이용하여 구현 밀집그래프에서 모든 edge간 경로 구할때 적합 2. Pesudo Code let dist be a |V| × |V| array of minimum distances initialized to ∞ let p be a |V| × |V| array of previous node initialized to null...
Read More[MST] Prim 알고리즘
- Algorithm
- 2021년 4월 12일
우선순위 큐의 방법을 이용하는 알고리즘으로 vertex를 한개씩 선택하며 최소 비용의 edge를 찾는 방법이다. decrease-key의 개념을 이용하며 decrease-key는 현재 계산된 v노드까지의 거리보다 현재 노드 u부터 v까지의 경로가 더 작다면 값을 갱신해주는 방법을 이용한다. 1. 특징 정점 선택 기반 시작 정점부터 출발하여...
Read More[Disjoint Set] Union Find 알고리즘
- Algorithm
- 2021년 4월 12일
1. Disjoint Set 번역하면 서로소 집합으로 서로 중복 되지 않는 부분 집합들로 이루어진 집합(set)으로 교집합이 존재 하지 않는 부분집합들로 이루어진 집합이다. 2. Union-Find Union : 두개의 집합을 하나의 집합으로 합치는 것. Find : 어떤 원소가 주어졌을 때 이 원소가 속한 집합을 반환하는(찾는) 것. 집합들을 tree구조로 나타내어 해당원소가 어떤 집합에 속하는지 판단...
Read More[MST] Kruskal 알고리즘
- Algorithm
- 2021년 4월 12일
그래프 중에서 MST (Minumum Spannig Tree) 를 찾는 알고리즘중에 하나로 Union-Find알고리즘을 이용하며, 간선 (edge)의 가중치(weight)를 오름차순으로 정렬하여 가중치가 사이클이 생기지 않는 낮은 간선을 먼저 선택하는 방법이다. 사이클의 여부를 확인할때 union-find 알고리즘을 이용하여 찾는 알고리즘이다. union find 알고리즘 설명 보기 1. 특징 탐욕적인 방...
Read More[SPSP] Dijkstra 알고리즘
- Algorithm
- 2021년 4월 12일
그래프 중에서 최단 경로를 찾는 알고리즘중에 하나로 하나의 정점에서 다른 모든 정점까지의 최단경로를 구하는 알고리즘 (single-source shortest path algorithmm)으로 우선순위 큐의 방법을 이용하는 알고리즘이다. 가장 최적의 vertex를 한개씩 선택하며 최단 경로를 찾는 방법으로 relax의 개념을 이용하며 relax는 현재 계산된 v노드까지의 거리보다...
Read More[SPSP] Bellman Ford 알고리즘
- Algorithm
- 2021년 4월 12일
그래프 중에서 최단 경로를 찾는 알고리즘중에 하나로 하나의 정점에서 다른 모든 정점까지의 최단경로를 구하는 알고리즘 (single-source shortest path algorithmm)으로 음의 가중치도 계산 할수 있는 알고리즘이다. Vertex의 개수가 N개일 때, 한 vertex에서 다른 vertex까지 가는데 거치는 edge수는 최소 1개부터 최대 N-1번 거치게 된다. 이...
Read MoreTopological Sort (위상 정렬)
- Algorithm
- 2021년 4월 12일
조건 : 방향이 있고 사이클이 없는 그래프 (Directed Acyclic Graph) DAG일때, 방향성을 거스르지 않고 나열하는 것으로 순서가 있는 작업을 차례로 수행해야할때 순서를 결정해주기 위해 사용하는 알고리즘이다. 대학 커리큘럼의 선수과목이나 엄무의 일정을 시간 순서대로 배치한것이 그 예 이다. 1. 특징 방향이 있는 그래프이어야 한다. (directed) 사이클이 없어야 한다. (Acyclic) 2. Pesudo Code 1) InDegree...
Read MoreCounting Sort ( 계수 정렬 )
- Algorithm
- 2020년 10월 13일
계수 정렬은 삽입, 버블, 선택, 퀵, 합병 정렬들과 같이 비교를 수행하는 방식이 아닌 비교를 하지 않는 Non-Comparisions Sorting Algorithm 이다. 그러면 여기서 값을 정렬하는데 어떻게 비교 없이 수행하나요? 와 같은 질문이 있을 텐데, 계수 정렬은 비교 대신 정렬할 수의 개수와 배열의 인덱스를 가지고 정렬을 수행하게 된다. 1. 기본적인 흐름 2 1 2 4 5 3 6 5 3 을 정렬하고자 한다면 1의...
Read MoreSorting Algorithm
- Algorithm
- 2020년 9월 20일
1. 종류 선택 정렬 ( Selection Sort ) 삽입 정렬 ( Insertion Sort ) 버블 정렬 ( Bubble Sort ) 셸 정렬 ( Shell Sort ) 퀵 정렬 ( Quick Sort ) 힙 정렬 ( Heap Sort ) 합병 정렬 ( Merge Sort ) 기수 정렬 ( Radix Sort ) 계수(카운트) 정렬 ( Count Sort ) 트리 정렬 큐브 정렬 팀 정렬 2. 시간 복잡도 ( Big-O ) 알고리즘 최선 평균 최악 선택 정렬 Ω(n^2) Θ(n^2) O(n^2) 버블 정렬 Ω(n) Θ(n^2) O(n^2) 삽입 정렬 Ω(n) Θ(n...
Read More