분할 정복 알고리즘

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 분할 정복 알고리즘
3. 역사적 예시
4. 장점
5. 구현 시 고려 사항
참조

1. 개요

분할 정복 알고리즘은 주어진 문제를 더 작은 하위 문제로 나누어 해결하고, 하위 문제의 해결책을 결합하여 원래 문제의 해를 구하는 방식이다. 충분히 작은 하위 문제는 직접 해결하며, 재귀 함수를 사용하여 구현하는 것이 일반적이다. 이진 검색, 유클리드 호제법, 쿨리-터키 고속 푸리에 변환, 병합 정렬, 카라추바 알고리즘 등이 분할 정복 알고리즘의 예시이며, 어려운 문제 해결, 알고리즘 효율성 향상, 병렬 처리, 메모리 캐시 활용, 반올림 오류 제어 등의 장점을 가진다. 구현 시에는 재귀, 명시적 스택, 스택 크기, 기저 사례 선택, 중복되는 하위 문제 등을 고려해야 한다.

더 읽어볼만한 페이지

최적화 알고리즘 및 방법 - 신뢰 영역
신뢰 영역 방법은 비선형 최적화에서 함수의 모델을 신뢰할 수 있는 영역 내에서만 사용하여 최적화를 수행하는 방법으로, 다양한 분야에서 전역 최적해를 찾기 위한 도구로 활용된다.
최적화 알고리즘 및 방법 - 확률적 계획법
확률적 계획법은 불확실한 상황에서 최적의 의사 결정을 내리기 위한 수학적 방법론으로, 다양한 확률적 프로그래밍 기법을 포함하며, 생물학, 경제, 금융 공학 등 여러 분야에 응용된다.
알고리즘 - 텍스트-비디오 모델
텍스트-비디오 모델은 텍스트 입력을 기반으로 비디오를 생성하는 인공지능 모델로서, 다양한 모델들이 개발되고 교육, 홍보, 창작 산업 등 여러 분야에 활용되지만 컴퓨팅 자원 소모, 데이터 부족, 텍스트 해석 오류, 윤리적 문제 등의 한계점을 가진다.
알고리즘 - 마스터 정리
마스터 정리는 분할 정복 알고리즘의 시간 복잡도 분석 도구로서, 점화식을 세 가지 경우로 나누어 재귀 알고리즘의 효율성을 파악하고, 다양한 정렬 및 일반 알고리즘 분석에 활용되지만, 특정 조건에서는 적용이 제한될 수 있습니다.

분할 정복 알고리즘

2. 분할 정복 알고리즘

분할 정복 알고리즘은 주어진 문제를 그와 유사하지만 크기가 더 작은 여러 개의 하위 문제로 나누어 해결하고, 그 결과를 조합하여 원래 문제의 답을 얻는 방식이다. 문제가 충분히 작아지면 직접 해결한다. 분할 정복 알고리즘은 문제의 최적 해를 찾는 데 자주 사용된다.^[2]

예를 들어, 주어진 ''n''개의 자연수 목록을 정렬하는 경우, 목록을 약 ''n''/2개의 숫자를 포함하는 두 개의 하위 목록으로 나누고, 각 하위 목록을 재귀적으로 정렬한 다음, 정렬된 두 하위 목록을 병합하여 최종적으로 정렬된 목록을 얻는다. 이 방식이 바로 병합 정렬 알고리즘이다.

오름차순으로 정렬할 목록 (38, 27, 43, 3, 9, 82, 10)에 대한 분할 정복 접근 방식. ''상단 절반:'' 하위 목록으로 분할; ''중간:'' 단일 요소 목록은 자명하게 정렬됨; ''하단 절반:'' 정렬된 하위 목록들을 병합하여 최종 결과를 구성함.

분할 정복 알고리즘은 보통 재귀 함수를 통해 자연스럽게 구현된다. 의사 코드로 표현하면 다음과 같은 형태를 띤다.

```text

function F(x):

if F(x)의 문제가 간단 then:

return F(x)을 직접 계산한 값

else:

x를 y1, y2로 분할

F(y1)과 F(y2)를 호출

return F(y1), F(y2)로부터 F(x)를 구한 값

```

더 일반적인 형태의 의사 코드는 다음과 같다.

