'알고리즘'과 '알고리즘 설계 기법'은 다르다.

분할 정복(Divide And Conquer)이라고 들어본 적이 있을 것이다.

분할정복 전략은 주어진 문제를 가능한 가장 간단한 문제로 쪼개어 해결함으로써 복잡한 문제를 간단하게 해결하는 알고리즘 전략이다.

문자 그대로, 통째로 한 번에 이기기는 어려우니 잘게 쪼개서 정복하겠다는 전략이다.
(자세한 설명은 분할정복 이란을 참조)

그런데 분할정복은 '분할정복 알고리즘'으로도 불린다.
'선택 정렬', '이진 검색' 같은 알고리즘들 처럼 '알고리즘'이라고도 불린다는 것이다.

혼란은 여기서 시작되었다.

'검색할 값을 기준으로 두 그룹으로 나눠가며 값을 찾으라'는 이진 검색과
'복잡한 문제는 쪼개서 해결하라'는 분할정복을
둘 다 '알고리즘'이라는 같은 이름으로 부르기에 굉장히 찝찝하고 혼란스러웠달까.
분할정복은 분명 이진검색보다 뭔가 더 Meta적이고, 더 높은 층위에서 알고리즘을 얘기하는 것 같았기 때문이다.

상당히 많은 책들이나 온라인 문서들이 이것들을 특별히 구분하지 않고 부르고 있었기에, 따로 좀 더 찾아본 끝에 답을 얻을 수 있었다.

결론부터 말하자면 둘은 다르다.
'선택 정렬'은 알고리즘이고, '분할 정복'은 알고리즘 설계 기법이다.

알고리즘 설계 기법(Algorithm Design Paradigm) 이란?

알고리즘은 알고리즘 설계 기법을 기반으로 만들어진다.

퀵정렬과 병합정렬은 구체적인 정렬 방식은 다르지만, 큰 틀에서 정렬 대상 데이터를 둘로 나눠 각각 정렬한 후 그 두 데이터를 연결한다는 점에서 공통점을 가지고 있다.
내용도 다르고 성능도 다르지만 동일한 구조적 기반으로서 알고리즘 설계 기법을 공유하고 있다는 것이다.
(퀵정렬과 병합정렬은 '분할정복'이라는 설계 기법을 기반으로 한다)

이처럼 알고리즘 설계기법은 특정 알고리즘이 만들어지는 기반이 된다.

즉, 알고리즘 설계 기법이란 '알고리즘을 어떤 식으로 만들 수 있는가?'에 대한 이야기인 것이다.

알고리즘 설계 기법은 새로운 알고리즘을 만드는데 도움을 준다.

세상에는 훌륭한 알고리즘들이 많이 알려져 있다.
문제를 만나면 그 알고리즘들을 사용해서 해결하면 된다.
예를 들어 검색에는 퀵정렬이나 병합정렬을 사용하는 셈이다.

하지만 만약 새로운 문제를 만났다면?
내가 아는 알고리즘으로 풀 수 없는 문제를 만났다면?

그때는 새로운 알고리즘을 만들어야한다.
알고리즘 설계기법은 이때 도움을 줄 수 있다.
알고리즘 설계기법은 어떻게 알고리즘을 만들 수 있는지(= 문제를 해결할 수 있는지)에 대한 방법론/사고방식/전략 이기 때문에 효율적으로 새로운 알고리즘을 개발할 수 있게 도와준다.

알고리즘 설계 기법의 종류

다음은 내가 파악한 알고리즘 설계기법 종류이다.
설명이 가능한 것은 상세 포스팅으로 설명해놓았다.

• 분할 정복 Divide And Conquer
• 탐욕 알고리즘 Greedy Algorithm
• 동적 프로그래밍 Dynamic Programming