알고리즘 개념 총정리 - 탐색 및 기타

1. 탐색 (Search)

a) 너비우선탐색(Breadth First Search, BFS)

- Graph의 모든 노드를 탐색하는 알고리즘으로, 완전탐색에 포함된다.

- 동일한 level의 형제노드를 우선적으로 탐색하는 방법

- need_visit Queue와 visited Queue를 이용하여 방문할 노드와 방문한 노드의 정보를 관리한다.

- Vertex와 Arc의 수에 따라 O(V + A)의 시간복잡도를 가진다.

 

b) 깊이우선탐색(Deapth First Search, DFS)

- Graph의 모든 노드를 탐색하는 알고리즘으로, 완전탐색에 포함된다.

- 하나의 노드를 시작으로 자식노드를 순차적으로  말단노드까지 탐색한다.

- 말단노드까지 탐색을 했다면, 시작노드의 위치로 돌아와 동일한 방법으로 다른 형제노드를 탐색한다.

- Vertex와 Arc의 수에 따라 O(V + A)의 시간복잡도를 가진다.

 

c) 탐욕 알고리즘(Greedy Algorithm)

- 최적해에 근사한(approximate) 값을 찾는 알고리즘

- 매번 선택을 할 때마다, 최적해를 만들기 위해 가장 높은 확률을 가진 방향을 선택한다.

- 즉, 현 시점에서 최선/최적의 경우를 선택하는 방법 

---

2. 최단경로/최단거리 알고리즘

a)최단경로 또는 최단거리란?

- 가중치 그래프에서 특정 경로에 대해 간선의 가중치 합이 최소인 경로 

 

b) 최단거리 문제의 종류 

- 단일 출발 및 도착: A to B의 경로 중 최단경로를 찾는 케이스 

- 단일 출발: 특정 노드를 기점으로, 그 외의 모든 노드간의 최단경로를 찾는 케이스 

- 전체 쌍: 그래프 내의 모든 노드간의 최단경로를 찾는 케이스 

 

d) 다익스트라 알고리즘(Dijikstra Algorithm)

- 최단경로를 구하기 위한 알고리즘

- 그리디 알고리즘이자, 단일출발 케이스의 최단경로를 구하는 방법 

- 단일 출발을 기준으로 인접노드의 간선 가중치를 이용하여 최단거리를 갱신하는 방식 

- A to B의 모든 경로를 탐색하고 각 경로의 간선 가중치 합을 우선순위 Queue에 저장한다.

- 우선순위 Queue에 저장된 특정 노드까지의 경로 중 간선 가중치 합이 최소인 경로를 선택하여 최단경로를 찾는다.

- 모든 간선의 가중치를 오름차순으로 정렬하는 과정으로 인해 O(E log E)의 시간복잡도를 가진다. (E = Edge)

 

---

2. 최소신장트리(Minimum Spanning Tree, MST) 알고리즘

a) 신장트리(Spanning Tree)란?

- 모든 노드가 연결되어 있으며, 사이클이 존재하지 않는 Tree

 

b) 최소신장트리(MST)란?

- 모든 노드를 연결하는 경로 중 최소 가중치 합을 가진 경로로 이루어진 신장트리

 

