알고리즘.

Apr 27 2023

프로그래밍이나 알고리즘적 사고가 처음이라면 배워야 할 두 가지 핵심 알고리즘은 이진 검색과 빠른 정렬입니다. 이러한 알고리즘은 컴퓨터 과학에서 널리 사용되며 많은 실제 응용 프로그램이 있습니다.

이 기사에서는 구현, 사용 사례 및 실제 응용 프로그램을 포함하여 이진 검색 및 빠른 정렬에 대한 자세한 가이드를 제공합니다. 또한 이러한 알고리즘과 작동 방식을 이해하는 데 도움이 되는 예제와 설명을 제공합니다.

따라서 초보자이든 숙련된 프로그래머이든 이 강력한 알고리즘에 대해 자세히 알아보고 코드와 실제 세계에서 문제를 해결하는 데 어떻게 도움이 되는지 읽어보세요.

알고리즘에 대해 자세히 알아보려면 Aditya Bhargava의 "Grokking Algorithms: 프로그래머 및 기타 호기심 많은 사람들을 위한 그림 가이드"라는 책을 읽어보십시오 .

Unsplash의 SCREEN POST 사진

이진 검색

이진 검색은 검색 구간을 반복적으로 반으로 나누어 각 단계에서 나머지 요소의 절반을 제거하는 검색 알고리즘입니다. 이 접근 방식은 로그 시간 복잡도가 O(log n). 이진 검색은 데이터베이스 검색, 컴퓨터 프로그램에서 특정 항목 찾기, 숫자 데이터 세트에서 값 찾기 등 많은 응용 프로그램에서 널리 사용됩니다.

구현

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

7in 의 인덱스를 찾으려면 [1, 2, 3, 4, 5, 6, 7, 8, 9]중간 요소인 와 비교하십시오 5. 보다 크면 5위쪽 절반에서 검색합니다 [6, 7, 8, 9]. 미만인 경우 8하단에서 검색합니다 [1, 2, 3, 4, 5, 6]. 을 찾으면 7인덱스는 입니다 6.

사용 사례

정렬된 목록에서 요소 검색 또는 정렬된 목록에서 요소의 인덱스 찾기: 이진 검색은 O(log n)시간 복잡도에서 두 작업을 모두 수행할 수 있습니다.
정렬된 목록에서 주어진 값에 가장 가까운 요소 찾기: 이진 검색을 사용하여 주어진 값과 같거나 바로 앞이나 뒤의 요소를 찾습니다.
오름차순으로 정렬된 다음 내림차순으로 정렬된 배열에서 피크 요소 찾기: 이진 검색을 사용하여 이웃보다 큰 피크 요소를 찾습니다.

이진 검색은 웹 페이지 및 의료 기록과 같은 대규모 데이터베이스를 효율적으로 검색하여 관련 결과를 사용자에게 반환합니다.
이 알고리즘은 컴퓨터 네트워크에서 네트워크 데이터 패킷의 정렬된 순서로 특정 데이터 패킷을 빠르게 찾고 금융 거래에서 대규모 데이터 세트의 특정 데이터를 기반으로 정보에 입각한 결정을 내리는 데 사용됩니다.
이진 검색은 주어진 모델에 대한 최적의 하이퍼파라미터를 찾기 위한 기계 학습과 대규모 데이터 세트에서 특정 유전자 또는 돌연변이를 식별하기 위한 DNA 시퀀싱에서도 사용됩니다.

빠른 정렬은 배열을 두 개의 하위 배열로 재귀적으로 분할하여 배열을 효율적으로 정렬하는 널리 사용되는 정렬 알고리즘입니다. 알고리즘은 배열에서 피벗 요소를 선택하고 나머지 요소를 피벗보다 작거나 같은 그룹과 피벗보다 큰 그룹의 두 그룹으로 나눕니다. 그런 다음 전체 배열이 정렬될 때까지 두 그룹을 재귀적으로 정렬합니다. 퀵 정렬은 분할 정복 전략으로 인해 평균 시간 복잡도가 O(n log n). 대용량 데이터 세트를 처리할 수 있으며 다양한 애플리케이션에서 일반적으로 사용됩니다.

