알고리즘 종류 (탐색, 정렬, 그래프, 설계 기법)

 

문제를 해결하기 위한 절차나 방법인 알고리즘은 어떤 종류가 있고 어떠한 방식으로 설계되어 있는지 쉽고 간단하게 살펴보겠습니다. 

 

 

목차

 

 

자료 구조에 따른 분류

 

탐색 알고리즘

1. 선형 탐색 - 처음 위치부터 순차적으로 살펴보면서 값이 있는지 확인

2. 이진 탐색 - 리스트를 같은 크기의 두 부분으로 나누고 필요한 부분에서만 탐색하도록 제한

 

정렬 알고리즘

1. 버블 정렬 - 이웃한 두 숫자를 비교해가며 기준에 따라 수의 자리를 바꿔가면 정렬하는 방법

2. 선택 정렬 - 데이터에서 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해나가는 방식

3. 삽입 정렬 - 임의의 데이터를 이미 정렬된 배열 부분과 비교해 자신의 위치를 찾아 삽입해 가며 정렬

4. 병합 정렬 - 데이터를 최대한 쪼갠 다음 다시 병합하면서 정렬하는 방식

5. 퀵 정렬 - 리스트 안에 한 요소(피벗)를 선택해 피벗보다 작은 요소는 모두 왼쪽, 큰 요소들은 모두 오른쪽

6. 힙 정렬 - 힙 자료구조를 이용한 정렬 알고리즘

 

그래프 알고리즘

1. 깊이 우선 탐색 (DFS) - 트리나 그래프에서 한 루트로 탐색하다가 최대한 깊숙히 들어간 후 다시 돌아가 다른 루트로 탐색하는 방식

2. 너비 우선 탐색 (BFS) - 트리나 그래프에서 자식 노드를 차례로 방문하고 다시 각각의 자식 노드들을 차례로 방문하는 과정을 반복해 모든 노드를 방문하면 탐색을 마칩니다.

 

3. 최단 경로 알고리즘 - 출발지와 목적지 사이 링크들의 가중치 합이 최소가 되는 경로

4. 최소 신장 트리 (MST) - 간선에 가중치를 고려하여 최소 비용의 Spanning Tree를 선택하는 것

 

 

알고리즘의 설계 기법/전략/패러다임에 의한 분류

 

그리디 (Greedy) 알고리즘

매 선택에서 지금 가장 최적인 답만 선택하는 욕심쟁이(Greedy) 알고리즘입니다. 하지만 전체적으로 봤을 때 최적이라는 보장은 없습니다.

 

분할 정복 (Divide and Conquer)

여러 알고리즘의 기본이 되는 해결방법으로 크고 방대한 문제를 조금씩 나눠서 쉽게 풀 수 있는 문제 단위로 나눈 다음 그것들을 다시 합쳐서 해결합니다.

 

대표적으로 퀵 정렬, 병합정렬 등이 있고 오토마타에서도 사용됩니다.

동적 계획법 (Dynamic Programming)

최적화 이론의 한 기술로 분할 정복 알고리즘과 비슷합니다. 문제를 더 작은 문제의 연장선으로 생각하고 과거에 구한 해를 활용하는 방식의 알고리즘을 말합니다.

 

분할 정복 알고리즘과 차이점은 원래의 문제를 부분 문제로 나눌 때 부분 문제를 최대한 많이 이용할 수 있도록 나누어 계산하고 저장해 필요 시 바로 산출하여 이용한다는 것입니다.

 

백트레킹 (Backtracking)

모든 경우의 수를 전부 고려하는 알고리즘으로 일종의 트리 탐색 알고리즘. 

방식에 따라서 깊이우선탐색, 너비우선탐색, 최선 우선 탐색이 있습니다.

 

 

 

 

기타 분류

 

확률의 개입 여부에 따른 분류

1. 결정 알고리즘 - 항상 정확한 답을 반환하는 알고리즘

2. 확률 알고리즘 - 실행될 명령이 무작위로 결정되는 알고리즘

 

인공지능 분야

1. 머신 러닝 - 인공신경망, 서포트 벡터 머신

2. 미로탐색 알고리즘 - 트리 탐색 알고리즘

3. 데이터 마이닝 - 군집 분석, 회귀 분석

 

---

 

문제 해결을 위해 어떤 알고리즘을 선택하느냐에 따라 데이터 처리와 분석의 효율성에 큰 영향을 미칠 수 있습니다. 어떠한 알고리즘이 있는지 어떤 방식으로 돌아가는지 알아둔다면 적합한 알고리즘을 선택하는데 도움이 되겠죠.

관련포스트

알고리즘 (Algorithm) 기초 개념과 조건, 복잡도

딥러닝과 머신 러닝 개요

게임 알고리즘 (레벨업, 데미지, 피해량)

알고리즘 | 종류 (탐색, 정렬, 그리드)