```text

function conquer(x) is

if x는 쉽게 conquer할 수 있다면

return conquer의 결과

else

(x1, x2, ...) := divide(x) // 여러 개의 작은 부문제로 분할

(y1, y2, ...) := (conquer(x1), conquer(x2), ...) // 재귀 호출을 통해 각 부문제를 해결

return synthesize(y1, y2, ...) // 각 부문제의 해를 합성하여 원래 문제의 해를 구함 (예: 최댓값 선택)

```

이러한 재귀 호출은 함수 호출에 따른 오버헤드 때문에 실행 속도가 느려질 수 있다. 실행 속도를 높이거나 부문제 해결 순서를 제어하기 위해, 재귀 호출 대신 스택이나 큐 같은 자료구조를 이용하여 분할 정복 알고리즘을 구현할 수도 있다. 큐를 사용하는 경우는 주로 너비 우선 탐색처럼 횡적 탐색이 필요할 때 고려된다.

"분할 정복"이라는 용어는 때때로 각 문제를 단 하나의 하위 문제로 축소하는 알고리즘에도 사용된다. 예를 들어 정렬된 목록에서 특정 값을 찾는 이진 검색 알고리즘이나 수치 해석 분야의 근 찾기 알고리즘 중 하나인 이분법이 이에 해당한다.^[2] 이러한 알고리즘은 일반적인 분할 정복 알고리즘보다 효율적으로 구현될 수 있으며, 특히 꼬리 재귀 최적화를 통해 단순한 반복문으로 변환될 수도 있다. 하지만 넓은 의미에서는 재귀나 반복문을 사용하는 모든 알고리즘을 분할 정복으로 볼 수도 있기 때문에, 일부 전문가들은 문제가 두 개 이상의 하위 문제로 나뉘는 경우에만 "분할 정복"이라는 용어를 사용해야 한다고 주장한다.^[3] 문제가 단 하나의 하위 문제로 줄어드는 경우에는 '''감소 정복'''(decrease and conquer)이라는 용어를 사용하기도 한다.^[4]

분할 정복 기법의 중요한 응용 분야 중 하나는 최적화 문제이다. 각 단계에서 검색 공간이 일정한 비율로 줄어드는 경우("가지치기"), 전체 알고리즘의 복잡도는 가지치기 단계의 복잡도와 점근적으로 동일해진다. 이를 가지치기 및 검색(prune and search)이라고 한다.

분할 정복 알고리즘은 재귀 호출 과정에서 동일한 하위 문제를 여러 번 반복해서 푸는 경우가 발생할 수 있다. 이 경우 계산 비용이 지수적으로 늘어나 현실적으로 계산을 완료하기 어려워질 수 있다. 이러한 문제는 이전에 계산된 결과를 저장해두고 재활용하는 메모이제이션 기법으로 해결할 수 있다. 동적 계획법은 메모이제이션을 처음부터 통합하여 설계된 대표적인 기법이다.

또한, 재귀 호출을 사용하는 프로그램은 재귀의 깊이가 깊어질 경우 스택 사용량이 증가하여 메모리 부족이나 스래싱과 같은 문제를 일으킬 수 있다. 재귀를 반복문으로 변환하는 기법도 존재하지만, 꼬리 재귀가 아닌 일반적인 재귀를 변환하는 것은 직접 스택을 관리하는 것과 유사하여 복잡도에 비해 큰 이득이 없을 수도 있다.

3. 역사적 예시

분할 정복 알고리즘의 초기 예시들은 주로 원래 문제를 연속적으로 하나의 하위 문제로 분해하여 반복적으로 해결하는 감소 정복 방식에 해당한다.

이진 검색은 하위 문제의 크기가 원래 문제의 약 절반이 되는 대표적인 감소 정복 알고리즘으로 오랜 역사를 지닌다. 컴퓨터에서의 명확한 알고리즘 설명은 1946년 존 모클리의 논문에서 처음 등장했지만, 검색 효율을 높이기 위해 항목 목록을 정렬하는 아이디어 자체는 기원전 200년경 바빌로니아 시대까지 거슬러 올라간다.^[8] 또 다른 고대의 감소 정복 알고리즘으로는 두 수의 최대공약수를 구하는 유클리드 호제법이 있다. 이 방법은 문제를 점점 더 작은 크기의 동일한 하위 문제로 줄여나가며, 기원전 수 세기 전부터 사용되었다.

