반응형 Algorithm16 Counting Sort & Radix Sort Counting Sort & Radix Sort (기수 정렬) - element 값을 명시적으로 비교하지 않아도 정렬할 수 있는 기법 Comparison sort = 두 개 요소 값을 반복적으로 비교하여 정렬을 수행하는 알고리즘. (Decision tree 모델 이라고도 불림) ● Counting Sort counting sort로 1,3,2,4,3을 정렬하면 count[1] = 1; count[2] = 1; count[3] = 2; count[4] = 1; 해당 개수만큼 순서대로 써주면 됨. -> 이 방식은 stable sorting이 불가능. (stable sorting = 처음 가진 순서를 유지한 상태로 정렬을 하는 방식을 말함. 같은 값을 가졌다고 해서 순서를 마음대로 배치시키는 것이 아니라 원래.. 2022. 6. 28. Algorithm - Network Flow, Edmonds-Karp Network Flow(네트워크 플로우)란? 특정한 지점에서 다른 지점으로 데이터가 얼마나 많이 흐르고 있는가를 측정하는 알고리즘. / 한 정점에서 다른 정점까지 흐를 수 있는 데이터의 최대 크기가 어느정도 인지를 확인하는 알고리즘. (얼마나 많은 유량(Flow)를 보낼 수 있는지를 계산/ 이러한 알고리즘은 교통 체증, 네트워크 전송, 전자 회로의 전류, 배수관을 흐르는 유체, 유량구하기 등의 다양한 분야에서 활용됨. / 유향 그래프에서 각 간선은 데이터가 흐를 수 있는 정해진 용량으로 제한되어 있으며 이를 최대한의 양으로 얼마나 흐르게 할 수 있는지를 확인함. -> 최대 유량 문제(Max Flow)로 정의하며 해결하기 위한 알고리즘으로 에드몬드 카프 알고리즘(Edmonds-Karp)를 적용함. - 유량.. 2022. 6. 22. Algorithm - Topological Sort(위상 정렬) Topological Sort : 어떤 일을 하는 순서를 찾기 위한 알고리즘. / 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것. / '순서가 정해져 있는 작업'을 차례로 수행해야 할때, 그 순서를 결정해 주기 위해 사용하는 알고리즘. 위상 정렬은 여러 개의 답이 존재할 수 있음. 또한 위상 정렬은 DAG(Directed Acyclic Graph)에만 적용이 가능함. -> 사이클이 발생하지 않는 방향 그래프. 사이클이 발생하는 경우 위상 정렬은 수행 불가. Topological Sort 의 특징 : 하나의 방향 그래프에는 여러 위상 정렬이 가능. / 위상 정렬의 과정에서 선택되는 정점의 순서를 위상 순서(Topological Order)라 함. / 위상 정렬의.. 2022. 6. 12. Algorithm - Hashing(해싱 알고리즘) Hash? - 해시에는 크게 Hash, Hash function, Hashing, Hash table 이렇게 네가지로 나뉘어짐. ㆍHash : 해시는 데이터를 다루는 기법 중의 하나로 검색과 저장을 아주 빠르게 하는 자료구조이다. 데이터를 저장할때 Key, Value 형태로 데이터가 존재하고, Key값이 배열의 인덱스로 저장되기 때문에 검색과 저장을 빠르게 할 수 있음. ㆍHash function과 Hashing Hash function은 Key값을 고정된 길이의 hash로 변환하는 역할을 함. Hash function에서 Key값을 hash로 변환하는 과정을 hashing이라고 한다. Hash function에서는 Key값을 해싱 과정을 통해 Hash value(해시 값) 또는 Hash code로 변경.. 2022. 5. 21. Algorithm - Dijkstra(다익스트라) 알고리즘 Dijkstra Algorithm : Dynamic programming을 이용한 대표적인 최단경로(Shortest path) 탐색 알고리즘. 다익스트라 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려줌. 이 때 음의 Edge는 포함할 수 없음(현실 세계에선 음의 Edge가 존재 하지 않기 때문에 다익스트라는 현실에서 사용하기 매우 적합함). / 음의 가중치가 없는 그래프의 한 정점(vertex)에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘 / 에츠허르 다익스트라 라는 사람이 고안한 알고리즘이라함. / 그래프 방향의 유무는 상관없으나 간선(Edge)들 중 단 하나라도 가중치가 음수이면 이 알고리즘은 사용할 수 없음. 음의 가중치를 가지는 간선이 있으며 가중치 합이 음인.. 2022. 5. 7. Algorithm - Backtracking(백트래킹) Backtracking : 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾는 기법. 최적화 문제와 결정 문제를 푸는 방법이 된다. / 가능한 모든 방법을 탐색한다라는 성격을 가짐. / 모든 경우의 수를 전부 고려하는 알고리즘. 상태 공간을 트리로 나타낼 수 있을때 적합한 방식(일종의 트리 탐색 알고리즘). 방식에 따라서 DFS, BFS, 최선 우선 탐색 등이 있다. DFS가 일반적. / 현재 상태에서 가능한 모든 후보군을 따라 들어가며 해결책에 대한 후보를 구축해 나아가다 가능성이 없다고 판단되면, 즉시 후보를 포기하면서 정답을 찾아가는 범용적인 알고리즘. DFS와 Backtracking : DFS - DFS의 장점은 무한히 깊은곳을 찾아야 할때 효과적이고 단점은 모든곳을 방문하기 때문에.. 2022. 5. 4. 이전 1 2 3 다음 반응형