구현

def quick_sort(arr):
    if len(arr) <= 1:
        return arrp
    else:
        pivot = arr[0]
        left = [x for x in arr[1:] if x <= pivot]
        right = [x for x in arr[1:] if x > pivot]
        return quick_sort(left) + [pivot] + quick_sort(right)

다음 요소를 포함하는 배열이 있다고 가정합니다. [9, 7, 5, 11, 12, 2, 14, 3, 10, 6].

빠른 정렬 알고리즘을 사용하여 어레이를 정렬하려면 다음 단계를 따르십시오.

배열의 첫 번째 요소를 피벗 요소(이 경우 )로 선택합니다 9.
배열을 두 개의 하위 배열로 분할합니다. 하나는 피벗보다 작거나 같은 요소가 있는 하위 배열이고 다른 하나는 피벗보다 큰 요소가 있는 하위 배열입니다.

[9, 7, 5, 11, 12, 2, 14, 3, 10, 6]
 ^ pivot
[7, 5, 2, 3, 6]   [9]   [11, 12, 14, 10]

[7, 5, 2, 3, 6]
 ^ pivot
[5, 2, 3, 6]   [7]
 ^ pivot
[2, 3]   [5]   [6]   [7]
 ^ pivot
[2]   [3]   [5]   [6]   [7]
[2, 3, 5, 6, 7]

[11, 12, 14, 10]
 ^ pivot
[10]   [11]   [12, 14]
               ^ pivot
[10]   [11]   [12]   [14]
[10, 11, 12, 14]

[2, 3, 5, 6, 7]   [9]   [10, 11, 12, 14]
[2, 3, 5, 6, 7, 9, 10, 11, 12, 14]

퀵 정렬은 컴퓨터 과학 교육 및 프로그래밍에 사용되는 고전적인 분할 정복 알고리즘입니다.
빠른 정렬은 임베디드 시스템 및 실시간 애플리케이션과 같이 메모리 사용량이 중요한 애플리케이션에서 유용합니다.

빠른 정렬은 대규모 데이터 세트 및 데이터 구조를 정렬하기 위해 데이터베이스 및 프로그래밍 언어에서 일반적으로 사용됩니다.
퀵 정렬은 시뮬레이션 및 실험에서 생성된 대규모 데이터 세트를 정렬하기 위해 과학 컴퓨팅 및 수치 분석에 사용됩니다.
빠른 정렬은 전자 상거래에서 사용자 선호도에 따라 제품, 리뷰 및 기타 데이터를 빠르게 정렬하는 데 유용합니다. 큰 카탈로그가 있는 온라인 소매업체에 유용합니다.

Unsplash에 있는 Viktor Ritsvall의 사진

이진 검색과 빠른 정렬은 모든 프로그래머가 알아야 하는 두 가지 기본 알고리즘입니다. 이진 검색은 컴퓨터 프로그램에서 특정 항목을 찾는 데 도움이 되는 검색 알고리즘이고, 퀵 정렬은 대용량 데이터 세트를 효율적으로 정렬할 수 있는 정렬 알고리즘입니다. 두 알고리즘 모두 데이터베이스 검색 및 금융 거래에서 기계 학습 및 DNA 시퀀싱에 이르기까지 수많은 실제 응용 프로그램이 있습니다. 이 기사에서는 구현, 사용 사례 및 실제 응용 프로그램을 포함하여 두 알고리즘에 대한 자세한 가이드를 제공합니다. 초보자이든 숙련된 프로그래머이든 이 강력한 알고리즘은 코드와 실제 세계에서 문제를 해결하는 데 도움이 될 수 있습니다. 알고리즘에 대해 더 알고 싶다면 책을 읽어보세요.Aditya Bhargava의 "Grokking Algorithms: 프로그래머 및 기타 호기심 많은 사람들을 위한 그림 가이드" .

다음 기사에서는 또 다른 유명한 알고리즘인 BFS(Breadth-First Search)에 대해 다룰 것입니다. 이 알고리즘은 그래프의 모든 정점을 탐색하는 데 사용됩니다.