문제를 여러 개의 하위 문제로 나누는 분할 정복 알고리즘의 초기 예시로는 가우스가 1805년에 기술한 쿨리-터키 고속 푸리에 변환(FFT) 알고리즘을 들 수 있다.^[5] 하지만 가우스는 연산 횟수를 정량적으로 분석하지 않았고, 이 알고리즘은 100년 이상 지난 후에 재발견되어 널리 사용되기 시작했다.

컴퓨터를 위해 특별히 개발되고 제대로 분석된 최초의 분할 정복 알고리즘 중 하나는 병합 정렬로, 1945년 존 폰 노이만에 의해 발명되었다.^[6]

또 다른 중요한 예시는 1960년 아나톨리 A. 카라추바가 발명한 카라추바 알고리즘이다. 이 알고리즘은 두 개의 ''n''-자리수 숫자를 $O(n^{\log_2 3})$ (빅 오 표기법) 연산만으로 곱할 수 있게 했다. 이는 안드레이 콜모고로프가 1956년에 제기했던, 해당 연산에 최소 $\Omega(n^2)$ 의 연산이 필요할 것이라는 추측을 반증하는 결과였다.

컴퓨터와 직접적인 관련 없이 사용된 분할 정복 방식의 예시도 있다. 도널드 커누스는 우체국에서 우편물을 배송 지역별로 분류하는 방식을 예로 들었다. 편지들을 각기 다른 지리적 영역에 해당하는 별도의 가방으로 나누고, 각 가방 안의 편지들을 다시 더 작은 하위 지역별 묶음으로 정렬하는 과정을 배달 직전까지 반복하는 방식이다.^[8] 이는 1929년 이전에 사용된 펀치 카드 정렬 기계에서 활용된 기수 정렬과 관련이 있다.^[8]

4. 장점

분할 정복 알고리즘은 여러 가지 장점을 가진다. 복잡한 문제를 작은 하위 문제로 나누어 해결함으로써 하노이의 탑과 같은 어려운 문제를 푸는 데 효과적인 접근법을 제공한다. 또한, 카라추바 알고리즘, 퀵 정렬, 병합 정렬, 고속 푸리에 변환 등 많은 효율적인 알고리즘 개발의 기반이 되었으며, 종종 알고리즘의 점근적 복잡도를 개선하는 결과를 가져온다.

분할된 하위 문제들은 멀티 프로세싱 환경에서 병렬 처리하기에 용이하여 성능 향상을 기대할 수 있다. 더불어, 메모리 캐시와 같은 메모리 계층 구조를 효율적으로 활용하여 메모리 접근성을 높이는 데 유리하며, 이는 캐시 무관 알고리즘 설계로 이어지기도 한다.^[9] 마지막으로, 부동 소수점 연산 시 반올림 오류를 제어하는 데 있어 단순 반복 계산보다 더 정확한 결과를 제공할 수 있다.^[10]

4. 1. 어려운 문제 해결

분할 정복은 개념적으로 어려운 문제를 해결하는 강력한 도구이다. 이 방법은 문제를 여러 개의 하위 문제로 나누고, 가장 간단한 경우의 해답을 구한 뒤, 각 하위 문제의 해답을 결합하여 원래 문제의 해답을 찾는 방식으로 작동한다. 이와 유사하지만 구분되는 방식으로, 감소 정복은 문제를 단 하나의 더 작은 문제로 줄여나가는 접근법을 사용한다. 고전적인 하노이의 탑 퍼즐은 높이 ''n''인 탑을 이동하는 문제를 높이 ''n-1''인 탑을 이동하는 문제로 줄이는 감소 정복 방식의 좋은 예시이다.

분할 정복 알고리즘을 의사 코드로 표현하면 다음과 같은 재귀 호출을 사용한 형태가 된다. 분할 정복 방식을 사용하는 알고리즘을 구현할 때 기본적인 골격은 다음과 같다.

function conquer(x) is

if x는 쉽게 conquer할 수 있다면

return conquer의 결과

else

(x1, x2, ...) := divide(x) // 여러 개의 작은 부문제로 분할

(y1, y2, ...) := (conquer(x1), conquer(x2), ...) // 재귀

return synthesize(y1, y2, ...) // 각 부문제의 해를 합성 (최댓값을 고르는 등)

구체적인 알고리즘의 예시로는 합병 정렬 문서를 참고할 수 있다.