c) 크루스칼 알고리즘(Kruskal's Algorithm)

- MST를 구하기 위한 알고리즘

- 그리디 알고리즘이자, 단일출발 케이스의 최단경로를 구하는 방법

- 모든 간선의 가중치를 오름차순으로 정렬하여 가중치 작은 순서로 노드를 하나씩 연결한다.

- 사이클의 유무를 판단하기위해 Union-Find 알고리즘을 사이클 검증 로직으로 사용한다.

- skewed tree의 생성을 방지하기 위해 Union-by-Rank 또는 Path Compression 기법을 Union-FInd와 함께 사용한다.

- 모든 간선의 가중치를 오름차순으로 정렬하는 과정으로 인해 O(E log E)의 시간복잡도를 가진다.(E = 탐색해야하는 간선의 갯수)

 

d) 프림 알고리즘(Prim's Algorithm)

- MST를 구하기 위한 알고리즘

- 그리디 알고리즘이자, 단일출발 케이스의 최단경로를 구하는 방법 

- 크루스칼은 전체 간선의 가중치를 정렬하여 MST를 구하는 방식이라면,

  프림은 시작 노드의 인접노드가 가진 간선 가중치를 정렬하여 순차적으로 간선을 선택하는 방식으로 MST를 구한다.

- 우선순위 Queue를 사용하여 인접노드의 간선 가중치 중 최소 가중치를 가진 간선을 추출한다.

- 인접노드를 대상으로 MST를 구하기에 사이클 검증은 따로하지 않다.

- 우선순위 Queue를 구축하는 과정으로 인해 O(E log E)의 시간복잡도를 가진다. (E = 탐색해야 하는 간선의 갯수)

 

e) 개선된 프림 알고리즘(Improved Prim's Algorithm)

- MST를 구하기 위한 알고리즘

- 그리디 알고리즘이자, 단일출발 케이스의 최단경로를 구하는 방법 

- 프림 알고리즘은 인접노드의 간선 가중치를 기준으로 우선순위 큐를 구축한다. 

  반면에, 개선된 프림 알고리즘은 노드를 기준으로 운선순위 큐를 구축한다.

- 프림 알고리즘은 인접노드의 간선 갯수에 의해 시간복잡도가 결정되어 O(E log E)의 시간복잡도를 갖는 반면, 

  개선된 프림 알고리즘은 노드의 갯수에 의해 시간복잡도가 결정되어 O(E log V)의 시간복잡도를 가진다.

- 노드의 갯수가 간선의 갯수보다 항상 적기 때문에, 그 차이만큼 반복문의 횟수가 줄어들어 시간복잡도가 개선된다. 

 

---

3. 기타 알고리즘 

a) 완전탐색 알고리즘

- 모든 경우의 수를 검증하여 답을 찾는 방법

- 모든 경우의 수를 검증하기 때문에 반드시 답을 찾는다.(장점)

- 모든 경우의 수를 검증하기 때문에 input의 크기에 비례하여 시간복잡도가 증가한다.(단점)

- 그러므로 input의 크기에 따른 반복문의 실행횟수를 잘 생각하고 적용해야 한다.

 

a-1) 완전탐색 알고리즘의 종류

- 브루트포스(Brute Force): if와 for문 만을 이용하여 모든 경우의 수를 검증하는 방법

- 비트마스크(Bit Mask): 컴퓨터의 이진연산을 이용한 방법으로, 0과 1에 해당하는 조건으로 나누어 모든 경우를 검증하는 방법 

- 재귀(Recursion): 비트마스크와 마찬가지로 2가지 경우로 나누어 모든 경우를 검증하는 방법 

- 순열(Permutation): N개의 서로 다른 수가 나열되어 있는 순열은 N!의 경우를 갖는다. 순열의 경우 N < 10일 때, 완전탐색을 사용한다.

- DFS/BFS: 길찾기 문제에서 장애물이나 경우지가 존재하는 경우, 완전탐색을 적용하여 모든 경로를 검증한 후 BFS/DFS를 적용한다.

- 백트래킹(BackTracking): 현재의 탐색이 조건에 부합하지 않는 경우, 이전 단계로 돌아가 다른 방향으로 탐색을 진행하는 방법 

 

b) 동적계획법(Dynamic Programming)

- 하나의 큰 문제를 여러개의 작은 문제로 쪼개어 파생된 값을 이용해 전체 문제를 해결하는 방법 

- 상향식 접근법과 메모이제이션(memoization) 기법을 사용하여 동일하거나 중복된 연산을 최소화하여 답을 구한다.

- 동적 계획법의 경우, 문제를 쪼갰을 때 하위 문제에 중복연산이 발생하는 경우 사용한다.

 

c) 분할정복(Divide & Conquer)

- 하나의 문제를 더이상 쪼갤 수 없을 때까지 최소화 하여, 하위 문제를 해결 후 병합하여 상위문제를 해결하는 방식

- 하향식 접근법(= 재귀)을 사용하여 답을 구한다.

- 분할 정복의 경우, 문제를 쪼갰을 때 하위 문제에서 중복연산이 발생하지 않는 경우 사용한다. 

- 대표적으로 병합정렬과 퀵 정렬이 분할정복 알고리즘에 해당한다.