Algorithm
- Home /
- Categories /
- Algorithm
Permutation(순열)
- Algorithm
- 2021년 5월 28일
1. next_permutation c++에는 algorithm헤더에 매개변수의 배열/iterator의 다음 순열을 적용시켜 바뀌었다면 true/false를 반환해주는 메서드가 존재해서 이를 do~while문으로 쉽게 순열문제를 해결할 수 있다. 하지만, 자바는 존재하지 않기 때문에 다음과 같이 구현할 수 있다. 2. swap 구현하기가 가장 쉬워 보통 알고리즘문제에 순열이 등장할때 많이쓰는 방식중 하나로 재귀함수를 이용한 백트래킹을 이용한 방법이다....
Read More[APSP] Floyd Warshall 알고리즘
- Algorithm
- 2021년 4월 12일
벨만-포드 알고리즘과 다익스트라 알고리즘과 달리 모든 최단 경로를 구하는 알고리즘이다. (물론 두 알고리즘도 모든 정점에대해 수행하면 모든 최단 경로를 구할 수 있다.) 1. 특징 음의 가중치 허용 optimal substructure 개념 이용 배열을 이용하여 구현 밀집그래프에서 모든 edge간 경로 구할때 적합 2. Pesudo Code 3. 구현 방법 그래프 edge가 주어졌을때, edge들의 정보를 이용하여 각 edge간 거리 정보를 저장할 distance 2차원 행렬과 경로를 구하기 위해 이전 노드를 저장할 previous 2차원 행렬 생성 distance 행렬은 Infinity로 previous 행렬은 NIL(-1)로 초기화 그래프 G의 edge들의 가중치의 정보를 이용해 distance행렬을 초기화하고 자기의 거리는 0으로 초기화 3중 반복문을 이용하여, 현재까지 계산된 i - j까지의 경로 값보다 사이에 k를 경유하는 경로 값이 더 작다면 값을 바꾸기 4. 시간복잡도 매번 모든 노드들의 조합에 대해서 현재까지의 최단 경로를 구하고 총 |V-1| 번 반복하기 때문에 O(|V|^3) 의 시간복잡도를 갖는다....
Read More[MST] Prim 알고리즘
- Algorithm
- 2021년 4월 12일
우선순위 큐의 방법을 이용하는 알고리즘으로 vertex를 한개씩 선택하며 최소 비용의 edge를 찾는 방법이다. decrease-key의 개념을 이용하며 decrease-key는 현재 계산된 v노드까지의 거리보다 현재 노드 u부터 v까지의 경로가 더 작다면 값을 갱신해주는 방법을 이용한다. 1. 특징 정점 선택 기반 시작 정점부터 출발하여 해당 노드까지의 최소 비용을 기록하는 배열을 이용하여 구하는 방식 자료구조중 하나인 우선순위 큐를 이용하며, 우선순위 큐를 어떻게 구현했는가가 시간복잡도에 영향 2. Pesudo Code 3. 구현 방법 vertex들의 key값을 Infinity로 초기화 start vertex의 key값을 0으로 초기화 (어떤 vertex를 선택하더라고 MST가 나온다.) 현재 vertex에 인접한 vertex들 중 선택하지 않았고, 가장 vertex의 key값이 작은 vertex을 찾기 (exract-min = 최소값 추출) 현재 vertex를 선택 인접한 vertex중 vertex의 key값보다 간선의 가중치가 더 작다면 key값을 가중치로 갱신 (decrease -key) 인접한 vertex중 선택하지 않았고, 가장 vertex의 key값이 작은 vertex를 기준으로 3번부터 다시 반복 모든 vertex가 선택되었다면 종료 1) 인접 행렬 위에 설명한 3번 방법의 extract-min을 아래와 같이 배열로 구현하며, 매번 V회 반복한다....
Read More[Disjoint Set] Union Find 알고리즘
- Algorithm
- 2021년 4월 12일
1. Disjoint Set 번역하면 서로소 집합으로 서로 중복 되지 않는 부분 집합들로 이루어진 집합(set)으로 교집합이 존재 하지 않는 부분집합들로 이루어진 집합이다. 2. Union-Find Union : 두개의 집합을 하나의 집합으로 합치는 것. Find : 어떤 원소가 주어졌을 때 이 원소가 속한 집합을 반환하는(찾는) 것. 집합들을 tree구조로 나타내어 해당원소가 어떤 집합에 속하는지 판단할때 각 집합의 대표값(root)을 이용해서 집합이 같은지를 비교....
Read More[MST] Kruskal 알고리즘
- Algorithm
- 2021년 4월 12일
그래프 중에서 MST (Minumum Spannig Tree) 를 찾는 알고리즘중에 하나로 Union-Find알고리즘을 이용하며, 간선 (edge)의 가중치(weight)를 오름차순으로 정렬하여 가중치가 사이클이 생기지 않는 낮은 간선을 먼저 선택하는 방법이다. 사이클의 여부를 확인할때 union-find 알고리즘을 이용하여 찾는 알고리즘이다. union find 알고리즘 설명 보기 1. 특징 탐욕적인 방법 (Greedy) 간선 선택 기반 알고리즘 간선 선택 단계에서 사이클을 포함하지 않고 최소 비용 간선을 선택 부분 트리집합을 병합하면서 하나의 트리로 확장 희소그래프에 적합 ( V > E ) 정렬 속도가 시간복잡도에 영향 2. Pesudo Code 3. 구현 Note...
Read More[SPSP] Dijkstra 알고리즘
- Algorithm
- 2021년 4월 12일
그래프 중에서 최단 경로를 찾는 알고리즘중에 하나로 하나의 정점에서 다른 모든 정점까지의 최단경로를 구하는 알고리즘 (single-source shortest path algorithmm)으로 우선순위 큐의 방법을 이용하는 알고리즘이다. 가장 최적의 vertex를 한개씩 선택하며 최단 경로를 찾는 방법으로 relax의 개념을 이용하며 relax는 현재 계산된 v노드까지의 거리보다 현재 노드 u까지의 경로와 u에서 v의 가중치 ( e(u,v) ) 가 더 작다면 값을 갱신해준다....
Read More[SPSP] Bellman Ford 알고리즘
- Algorithm
- 2021년 4월 12일
그래프 중에서 최단 경로를 찾는 알고리즘중에 하나로 하나의 정점에서 다른 모든 정점까지의 최단경로를 구하는 알고리즘 (single-source shortest path algorithmm)으로 음의 가중치도 계산 할수 있는 알고리즘이다. Vertex의 개수가 N개일 때, 한 vertex에서 다른 vertex까지 가는데 거치는 edge수는 최소 1개부터 최대 N-1번 거치게 된다. 이때, relax의 개념을 이용하며 relax는 현재 계산된 v노드까지의 거리보다 현재 노드 u까지의 경로와 u에서 v의 가중치 (e(u,v)) 가 더 작다면 값을 갱신해주는 것이다....
Read MoreTopological Sort (위상 정렬)
- Algorithm
- 2021년 4월 12일
조건 : 방향이 있고 사이클이 없는 그래프 (Directed Acyclic Graph) DAG일때, 방향성을 거스르지 않고 나열하는 것으로 순서가 있는 작업을 차례로 수행해야할때 순서를 결정해주기 위해 사용하는 알고리즘이다. 대학 커리큘럼의 선수과목이나 엄무의 일정을 시간 순서대로 배치한것이 그 예 이다. 1. 특징 방향이 있는 그래프이어야 한다. (directed) 사이클이 없어야 한다. (Acyclic) 2. Pesudo Code 1) InDegree 이용방법 2) dfs 이용방법 3. 구현 방법 1) InDegree 이용 모든 vertex에 대해 InDegree값을 초기화 진입 차수 (indegree)가 0인 값을 큐에 삽입 큐에서 1개 vertex, v를 pop v를 stack에 쌓기 (정렬한 값을 담는 것이 stack) v에 연결된 vertex들의 indegree값을 1감소 진입 차수가 0인 정점들을 큐에 삽입 3-6번을 Vertex수만큼 반복 만약에 큐가 비어있다면, 사이클이 존재하는 그래프 (큐가 비어있다면 indegree가 0인 값이 없었다는 소리. 즉, 사이클 발생) 2) dfs 이용 방문하지 않은 vertex들을 dfs함수 진행. dfs 해당 vertex 방문표시 인접 vertex에 대해 방문하지 않았다면 dfs함수 진행 dfs함수 종료시 stack에 push 4. 시간 복잡도 indegree방법은 초기화하는데 O(V), 큐에 삽입, 제거 하는게 O(V)번씩 소요되며, indegree를 1감소 시켜주는게 O(E)번 일어난다. (indegree를 1감소해주는건 edge를 삭제해주는거와 같기 때문) 따라서, O(V+E)의 시간복잡도를 갖는다....
Read MoreCounting Sort ( 계수 정렬 )
- Algorithm
- 2020년 10월 13일
계수 정렬은 삽입, 버블, 선택, 퀵, 합병 정렬들과 같이 비교를 수행하는 방식이 아닌 비교를 하지 않는 Non-Comparisions Sorting Algorithm 이다. 그러면 여기서 값을 정렬하는데 어떻게 비교 없이 수행하나요? 와 같은 질문이 있을 텐데, 계수 정렬은 비교 대신 정렬할 수의 개수와 배열의 인덱스를 가지고 정렬을 수행하게 된다. 1. 기본적인 흐름 2 1 2 4 5 3 6 5 3 을 정렬하고자 한다면 1의 개수는 1개, 2의 개수는 2개, 3의 개수는 2개, 4의 개수는 1개, 5의 개수는 2개, 6의 개수는 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^2) O(n^2) 트리 정렬 Ω(nlogn) Θ(nlogn) O(n^2) 퀵 정렬 Ω(nlogn) Θ(nlogn) O(n^2) 셸 정렬 Ω(n) Θ(n^1.5) O(n^1.5) 힙 정렬 Ω(nlogn) Θ(nlogn) O(nlogn) 합병 정렬 Ω(nlogn) Θ(nlogn) O(nlogn) 큐브 정렬 Ω(n) Θ(nlogn) O(nlogn) 팀 정렬 Ω(n) Θ(nlogn) O(nlogn) 기수 정렬 Ω(nk) Θ(nk) O(nk) 계수 정렬 Ω(n+k) Θ(n+k) O(n+k) 3. 공간 복잡도 ( Big-O ) 알고리즘 최악 선택 정렬 O(1) 버블 정렬 O(1) 삽입 정렬 O(1) 셸 정렬 O(1) 힙 정렬 O(1) 퀵 정렬 O(logn) 합병 정렬 O(n) 큐브 정렬 O(n) 트리 정렬 O(n) 팀 정렬 O(n) 계수 정렬 O(k) 기수 정렬 O(n+k) 4. 정렬의 특성 1) 안정 정렬( stable sort ) 정렬되지 않은 상태의 같은 키값을 가진 원소의 순서가 정렬 후에도 유지 되는 정렬 상황에 따라서 객체나 키값이 여러개인 값들을 정렬 하려고 할때 원래의 순서가 바뀌게 되면 안될 수 있기 때문에 그때는 stable한 sort를 이용해야 한다. Bubble, Insertion, Merge, Counting, Bucket, Radix Sort가 해당된다. Note...
Read More