4. 2. 알고리즘 효율성

분할 정복 패러다임은 종종 효율적인 알고리즘을 발견하는 데 도움을 준다. 예를 들어, 이는 카라추바의 빠른 곱셈 방법, 퀵 정렬과 병합 정렬 알고리즘, 슈트라센 알고리즘을 이용한 행렬 곱셈, 그리고 고속 푸리에 변환의 핵심이었다.

이러한 예시들에서 볼 수 있듯이, 분할 정복 접근 방식은 해결책의 점근적 비용을 개선하는 결과를 가져오는 경우가 많다. 예를 들어, 다음과 같은 조건들이 만족될 때 분할 정복 알고리즘의 비용은

O(n\log_{p}n)

이 된다.

(a) 기저 사례의 크기가 상수 범위 내에 있다.
(b) 문제를 분할하고 부분적인 해결책을 결합하는 작업이 문제의 크기 $n$ 에 비례한다.
(c) 각 단계에서 크기가 약 $n/p$ 인 하위 문제는 $p$ 개로 제한된다.

4. 3. 병렬 처리

분할 정복 알고리즘은 멀티 프로세싱 환경에서 효율적으로 작동한다. 특히 공유 메모리 시스템을 사용하는 컴퓨터에서는 나누어진 각 하위 문제를 서로 다른 프로세서에서 동시에 실행할 수 있다. 이 방식은 여러 프로세서 간의 데이터 통신을 미리 복잡하게 계획할 필요가 없다는 장점을 가진다.

4. 4. 메모리 접근성

분할 정복 알고리즘은 자연스럽게 메모리 캐시를 효율적으로 사용하게 된다. 하위 문제가 충분히 작아지면, 상대적으로 느린 주 메모리에 접근하는 대신 캐시 내에서 해당 하위 문제와 관련된 모든 계산을 처리할 수 있기 때문이다. 이렇게 캐시를 효율적으로 활용하도록 설계된 알고리즘을 ''캐시 무관 알고리즘''이라고 부른다. 이 명칭은 알고리즘 설계 시 특정 캐시 크기를 매개변수로 명시적으로 포함하지 않는다는 특징에서 유래했다.^[9]

더 나아가, 정렬, FFT, 행렬 곱셈과 같은 주요 알고리즘에 대해 분할 정복 기법을 적용하여 ''최적의'' 캐시 무관 알고리즘을 설계할 수 있다. 이는 알고리즘이 특정 캐시 크기에 상관없이 점근적으로 최적의 방식으로 캐시를 활용한다는 의미이다. 반면, 전통적인 캐시 활용 기법인 ''블로킹''(루프 네스트 최적화 등)은 문제를 특정 크기의 덩어리로 명시적으로 나누어 처리하며, 이는 특정 컴퓨터의 캐시 크기에 맞게 알고리즘을 조정해야만 최적의 캐시 성능을 얻을 수 있다.

분할 정복 알고리즘의 이러한 메모리 계층 구조 활용 이점은 캐시 외에도 NUMA(Non-Uniform Memory Access)나 가상 메모리 시스템처럼 여러 단계로 이루어진 다른 계층적 저장 시스템에서도 동일하게 적용된다. 즉, 하위 문제가 충분히 작아지면 상위 계층(더 느린 저장 장치)에 접근하지 않고도 현재 계층 내에서 문제를 해결할 수 있다.

4. 5. 반올림 제어

부동 소수점 숫자와 같이 반올림이 필요한 산술 연산에서 분할 정복 알고리즘은 겉보기에는 동일해 보이는 반복적인 방법보다 더 정확한 결과를 얻을 수 있다. 예를 들어, ''N''개의 숫자를 더하는 경우, 각 데이터를 하나의 변수에 순서대로 더하는 간단한 반복 방법과 쌍별 덧셈이라는 분할 정복 알고리즘을 사용할 수 있다. 쌍별 덧셈은 데이터 집합을 두 부분으로 나누고 각 부분의 합을 재귀적으로 계산한 다음, 최종적으로 두 합을 더하는 방식이다. 이 두 번째 방법은 첫 번째 방법과 동일한 횟수의 덧셈 연산을 수행하고 재귀 호출에 따른 추가적인 부담(오버헤드)이 있지만, 일반적으로 더 정확한 계산 결과를 제공한다.^[10]

