[perl] 검색 알고리즘

26 Dec 2023

perl

검색 알고리즘은 많은 정보가 존재하는 데이터베이스나 인터넷에서 원하는 정보를 빠르게 검색하는 데 사용됩니다. 이러한 알고리즘은 데이터의 구조와 탐색 방법에 따라 다양하게 구현됩니다.

이 블로그에서는 검색 알고리즘의 주요 유형과 각 유형의 장단점에 대해 살펴보겠습니다.

선형 검색

선형 검색은 리스트나 배열을 처음부터 끝까지 순차적으로 탐색하여 원하는 항목을 찾는 방법입니다. 이 방법은 간단하지만, 대량의 데이터에서 검색 속도가 느려지는 단점이 있습니다.

sub linear_search {
    my ($arr, $target) = @_;
    for (my $i = 0; $i < scalar(@$arr); $i++) {
        if ($arr->[$i] == $target) {
            return $i;  # 찾은 경우 인덱스 반환
        }
    }
    return -1;  # 찾지 못한 경우 -1 반환
}

이진 검색

이진 검색은 정렬된 배열에서 중간값을 기준으로 탐색 범위를 반으로 줄여가면서 원하는 항목을 찾는 방법입니다. 이진 검색은 선형 검색에 비해 훨씬 빠르게 동작하며, 데이터가 정렬되어 있어야 한다는 제약이 있습니다.

sub binary_search {
    my ($arr, $target) = @_;
    my $low = 0;
    my $high = scalar(@$arr) - 1;

    while ($low <= $high) {
        my $mid = int(($low + $high) / 2);
        if ($arr->[$mid] == $target) {
            return $mid;  # 찾은 경우 인덱스 반환
        } elsif ($arr->[$mid] < $target) {
            $low = $mid + 1;
        } else {
            $high = $mid - 1;
        }
    }
    return -1;  # 찾지 못한 경우 -1 반환
}

해쉬 검색

해쉬 검색은 해쉬 함수를 사용하여 데이터를 저장하고 검색하는 방법입니다. 해쉬 함수를 통해 각 항목에 고유한 키를 부여하고, 이 키를 기반으로 빠르게 해당 항목을 검색할 수 있습니다.

my %hash = (
    'apple' => 1,
    'banana' => 2,
    'cherry' => 3
);

# 값 찾기
my $value = $hash{'banana'};

트리 검색

트리 검색은 이진 트리, AVL 트리, 레드-블랙 트리 등 다양한 트리 구조를 활용하여 데이터를 저장하고 효율적으로 탐색하는 방법입니다. 트리 검색은 데이터 삽입과 삭제가 빈번한 경우에도 빠른 검색을 제공할 수 있습니다.

# 이진 트리 구현
package BinaryTree;

sub new {
    my $class = shift;
    my $self = {
        value => shift,
        left => undef,
        right => undef
    };
    bless $self, $class;
    return $self;
}

sub insert {
    my ($self, $value) = @_;
    if ($value < $self->{value}) {
        if ($self->{left}) {
            $self->{left}->insert($value);
        } else {
            $self->{left} = BinaryTree->new($value);
        }
    } elsif ($value > $self->{value}) {
        if ($self->{right}) {
            $self->{right}->insert($value);
        } else {
            $self->{right} = BinaryTree->new($value);
        }
    }
}

sub search {
    my ($self, $value) = @_;
    if ($self->{value} == $value) {
        return 1;  # 찾은 경우
    } elsif ($value < $self->{value} && $self->{left}) {
        return $self->{left}->search($value);
    } elsif ($value > $self->{value} && $self->{right}) {
        return $self->{right}->search($value);
    }
    return 0;  # 찾지 못한 경우
}

여기까지, 검색 알고리즘에 대한 간략한 소개를 살펴보았습니다. 각 알고리즘은 데이터의 구조와 특성에 따라 적절히 선택되어야 합니다. 앞으로 더 다양한 검색 알고리즘과 그 활용 사례에 대해 알아볼 예정입니다.

목차

선형 검색

이진 검색

해쉬 검색

트리 검색