Brute-Force Search, Binary Search, Priority Queue

완전 탐색 알고리즘(Brute-Force Search)은 문제를 해결하기 위해 가능한 모든 경우의 수를 시험해보는 방법이다. 가장 기본적이면서 직관적인 알고리즘 접근 방식 중 하나로, 복잡한 문제 해결 방법이 바로 떠오르지 않을 때 유용하게 사용될 수 있다.

 

Brute-Force Search 는 문제의 가능한 모든 해를 체계적으로 나열하고 검사하여, 조건에 맞는 해를 찾아낸다. 이 방법은 문제의 크기가 작을 때 효과적이고 . 특정 문제에 국한되지 않고, 어떤 종류의 문제에도 적용 가능하다.

 

가능한 해의 수가 많아지면 계산 시간이 기하급수적으로 증가하는 단점이 있다 가능한 모든 경우의 수를 탐색하기 때문에, 문제의 규모가 커질수록 비효율적이고 시간이 많이 소요되기 때문이다.

 

Brute-Force Search는 비밀번호 크래킹(가능한 모든 문자열 조합을 시도하여 비밀번호를 찾아내는 과정)과 여러 도시를 순회하는 여행자 문제(TSP, Traveling Salesman Problem)에서 가능한 모든 경로를 탐색하여 최단 경로를 찾는 경우와 스도쿠, 큐브 퍼즐 등에서 가능한 모든 숫자나 위치의 조합을 시도하여 문제를 해결할 때 사용할 수 있다.

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # 원하는 값을 찾으면 그 위치를 반환
    return -1  # 값을 찾지 못하면 -1 반환

 

Brute-Force Search 방식은 문제를 해결하는 가장 확실한 방법 중 하나이지만, 대부분의 경우 더 효율적인 알고리즘을 고려하는 것이 좋다.

 

이진 탐색(Binary Search)은 정렬된 배열에서 특정한 값을 찾기 위한 효율적인 알고리즘이다. 이진 탐색은 분할 정복(Divide and Conquer) 전략을 사용하여, 탐색 과정에서 검사해야 할 요소의 수를 매 단계마다 절반으로 줄여 나간다. 이로 인해 탐색 시간을 대폭 줄일 수 있으며, 시간 복잡도는 O(log n)이다.

 

작동 원리

1. 분할(Divide): 배열의 중간에 위치한 원소를 선택하고, 이 원소를 피벗(pivot)으로 한다.
2. 정복(Conquer): 피벗과 탐색하고자 하는 값(target)을 비교한다.
   • 타겟 값이 피벗보다 작다면, 피벗의 왼쪽 부분에 대해서만 탐색을 계속한다.
   • 타겟 값이 피벗보다 크다면, 피벗의 오른쪽 부분에 대해서만 탐색을 계속한다.
3. 재귀(Recursive): 선택된 부분 배열에 대해 위의 과정을 반복한다.
4. 종료 조건:
   • 타겟 값이 피벗과 일치하는 경우, 해당 인덱스를 반환한다.
   • 탐색 범위가 더 이상 없는 경우(타겟 값을 찾지 못한 경우), -1 또는 탐색 실패를 나타내는 값이 반환된다.

이진 탐색을 사용하기 위해서는 배열이 미리 정렬되어 있어야 한다. 정렬된 데이터셋에서 특정 값의 존재 여부 확인, 값의 인덱스 찾기 등에 사용된다.

def binary_search(arr, target):
    left, right = 0, 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  # 타겟을 찾지 못한 경우, -1 반환

 

최소 힙(Min Heap)과 최대 힙(Max Heap)은 완전 이진 트리(complete binary tree)를 기반으로 하는 힙(Heap) 자료구조의 두 가지 주요 형태다. 힙은 각 노드가 하위 노드보다 우선순위가 높은 반정렬 상태(semi-ordered state)를 유지하는 트리 기반의 자료구조이다. 최소 힙과 최대 힙은 우선순위의 정의에 따라 분류되며, 우선순위 큐(priority queue) 구현에 자주 사용된다.

 