5. 구현 시 고려 사항

분할 정복 알고리즘을 실제 코드로 구현할 때는 여러 가지 중요한 사항들을 고려해야 한다. 이는 알고리즘의 효율성과 안정성에 직접적인 영향을 미치기 때문이다.

주요 고려 사항으로는 문제를 해결하는 방식(재귀 또는 반복), 메모리 관리(특히 스택 사용 시), 재귀 호출을 멈추는 조건(기저 사례) 설정, 그리고 동일한 계산이 반복되는 문제(중복 하위 문제) 처리 등이 있다.

재귀는 분할 정복 알고리즘을 자연스럽게 표현하는 방법이지만, 함수 호출 오버헤드나 스택 오버플로의 위험이 따른다. 이를 해결하기 위해 명시적인 스택이나 다른 자료구조를 사용하는 반복적인 구현 방식도 고려될 수 있다. 또한, 재귀의 깊이와 필요한 스택 크기를 예측하고 관리하는 것이 중요하다.

알고리즘의 종료 조건인 기저 사례를 어떻게 설정하느냐에 따라 성능이 크게 달라질 수 있으며, 너무 작은 문제까지 재귀적으로 처리하는 것보다 적절한 크기에서 반복문 등으로 처리하는 것이 효율적일 수 있다. 마지막으로, 동일한 하위 문제가 반복적으로 계산되는 경우 메모이제이션이나 동적 계획법과 같은 기법을 사용하여 불필요한 계산을 줄이는 것이 성능 향상에 필수적이다.

5. 1. 재귀

분할 정복 알고리즘은 보통 재귀 함수(recursive function)를 통해 자연스럽게 구현된다. 재귀 함수는 자기 자신의 정의 내에서 자기 자신을 호출하는 함수를 말한다. 분할 정복 알고리즘을 재귀적으로 구현하면, 현재 해결 중인 문제에서 파생된 하위 문제들이 자동으로 프로시저 호출 스택에 저장된다.

분할 정복 알고리즘을 의사 코드로 표현하면 다음과 같은 재귀 호출 형태를 띤다. 이는 분할 정복 알고리즘을 사용하는 대부분의 구현에서 기본적인 골격이 된다.

function conquer(x) is

if x는 쉽게 conquer할 수 있다면 // 문제가 충분히 작아서 바로 해결 가능하면

return conquer의 결과

else

(x1, x2, ...) := divide(x) // 문제를 여러 개의 작은 하위 문제로 분할

(y1, y2, ...) := (conquer(x1), conquer(x2), ...) // 각 하위 문제에 대해 재귀적으로 conquer 함수 호출

return synthesize(y1, y2, ...) // 각 하위 문제의 해답을 조합하여 원래 문제의 해답을 구함

예를 들어, 병합 정렬은 주어진 목록을 반으로 나누고, 각 부분을 재귀적으로 정렬한 뒤, 정렬된 두 부분을 합치는 방식으로 동작한다.

그러나 재귀 호출은 함수를 호출할 때마다 추가적인 오버헤드가 발생하여 실행 속도가 느려질 수 있다. 따라서 실행 속도를 높이거나 하위 문제 해결 순서를 직접 제어해야 하는 경우에는 재귀 호출 대신 스택이나 큐와 같은 자료구조를 사용하여 반복적인 방식으로 분할 정복 알고리즘을 구현하기도 한다.

5. 2. 명시적 스택

분할 정복 알고리즘은 일반적으로 재귀 함수를 사용하여 자연스럽게 구현되지만, 함수 호출에 따른 오버헤드나 재귀가 깊어질 경우 스택 메모리가 부족해지는 문제가 발생할 수 있다.

이러한 단점을 보완하고 실행 속도를 높이거나 하위 문제 해결 순서를 유연하게 선택하기 위해, 재귀 호출 없이 명시적인 자료구조를 사용하여 분할 정복 알고리즘을 구현하는 방법도 있다. 이 방식에서는 스택, 큐, 또는 우선순위 큐와 같은 자료구조에 해결해야 할 하위 문제들을 저장하고 관리한다.

