[perl] 분할 정복 알고리즘

26 Dec 2023

perl

분할 정복 알고리즘은 큰 문제를 해결하기 쉬운 작은 문제로 분할하여 해결하는 알고리즘 설계 기법입니다. 이 알고리즘은 다음 세 단계로 진행됩니다.

분할(Divide): 해결할 문제를 작은 크기의 동일한 부분 문제로 분할합니다.
정복(Conquer): 각각의 부분 문제를 순환적으로 해결합니다. 부분 문제의 크기가 충분히 작지 않을 때는 순환 호출을 멈추고 직접적인 방법으로 해결합니다.
병합(Combine): 부분 문제의 해를 결합하여 원래 문제를 해결합니다.

이 알고리즘은 재귀적인 구조를 가지고 있어 간단하지만 강력한 방법으로, 대표적으로 퀵 정렬과 합병 정렬에서 사용됩니다.

퀵 정렬의 예시

퀵 정렬은 분할 정복 알고리즘을 사용하여 리스트를 정렬하는 알고리즘입니다. 이를테면, 다음과 같은 코드를 사용합니다.

sub quicksort {
    my @unsorted = @_;
    return @unsorted if @unsorted < 2;

    my $pivot = shift @unsorted;
    my @smaller = grep { $_ < $pivot } @unsorted;
    my @greater = grep { $_ >= $pivot } @unsorted;

    return (quicksort(@smaller), $pivot, quicksort(@greater));
}

여기서 quicksort 함수는 입력 리스트를 두 부분 리스트로 분할하고, 각각을 재귀적으로 정렬하여 병합하는 분할 정복 알고리즘을 구현한 것입니다.

분할 정복 알고리즘은 문제 해결에 요구되는 최소한의 시간과 공간을 활용하여 효율적인 알고리즘을 설계하는 데에 사용됩니다.

참고 자료

Introduction to Algorithms, Third Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.