[perl] 알고리즘 패러다임

26 Dec 2023

perl

알고리즘은 문제를 해결하는 절차를 기술한 것입니다. 알고리즘은 다양한 패러다임을 사용하여 문제를 해결할 수 있습니다. 여기서는 몇 가지 주요한 알고리즘 패러다임에 대해 살펴보겠습니다.

동적 프로그래밍

동적 프로그래밍은 하위 문제의 해답을 저장하고 재활용하여 문제를 해결하는 알고리즘 기법이다. 반복적으로 같은 하위 문제를 풀어야 할 때 효율적이며, 최적 부분 구조를 갖는 문제에 적합하다.

sub fib {
    my ($n) = @_;
    if ($n <= 1) {
        return $n;
    }
    my @dp = (0, 1);
    for my $i (2 .. $n) {
        $dp[$i] = $dp[$i-1] + $dp[$i-2];
    }
    return $dp[$n];
}

자세한 내용은 다음 참조를 확인하세요 동적 프로그래밍.

분할 정복

분할 정복은 문제를 일부분으로 나눠서 각각 해결한 뒤, 그 결과를 합쳐 전체 문제의 답을 얻는 알고리즘 기법이다. 주로 재귀 함수를 사용하여 구현한다.

sub merge_sort {
    my @list = @_;
    return @list if @list <= 1;

    my $middle = int(@list / 2);
    my @left = merge_sort(@list[0 .. $middle - 1]);
    my @right = merge_sort(@list[$middle .. $#list]);
    my @sorted = merge(\@left, \@right);
    return @sorted;
}

자세한 내용은 다음 참조를 확인하세요 분할 정복.

탐욕 알고리즘

탐욕 알고리즘은 각 단계에서 가장 좋은 선택을 하는 알고리즘 기법이다. 각 선택은 지역 최적이지만 최종 해결책이 전반적으로 최적이라는 보장이 없다.

sub knapsack {
    my ($capacity, $weights, $values) = @_;
    my $n = @$weights;
    my $result = 0;
    for my $i (0 .. $n-1) {
        if ($weights->[$i] <= $capacity) {
            $capacity -= $weights->[$i];
            $result += $values->[$i];
        }
    }
    return $result;
}

자세한 내용은 다음 참조를 확인하세요 탐욕 알고리즘.

그리디 알고리즘

그리디 알고리즘은 탐욕 알고리즘의 한 종류로, 각 단계에서 가장 좋은 선택을 하는 것이 전체적으로도 최적해를 구할 수 있는 알고리즘 기법이다. 탐욕 알고리즘과 비슷하지만 전체적으로 최적해를 보장한다.

sub activitySelection {
    my ($start, $finish) = @_;
    my $n = @$start;
    my $i = 0;
    my $result = 1;
    for (my $j = 1; $j < $n; $j++) {
        if ($start->[$j] >= $finish->[$i]) {
            $result++;
            $i = $j;
        }
    }
    return $result;
}

자세한 내용은 다음 참조를 확인하세요 그리디 알고리즘.

목차

동적 프로그래밍

분할 정복

탐욕 알고리즘

그리디 알고리즘