이렇게 명시적인 자료구조를 사용하면 다음에 어떤 하위 문제를 해결할지 선택하는 데 더 많은 자유를 얻을 수 있다. 이는 특정 응용 프로그램에서 중요한 장점이 되는데, 예를 들어 너비 우선 탐색 방식의 처리가 필요하거나, 함수 최적화를 위한 분기 한정법처럼 특정 순서로 문제를 탐색해야 할 때 유용하다. 또한, 프로그래밍 언어가 재귀 호출을 지원하지 않는 경우에도 이 방식은 표준적인 해결책으로 사용될 수 있다. 특히 큐를 사용하는 경우는 속도 향상보다는 너비 우선 탐색처럼 하위 문제를 깊이 우선이 아닌 너비 우선 방식으로 탐색하고자 할 때 주로 선택된다.

5. 3. 스택 크기

분할 정복 알고리즘은 재귀 함수를 통해 구현되는 경우가 많다. 이때 재귀 호출이 깊어지면 스택에 많은 메모리가 필요하게 된다. 재귀적 구현에서는 재귀 스택에 충분한 메모리가 할당되어 있는지 확인해야 하며, 그렇지 않으면 스택 오버플로로 인해 실행이 실패할 수 있다. 시간 효율적인 분할 정복 알고리즘은 종종 비교적 작은 재귀 깊이를 가진다. 예를 들어, 퀵 정렬 알고리즘은 n개의 항목을 정렬하기 위해 log₂ n개 이하의 중첩된 재귀 호출만 필요하도록 구현할 수 있다.

스택 오버플로는 피하기 어려울 수 있는데, 많은 컴파일러가 재귀 스택을 메모리의 연속된 영역으로 가정하고 고정된 양의 공간을 할당하는 경우가 있기 때문이다. 또한 컴파일러는 반환 주소, 변경되지 않는 매개변수, 프로시저의 내부 변수 등 꼭 필요하지 않은 정보까지 재귀 스택에 저장할 수도 있다. 따라서 스택 오버플로의 위험을 줄이기 위해서는 재귀 프로시저의 매개변수와 내부 변수를 최소화하거나, 재귀 함수 대신 명시적인 스택 구조를 사용하는 방법을 고려할 수 있다.

5. 4. 기저 사례 선택

어떤 재귀 알고리즘에서든, 재귀를 종료하기 위해 직접 해결되는 작은 부분 문제인 '기저 사례'(base case)를 선택하는 데 상당한 자유가 있다.

가능한 가장 작거나 간단한 기저 사례를 선택하면 더 우아하고 일반적으로 더 간단한 프로그램을 만들 수 있다. 고려해야 할 사례가 적고 해결하기 더 쉽기 때문이다. 예를 들어, 고속 푸리에 변환 알고리즘은 입력이 단일 샘플일 때 재귀를 멈출 수 있고, 퀵 정렬 알고리즘은 입력이 빈 목록일 때 멈출 수 있다. 두 경우 모두 고려해야 할 기저 사례는 하나뿐이며, 특별한 처리가 필요 없다.

반면에, 재귀를 비교적 큰 기저 사례에서 멈추고 이 사례들을 비재귀적으로 해결하면 효율성이 종종 향상된다. 이는 하이브리드 알고리즘을 만드는 전략이다. 이 방법은 작업량이 거의 없는 재귀 호출의 오버헤드를 피할 수 있게 해주며, 해당 기저 사례에 대해 명시적 재귀보다 더 효율적인 특별한 비재귀 알고리즘을 사용할 수도 있다.

간단한 하이브리드 재귀 알고리즘을 위한 일반적인 절차는 '기저 사례 단락'(short-circuiting the base case)이라고도 부르는 방법이다. 이 경우, 다음 단계가 기저 사례가 될지를 함수 호출 전에 미리 확인하여 불필요한 함수 호출을 피한다. 예를 들어, 트리에서 자식 노드로 재귀한 다음 노드가 null인지 확인하는 대신, 재귀 전에 null인지 확인하면 일부 알고리즘에서 함수 호출의 절반을 줄일 수 있다. 분할 정복 알고리즘은 결국 각 문제를 많은 수의 기저 인스턴스로 줄이기 때문에, 이러한 기저 인스턴스 처리는 알고리즘의 전체 비용에 큰 영향을 미칠 수 있다. 특히 분할/결합 오버헤드가 낮을 때 더욱 그렇다. 이러한 점은 재귀가 컴파일러에 의해 구현되든 명시적인 스택으로 구현되든 마찬가지로 중요하다.

