컴퓨터 기본 알고리즘은 어떤 게 있을까?

 

프로그램의 로직과 데이터를 처리하는데 있어서 알고리즘은 매우 중요합니다. 결과가 같을지라도 알고리즘을 어떻게 세우느냐에 따라서 프로그램의 성능이 달라지기 때문입니다. 알고리즘은 그 원리를 안다면 코드로 구현하는 것은 어떤 프로그램밍 언어를 사용할지라도 방법이 비슷하죠. 따라서 무엇보다 알고리즘의 개념을 이해하는 것이 중요하다고 할 수 있습니다. 컴퓨터 이론에서는 대표적인 알고리즘이 몇 가지 있습니다. 이번 포스트에서는 알고리즘에 대해서 알아보겠습니다.  

---

 

1. Sorting Algorithm 

 

Sorting Algorithm은 리스트에 있는 원소들을 크기 순서에 따라서 정렬한 것 입니다. 

Sorting
Bubble Sort	두 개를 비교하여 정렬하는 방법
Insertion Sort	n-1 번째까지는 정렬되었다고 가정하고 n번째의 위치를 찾는 정렬
Selection Sort	최소가 되는 얘를 Select해서 맨 밑에 두는 방법
Merge Sort	Divide and Conquer. 둘씩 나눠서 정렬
Quick Sort	Pivot을 이용한 정렬
Bucket Sort	양동이에 배분을 하고 각각의 양동이에서 다른 Sort algorithm 적용
Radix Sort	Digit에 대한 정렬
heap Sort	자료 구조인 Heap에 원소들을 보관하고 Tree의 성질을 이용해서 정렬하는 방식

 

2. BFS/DFS

 

BFS(Breath First Search) 와 DFS(Depth First Search)는 그래프에서 엣지를 따라서 노드를 탐색하는 Search 알고리즘입니다. 두 개는 탐색 방법에 따라서 다릅니다. 

BFS	점을 탐색하면 주변의 점부터 탐색 Queue로 구현 가능
DFS	점을 탐색하면 점과 연결된 점에 지속적으로 탐색 Stack으로 구현 가능

3. Shortest Path

Shortest Path는 그래프에서 두 개의 점으로 가는 최소비용을 찾는 문제입니다. 

 

Dijkstra's Algorithm	Single Source Shortest Paths 거리가 최소인 Vertex를 선택하고 인접한 Vertex의 거리를 업데이트 합니다.  모든 Vertex를 찾을 때까지 반복합니다.  Vertex를 찾을 때, min Heap을 사용하면 O(E+V lg V) 시간에 찾을 수 있습니다.
Bellman-Ford	For graphs containing negative edge weights, Bellman-Ford runs in O(V.E)
Floyd Warshall	Non negative Cycle을 만드는 그래프여야 합니다.  All-pairs shortest Paths    i->k->j [cost]   i->k    [path]    k->j    [path] inorder print로 Path 확인 가능.

 

4. 기타

이 외에도 다양한 알고리즘이 존재합니다. 

Kadane's algorithm	원소의 합이 최대가 되는 Subsequence 찾기
Kruskal's algorithm	Minimal Spanning Tree를 찾는 방법 각각의 원소를 하나의 Set으로 생각합니다. Greedy하게 Edge를 선택하면서 Set을 합칩니다. Cycle을 만들지 않도록 주의!

 

---

위의 알고리즘은 기본 중의 기본으로 코드의 효율성을 위해서라면 반드시 인지하고 이어야 하는 알고리즘들 입니다.