[Section 8] 알고리즘 설계 기초 _ 분류(Classification)

자료구조와 알고리즘 목차 보기

[INTRO] 자료구조와 알고리즘

0. INTRO

알고리즘의 설계를 위해서는 내가 구현하고자 하는 문제가 어떤 유형인지 알아내고, 문제에 맞는 알고리즘 구현 방법을 체계적으로 분류할 필요가 있다. 분류된 방법들에는 어떤 종류가 있는지 간단히 알아보기로 하자.

1.  구현 방법에 따른 분류

구현 방식에 따른 분류

가장 먼저 구현 방법에 따른 분류로는 재귀(Recursion) 및 반복(Iteration) 알고리즘이 존재한다. 명령의 반복에 의해서 구현되는 이 알고리즘들은 쉽게 구현될 수 있다는 장점을 가지고 있다. 쉽게 구현될 수 있는 대표적인 문제들 중 하나는 "하노이의 타워 문제"이다.

 

다음으로 절차적 혹은 비-절차적(Non-Procedural) 알고리즘 구현 방법이 존재한다. 이 방법은 절차적 단계를 알고리즘의 형태로 잘 명시하는 방법이라 할 수 있겠다. 이 때문에 코드가 무엇을 의미하는지를 나타내는 선언적(Declarative) 알고리즘 구현 방법과 비교되기도 한다. 예를 들어, 웹페이지에 사용되는 HTML은 선언형 프로그래밍 언어이다. 반대로 절차적 프로그래밍 언어에는 C언어 등의 언어가 존재한다.

 

* 조금 더 깊게 들어가면, 구조화 질의어(Structured Query Language)이라는 프로그래밍 언어가 존재한다. 이는 관계형 데이터 베이스의 관리시스템에 특화된 프로그래밍 방법이다. 이 SQL은 선언형 프로그래밍으로 분류할 수 있다.

 

그리고 알고리즘의 구현 방법은 직렬 혹은 병렬(Serial or Parallel), 그리고 분산(Distributed)으로 분류될 수 있다. 만약 프로그램이 명령을 한 번에 하나씩 실행한다면 직렬 알고리즘이고, 동시에 여러 명령들을 실행한다면 병렬 알고리즘 방식이다. 이 병렬 알고리즘 방식은 독특하게도 컴퓨터 이외의 다른 기계들에도 이식될 수 있는 경우가 있으며, 다른 기계들에 이식되는 알고리즘을 분산형으로 분류한다.

2.  설계 방법에 따른 분류

설계 방식에 따른 분류

가장 먼저 그리디(Greedy) 알고리즘은 전역(global)에서 최적화 해를 찾기 위해 지역(local)에서 최선을 선택하는 알고리즘이다. 이게 무슨 소린가 하면, 정수 데이터가 작은 값에서부터 큰 값으로 정렬된 트리와 같은 자료구조에서 가장 큰 데이터를 탐색하는 프로그램을 만든다고 가정해보자. 이중의 선택길에서 그리디 알고리즘은 매번 문제 조건에 맞는 최선의 해, 즉 두 개의 선택지 중 큰 값을 선택하는 방법으로 문제를 해결한다. 결론적으로 그 결과가 트리 전체의 데이터 관점에서 최선의 답인가? 아닐 가능성이 분명히 존재하지만, 순간순간의 탐욕에 의존한다고 해서 탐욕 알고리즘이라고 부른다. 

 

분할 정복(Divide and Conquer) 알고리즘은 문제를 더 작은 하위 문제들로 분리하고 그 문제들의 해를 반복해서 구한다. 그리고 최종적으로 해를 결합하여 근접한 답을 구하는 알고리즘이다. 더 자세한 내용은 이후의 알고리즘에서 확인해보자. 

 

동적 프로그래밍(Dynamic Programming) 알고리즘은 분할 정복과 유사하게 하위  문제들로 분리하여 최적화된 답을 구하는 방식이다. 그렇다면 차이점은 무엇인가?  동적 프로그래밍은 동일한 하위 문제들에 대한 답을 저장해두기 때문에 동일한 하위 문제에서 간단히 답을 내린다. 마찬가지로 더 자세한 내용은 이후의 알고리즘에서 확인해보자. 

 

선형 프로그래밍(Linear Programming) 알고리즘은 선형 목적의 함수를 최적화하는 방식이다. 예를 들면, 일차 방정식과 같은 선형 관계에 있는 데이터들을 처리할 때 효율적인 방법이라 할 수 있다. 

 

마지막으로 치환 정복(Transform and Conquer) 알고리즘은 같은 문제를 다른 방식으로 바꾸는 방법이다. 주로 어려운 문제를 간단한 문제로 바꿀 때 사용되는데, 자세한 내용은 알고리즘을 통해 알아보자.

 

* 위에서 언급한 알고리즘의 분류는 이외에도 복잡도에 따른 분류나 랜덤 한 알고리즘 등 다양한 형태로 분류되기도 한다.