알고리즘 실전 활용을 위한 요약

알고리즘을 실전에 활용하기 위해서, 간단하게 어떤 알고리즘이 어떤 역할을 수행하는지에 대한 요약글을 적어보려한다.

나동빈님의 알고리즘 강의를 수강하면서 차곡차곡 적어나가보도록 하겠다. 등장하는 사진의 출처는 역시 나동빈님의 블로그/강의다.

영어/한국어/줄임말 모두로 제목을 걸어놓았으니 Ctrl + F로 원하는 알고리즘을 찾으면 된다.

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

최단 길이를 보장해야 할 때 많이 사용한다. 현재 노드에서 가장 가까운 노드부터 방문하는 것으로,

위와 같은 그래프일때 1부터 탐색을 시작하면 1 - 2 - 3 - 4 - 5 - 6 - 7의 순서로 방문하게 된다. 추후 다른 알고리즘에 활용되는 기본 알고리즘이다.

깊이 우선 탐색 (Depth First Seach, DFS)

방문하지 않은 인접노드를 깊이 우선으로 계속해서 방문하는 알고리즘으로 각 노드를 탐색할 때 사용된다.

위의 BFS 설명과 같은 그래프에서 1 - 2 - 3 - 6 - 7 - 4 - 5의 순서로 방문하게 된다.

합집합 찾기, 서로소 집합 알고리즘 (Union-Find, Disjoint-Set)

여러개의 노드가 존재할때 선택한 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘이다.

사진처럼 연결된 그래프가 있을때 1과 7을 선택해서 두개가 연결되있는지! 혹은 7의 부모는 누구인지! (여기서는 5) 판별할 수 있다. 

크루스칼 알고리즘, 최소비용신장트리 만들기 (Kruskal Algorithm, Minimum Spanning Tree)

 

여러개의 노드와, 그 노드간에 비용이있는 간선이있을때 그것을 최소 비용으로 이어주게 하는 알고리즘이다.

여러 개의 도시가 있을 때 각 도시를 연결할때 드는 비용을 최소한으로 하고자 할때 사용하기도 한다.

이진트리 순회 알고리즘, 전위/중위/후위 순회 (Binary tree traversal, preorder, inorder, postorder)

이진트리가 있을 때 이를 어떻게 순회할지 결정하는 방식이다. 특히 후위 순위의 경우 수식을 컴퓨터가 계산하기 쉽게하기 위해 사용되어

계산기 프로그램에서 잘 쓰인다. 전위 순회는 자신을 방문 -> 왼쪽 자식 방문 -> 오른쪽 자식 방문 순서로 순회하며, 중위 순회는 좌 -> 자신 -> 우 순서로, 후위 순회는 좌-> 우 -> 자신 순서로 방문한다.

전위: 1 - 2 - 4 - 8 - 9 - 5 - 10 - 11 - 3 - 6 - 12 - 13 - 7 - 14 - 15

중위: 8 - 4 - 9 - 2 - 10 - 5 - 11 - 1 - 12 - 6 - 13 - 3 - 14 - 7 - 15

후위: 8 - 9 - 4 - 10 - 11 - 5 - 2 - 12 - 13 - 6 - 14 - 15 - 7 - 3 - 1

동적계획법, 다이나믹 프로그래밍 (Dynamic Programming, DP)

대회에 많이 사용되는 알고리즘.

하나의 문제는 단 한번만 푸는 알고리즘. 분할정복 알고리즘에서 처럼 문제를 쪼개어 해결하는 과정에서

이미 푼 문제는 배열이나 다른 공간에 저장해두고 (메모이제이션, memoization) 이것만을 가져와서 재 계산을 줄인다.

에라토스테네스의 체, 소수판별 알고리즘 (Eratosthenes' sieve)

특정숫자가 소수인지 아닌지를 판별할때 단순하게 생각하면 2부터 N-1까지의 숫자로 일일이 나눠보면서 풀기 쉽다.

하지만 에라토스테네스의 체를 사용하면 많은 양의 소수를 빠르게 구할 수 있다. 소수라는 것은 "어떤 수의 배수가 아니다" 이기때문에

N까지의 배열을 만들고, 2부터 자기자신의 수는 남겨두고 자신의 배수를 지워주는 것이다.  그러면 만든배열의 N번째 칸이 지워지지않았다면 소수인것이다.

다익스트라 알고리즘, 최단경로 탐색 알고리즘 (Dijkstra algorithm, Shortest Path Algorithm)

특정 정점에서 다른 모든 정점까지 가는 최단 거리를 구할 때 사용하는 알고리즘으로, 최단경로 탐색 알고리즘이다.

GPS 소프트웨어에서 많이 사용하기도 한다. 하나의 최단거리를 구할 때 이전까지 구했던 최단 거리정보를 사용한다는 점에서 동적프로그래밍을 사용한다.

플로이드 와샬 알고리즘 (Floyd Warshall Algorithm)

다익스트라 알고리즘이 한 정점에서 출발하여 다른 모든 정점까지의 거리를 계산하는 알고리즘이라면, 플로이드 와샬 알고리즘은 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘이다. 특징점으로는 '거쳐가는 정점'을 기준으로 알고리즘을 수행하는 것이 있다.

1에서 3으로 가는 경로를 구한다면 정점 2를기준으로 1->2로 가는 비용 + 2->3 으로가는 비용과 1->3으로 가는 비용을 비교해서 갱신한다.