따라서, 예를 들어 퀵 정렬의 많은 라이브러리 구현은 정렬할 항목 수가 충분히 작아지면 간단한 루프 기반의 삽입 정렬 (또는 비슷한) 알고리즘으로 전환한다. 만약 빈 목록만이 유일한 기저 사례라면,

n

개의 항목이 있는 목록을 정렬할 때 아무것도 하지 않고 즉시 반환하는 호출이 최대

n

번 발생할 수 있다. 기저 사례를 크기 2 이하의 목록으로 늘리면 이러한 의미 없는 호출의 대부분이 제거된다. 일반적으로 2보다 큰 기저 사례는 함수 호출 오버헤드나 스택 조작에 소요되는 시간 비율을 줄이기 위해 사용된다.

또 다른 방법으로, 분할 정복 알고리즘을 계속 사용하는 큰 기저 사례를 사용할 수도 있다. 하지만 이때 미리 정해진 고정된 크기의 집합에 대해서는 알고리즘을 루프 언롤링하여 재귀, 루프 또는 조건문이 없는 코드로 완전히 풀어서 구현할 수 있다. (부분 평가 기술과 관련됨). 예를 들어, 이 접근 방식은 일부 효율적인 고속 푸리에 변환 구현에서 사용되는데, 여기서 기저 사례는 고정된 크기 집합에 대한 분할 정복 FFT 알고리즘의 언롤링된 구현이다.^[11] 소스 코드 생성 방법을 사용하면 이 전략을 효율적으로 구현하는 데 필요한 많은 수의 별도 기저 사례를 생성할 수 있다.^[11]

이 아이디어의 일반화된 버전은 재귀 "언롤링" 또는 "조대화"(coarsening)라고 하며, 기저 사례를 확대하는 절차를 자동화하기 위해 다양한 기술이 제안되었다.^[12]

5. 5. 중복되는 하위 문제

어떤 문제에서는 분할 정복의 재귀 과정에서 동일한 하위 문제를 여러 번 계산하는 경우가 있다. 예를 들어 특정 값을 계산하는 함수가 내부적으로 동일한 입력값을 가진 자기 자신을 다시 호출하는 경우가 이에 해당한다. 이 경우, 동일한 계산이 반복되어 전체 계산 비용이 지수적으로 증가하는 등 비효율이 발생할 수 있다.

이러한 중복 계산 문제를 해결하는 기법으로 메모이제이션(Memoization)이 있다. 메모이제이션은 한 번 계산한 하위 문제의 결과를 저장해 두었다가, 동일한 하위 문제가 다시 등장하면 계산 없이 저장된 결과를 사용하는 방식이다. 이를 통해 불필요한 반복 계산을 피하여 알고리즘의 효율성을 크게 높일 수 있다.

메모이제이션을 적극적으로 활용하는 대표적인 예가 동적 계획법(Dynamic Programming)이다. 동적 계획법은 가장 작은 하위 문제부터 해답을 계산하여 저장하고, 이 결과들을 조합하여 더 큰 문제의 해답을 순차적으로 구축하는 상향식 접근법이다. 이는 분할 정복의 기본 개념을 따르면서 중복되는 하위 문제 계산을 효율적으로 처리하는 기법이다.

참조

_[1] 서적 Fast Algorithms for Signal Processing Cambridge University Press 2014-05-14
_[2] 서적 Introduction to Algorithms https://books.google[...] MIT Press 2009-07-31
_[3] 간행물 Fundamental of Algorithmics Prentice-Hall 1996
_[4] 간행물 Introduction to the Design and Analysis of Algorithms Addison Wesley 2002
_[5] 간행물 Gauss and the history of the fast Fourier transform http://citeseerx.ist[...] IEEE ASSP Magazine 1984
_[6] 서적 The Art of Computer Programming: Volume 3 Sorting and Searching https://archive.org/[...] Addison-Wesley
_[7] 논문 Умножение многозначных чисел на автоматах
_[8] 간행물 The Art of Computer Programming: Volume 3, Sorting and Searching Addison-Wesley 1998
_[9] 서적 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039)
_[10] 간행물 The accuracy of floating-point summation https://pdfs.semanti[...] 1993
_[11] 논문 The design and implementation of FFTW3 http://www.fftw.org/[...] 2005-02
_[12] 간행물 Recursion unrolling for divide and conquer programs http://people.csail.[...] 2001

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com