[알고리즘] 알고리즘 설계 기법

 

* 알고리즘(algorithm)
: 수학과 컴퓨터과학, 언어학 또는 엮인 분야에서 어떠한 문제를 해결하기 위해 정해진 일련의 절차이다. 계산을 실행하기 위한 단계적 절차를 의미하기도 한다. 즉, 문제 풀이에 필요한 계산절차 또는 처리과정의 순서를 뜻한다. 프로그램명령어의 집합을 의미하기도 한다. 알고리즘은 연산, 데이터 마이닝(기계 학습) 또는 자동화된 추론을 수행한다.

 

1. 동적계획법(Dynamic Programming)

: 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법. 어떤 문제는 그 문제를 해결하기 위한 작은 문제들의 해의 결합으로 풀수 있다는 사고를 기반으로 함 / ex) 최단경로문제, 행렬의 제곱문제

 

2. 탐욕적 알고리즘(Greedy Algorithm)

: 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달. 분기마다 선택된 최적의 해의 결합이 전역적으로 최적이 되는 것은 아님

 

3. 재귀적 알고리즘(Recursion Algorithm)

: 해를 찾는 과정에서 자기 자신을 재참조해서 다시 불러오는 과정을 반복하는 방법. 호출의 역순으로 결과를 냄

 

4. 근사 알고리즘(Approximation Algorithm)

: 어떤 최적화 문제에 대한 해의 근사값을 구하는 알고리즘. 가장 최적화되는 답을 구할 수는 없지만, 비교적 빠른 시간에 계산이 가능하며 어느 정도 보장된 근사해를 계산할 수 있음. NP-완전 문제등 현재 알려진 빠른 최적화 알고리즘이 없는 문제에 대해 주로 사용됨

 

5. 분할정복법(Divide and Conquer)

:  그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법

 

6. 퇴각 검색법(Backtracking)

: 분기구조(tree) 탐색에서 탐색이 실패하는 경우, 새로운 탐색이 가능한 분기까지 탐색 과정을 되돌려 진행하는 방식, 모든 트리의 노트를 검사해도 답을 찾지 못하는 경우는 문제의 해답이 없는 경우로 판단 / ex) 깊이 우선 탐색(DFS)