알고리즘(29)
-
[알고리즘] 탐색(1) - 완전탐색(Brute-force)
개념 완전탐색은 알고리즘에 입문하는 사람들이 가장 처음으로 접하는 내용일것입니다. 그만큼 어려운 내용은 아니며, 말 그대로 완전히 탐색하는 것입니다. 영어로는 brute-force라고 하는데, 이것을 번역해보면 "무식하게 풀기"라는 뜻입니다. 구현 완전탐색을 할 때 사용되어지는 방식은 크게 두가지로 볼 수 있습니다. 1. Iterative 2. recursion 1번은 for문을 이용한 풀이 이고 2번은 재귀 호출을 이용하여 푸는 방법입니다. 예를 들어, 1부터 n까지의 합을 구하는 코드를 구성해보겠습니다. // iterator // 조건 : n >=1 // 1~n의 합을 반환한다. int sum(int n) { int ret = 0; for (int i = 1; i < n; ++i) ret += i; ..
2020.04.10 -
[알고리즘] 그래프 (5) - 다익스트라 알고리즘 (Dijkstra's Algorithm)
목차 1. Dijkstra 알고리즘의 개념 2. Dijkstra 알고리즘의 구현 정의 Dijkstra 알고리즘은 방향 혹은 무방향 그래프에서 임의의 시작점으로부터 다른 모든 정점까지 최단거리를 구해주는 알고리즘 입니다. Dijkstra 알고리즘을 사용하기 위해서는 한 가지 전제조건이 필요한데, 그래프의 어떠한 가중치도 음의 값을 포함하고 있으면 안됩니다. 개념 Dijkstra 알고리즘의 동작 방식에 대해 알아보겠습니다. Dijkstra 알고리즘을 수행하기에 앞서 임의의 시작점으로 하여금 자기 자신을 제외한 모든 정점까지의 거리를 무한대 값으로 초기화합니다. 1. 아직 방문하지 않은 정점들 중 거리가 가장 짧은 정점 하나를 선택하여 방문합니다. 2. 해당 정점에서 인접하고 아직 방문하지 않은 정점들의 거리..
2020.04.10 -
[알고리즘] 정렬(6) - 퀵 정렬(Quick Sort)
원리 1. 배열 리스트 중 하나를 선택한다. 이 원소를 피벗이라고 함. 2. 피벗을 기준으로 피벗 앞에는 피벗보다 작은 모든 원소들이 오고 피벗 뒤에는 피벗보다 큰 원소가 옴 3. 분할 : 리스틀 피벗을 기준으로 두 리스트로 나눈다. 4. 분할된 리스트들에서 1-3번 과정을 반복한다. 위와 같은 과정을 반복한다면 매번 분할시 피벗으로 한 원소의 위치를 정할 수 있으므로 모든 수를 정렬할 수 있는 것은 자명합니다. 앞서 포스팅한 병합정렬에서와 마찬가지로 분할 정복(Divide and conquer)을 이해하고 있어야합니다. 분할 정복을 모른다면 공부하고 읽는 것을 권장드립니다. 하지만 포스트를 통해서 이해는 할 수 있습니다. [ 16, 11, 6, 19, 12, 2, 2, 10 ] pivot값은 맨앞의 값..
2020.04.10 -
[알고리즘] 그래프(4) - 최소신장트리 MST (2)
목차 1. Prim 알고리즘의 개념 2. Prim 알고리즘의 구현 3. Kruskal 알고리즘과 Prim 알고리즘의 비교 이전 포스팅에서는 최소 신장 트리를 만들기 위한 알고리즘으로 Kruskal 알고리즘에 대하여 알아보았습니다. 이번 포스팅에서는 최소 신장 트리를 구현하는 또 다른 알고리즘인 Prim 알고리즘에 대해 알아보도록 하겠습니다. Prim 알고리즘은 Union-Find 와 같은 알고리즘을 몰라도 구현할 수 있습니다. 하지만 구현이 Kruskal 알고리즘에 비해 복잡합니다. 개념 Prim 알고리즘은 다음과 같은 방법으로 동작을 수행합니다. 임의의 정점을 선택하여 최소 신장 트리에 추가합니다. 최소 신장 트리에 포함된 정점과 연결된 정점들 중에서 아직 최소 신장 트리에 포함되지 않고 간선의 가중치..
2020.04.09 -
[알고리즘] 정렬(5) - 병합 정렬(Merge Sort)
원리 1. 정렬할 배열을 사이즈가 1이 될때까지 반으로 나눈다. (분할) 2. 나눌 수 없을때까지 나눈뒤 정렬을 한다. (정복) 3. 정렬 한 결과를 병합한다. (병합) [ 16, 11, 6, 19, 12, 2, 2, 10 ] 정렬하기에 앞서 분할 정복(Divide and conquer)을 이해하고 있어야합니다. 모르더라도 이번 기회에 직접 이해해 보도록 하겠습니다. 분할은 배열을 절반씩 나누어서 사이즈가 1이 될때까지 나눈 것입니다. 그리고 정렬을 하고 병합을 하는 식으로 구성되어있습니다. 방식은 쉽게 이해하실 수 있습니다. 그렇다면 왜 굳이 분할을 해서 다시 합치면서 정렬을 해야할까요? 이는 아래 시간복잡도를 알아보면서 이해해보도록 하겠습니다. 구현 template vector MergeSort(co..
2020.04.09 -
[알고리즘] 그래프(3) - 최소신장트리 MST (1)
목차 1. 최소 신장 트리의 정의 2. Kruskal 알고리즘의 개념 3. Kruskal 알고리즘 구현 정의 최소 신장 트리 (Minimum Spanning Tree)에 대해 알아보기 전에 우선 신장 트리가 무엇인지 알아보겠습니다. 신장 트리(Spanning Tree)는 무방향 연결 그래프가 존재할 때, 그 그래프에서 모든 정점을 포함하도록 간선을 부분적으로 선택하여 만들 수 있는 부분 그래프 입니다. 어떤 그래프가 정점 V개와 E개의 간선을 가지고 있다고 가정하면 신장 트리의 정점과 간선의 개수는 각각 V와 V-1이 되겠습니다. 최소 신장 트리는 그 중에서도 가중치가 있는 그래프일 때를 고려합니다. 그래프의 간선마다 가중치가 있을 때 간선의 가중치의 합이 최소가 되는 신장 트리를 최소 신장 트리라고 합..
2020.04.09