[알고리즘] 알고리즘 디자인 기법

1. 구현 기법에 의한 분류

1) 재귀 혹은 반복

재귀 알고리즘은 기본 조건이 충족될 때까지 자신을 반복 호출. C, C++에서 일반적으로 사용

반복 알고리즘은 기본적으로 루프 같은 구조로 스택이나 큐 등에 데이터 구조를 사용하여 문제 해결

어떤 문제들은 재귀에 적합하고 다른 문제들은 반복에 적합하다.

모든 재귀 알고리즘은 반복 알고리즘으로 변환 또는 반대로 가능하다.

 

2) 절차적 또는 선언적

선언형 프로그래밍 언어에서는 무엇을 할 것인지를 정의하는 방식을 이용한다.

절차적 프로그래밍에서는 결과를 얻기 위한 정확한 단계를 명시해야 한다.

SQL은 절차적이라기보다 선언적이다. 절차적 언어는 C, PHP, PERL 등

 

3) 직렬 또는 병렬 또는 분산

컴퓨터가 한 번에 한 명령을 수행한다고 가정하는데, 이를 직렬 알고리즘이라 한다.

병렬 알고리즘은 한 번에 여러 명령을 수행한다. 문제를 부속 문제들로 나누어 여러 프로세서나 스레드에 넘긴다.

반복 알고리즘은 일반적으로 병렬화하여 사용.

분산 알고리즘은 여러 개의 기계에 분산시키는 알고리즘

 

4) 결정적 또는 비결정적

결정적 알고리즘은 문제를 미리 정의된 절차로 풀고

비결정적 알고리즘은 휴리스틱을 사용해 매 단계마다 최선의 방법을 추측한다.

 

5) 정확한 또는 근사

최적의 해답을 찾도록 하는 알고리즘들은 정확한 알고리즘이라고 한다.

컴퓨터 과학에서는 최적의 해답이 없다면 근사 알고리즘을 제시하도록 하는 방법을 사용

근사 알고리즘은 일반적으로 NP-난해 문제에 연관

 

2. 디자인 기법에 의한 분류

1) 탐욕기법

단계별로 동작

각 단계에서 앞으로 결과에 상관하지 않고 그 시점에서 좋은 것을 결정하기 때문에

일반적으로 가장 가까운 범위에서 최선의 결과가 선택된다. 이렇게 선택된 결과가

전역적으로도 최적의 결과라고 가정하는 방식

 

2) 분할 정보

일명 D&C(Divide and Conquer)전략은 문제를 나누어서 해결한다.

  - 1) 분할 : 문제를 같은 종류의 더 작은 단위인 부속 문제들로 나눈다.

  - 2) 재귀: 부속 문제들을 재귀적으로 푼다.

  - 3) 정복: 해답들을 적절하게 합친다.

예:병합 정렬과 이진 검색 알고리즘

 

3) 동적 계획법

동적 계획법(DP, Dynamic Programming)과 메모라기(Memorization)는 함께 동작한다.

동적계획법과 분할 정복의 차이점은 분할 정복의 경우에는 보속 문제들 사이에 의존성이 없는데

반해 동적계획법은 부속 문제들이 중첩한다는 것

메모하기(이미 푼 문제를 유지)를 사용함으로써 DP는 많은 문제에 대해 지수적 복잡도를 다항적 복잡도로 감소시킨다.

동적계획법과 재귀의 차이점은 메모하기의 사용 유무이다.

부속 문제들이 비의존적이고 반복되지 않는다면 메모하기는 큰 도움이 되지 못하므로

동적계획법이 모든 문제의 해결법은 아니다. 동적계획법은 메모하기를 사용하여

복잡도를 지속적에서 다항적으로 감소시키는 장점이 잇다.

 

4) 선형 계획법

선형계획법(Linear Programming)에서는 입력과 입력에 대한 최대화(혹은 최소화) 선형 함수의

부등식을 갖는다. 많은 예제에서 선형계획법이 사용

예:방향 그래프의 최대 흐름

 

5) 감소 기법

감소기법은 해결하기 어려운 문제를 점근적인 최적 알고리즘을 갖고 있는 문제로 변환하려 풀 수 있도록 한다.

이 기법의 목적은 복잡도가 감소된 알고리즘에 영향 받지 않고 감소 알고리즘을 찾는 것이다.

예:리스트의 중간값을 찾는 선택 알고리즘은 정령과 정렬된 리스트에서 중간 항목 찾기가 포함된다.

이들 기법은 변환 정보(Transform And Conquer)이라고도 한다.

 

3. 기타 분류

1) 연구 영역에 따른 분류