최소 힙(Min Heap)에서는 부모 노드의 키(key) 값이 자식 노드의 키 값보다 항상 작거나 같다. 즉, 트리의 루트에는 힙 내의 최소값이 위치한다. 따라서, 최소 힙을 사용하면 원소들이 항상 오름차순으로 정렬된 상태를 유지할 수 있다.

• insert: 새로운 요소를 추가할 때는, 트리의 가장 마지막에 요소를 추가한 후, 부모 노드와 비교하여 힙 속성을 만족시키도록 위치를 조정한다.
• extract-min: 힙에서 최소값(루트 노드)을 제거하고, 트리의 가장 마지막 요소를 루트로 이동시킨 후, 힙 속성을 만족시키도록 다시 조정한다.

최대 힙 (Max Heap)에서는 부모 노드의 키 값이 자식 노드의 키 값보다 항상 크거나 같다. 즉, 트리의 루트에는 힙 내의 최대값이 위치한다. 최대 힙을 사용하면 원소들이 항상 내림차순으로 정렬된 상태를 유지할 수 있다.

• insert: 새로운 요소를 추가할 때는, 트리의 가장 마지막에 요소를 추가한 후, 부모 노드와 비교하여 힙 속성을 만족시키도록 위치를 조정한다.
• extract-max: 힙에서 최대값(루트 노드)을 제거하고, 트리의 가장 마지막 요소를 루트로 이동시킨 후, 힙 속성을 만족시키도록 다시 조정한다.

힙은 배열로 효율적으로 구현될 수 있다.

• 부모 노드의 인덱스: ⌊ i−1 / 2 ​⌋
• 왼쪽 자식 노드의 인덱스: 2i + 1
• 오른쪽 자식 노드의 인덱스: 2i + 2

Priority Queue, 즉 우선순위 큐는 우선순위를 기준으로 요소들이 정렬되는 추상 자료형(abstract data type)이다. 이 자료구조에서는 각 요소가 우선순위와 연관되어 있으며, 우선순위가 가장 높은 요소가 가장 먼저 제거된다. 우선순위 큐는 다양한 방법으로 구현될 수 있지만, 힙(heap)을 사용하는 것이 가장 일반적이다.

 

우선순위 큐에서 요소의 추가나 제거는 요소의 우선순위에 따라 결정된다. 가장 높은 우선순위를 가진 요소가 가장 먼저 제거된다. 배열, 연결 리스트, 이진 힙(최소 힙 또는 최대 힙) 등 여러 가지 방법으로 구현할 수 있다. 이 중 이진 힙을 사용하는 것이 추가 및 제거 작업에 대해 O(log n)의 시간 복잡도를 제공하여 가장 효율적이다.

 

Priority Queue는 다익스트라 알고리즘, 프림 알고리즘과 같은 그래프 알고리즘, 스케줄링, 네트워크 트래픽 제어, 이벤트 관리 시스템 등 다양한 분야에서 활용된다.

• insert(item, priority): 주어진 우선순위와 함께 요소를 큐에 추가한다.
• pop(): 가장 높은 우선순위를 가진 요소를 큐에서 제거하고, 그 요소를 반환한다.
• peek(): 가장 높은 우선순위를 가진 요소를 큐에서 제거하지 않고 반환한다.
• isEmpty(): 큐가 비어 있는지 여부를 확인한다.

Python의 표준 라이브러리인 heapq 모듈은 최소 힙 기능을 제공하며, 최소 힙을 우선순위 큐로 사용할 수 있다. 최대 힙을 구현하려면 우선순위에 음수를 적용하거나 사용자 정의 객체를 사용할 수 있다.

import heapq

# 최소 힙을 사용한 우선순위 큐 예시
priority_queue = []
heapq.heappush(priority_queue, (1, 'Task 1'))  # 우선순위 1
heapq.heappush(priority_queue, (3, 'Task 3'))  # 우선순위 3
heapq.heappush(priority_queue, (2, 'Task 2'))  # 우선순위 2

# 가장 우선순위가 높은 요소를 제거하고 반환
print(heapq.heappop(priority_queue))  # 출력: (1, 'Task 1')