[알고리즘] 이진 탐색

yesjuhee·2023년 2월 4일
0

코테공부

목록 보기
6/12

이진 탐색 알고리즘

  • 순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법
  • 이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법
    • 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정함

이진 탐색의 시간 복잡도

  • 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 log2N\log_2N에 비례한다.
  • 즉 이진 탐색은 탐색 범위를 절반씩 줄이며, 시간 복잡도는 O(logN)`O(logN)` 을 보장한다.

이진 탐색의 구현

파이썬 - 재귀 함수 이용

# 이진 탐색 - 재귀 함수
def binary_search(array, target, start, end):
    if start > end:
        return None
    
    mid = (start + end) // 2
    
    if array[mid] == target:
        return mid
    elif array[mid] > target:
        return binary_search(array, target, start, mid - 1)
    else:
        return binary_search(array, target, mid + 1, end)

# n : 원소의 개수
# target : 찾고자 하는 값
n, target = list(map(int, input().split()))

# 전체 원소 입력
array = list(map(int, input().split()))

# 출력
result = binary_search(array, target, 0, n - 1)
if result == None:
    print("원소가 존재하지 않습니다.")
else:
    print(result + 1)

파이썬 - 반복문 이용

# 이진 탐색 - 반복문
def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        if array[mid] == target:
            return mid
        elif array[mid] > target:
            end = mid - 1
        else:
            start = mid + 1
    return None

# 입력
n, target = list(map(int, input().split()))
array = list(map(int, input().split()))

# 이진 탐색 수행 결과 출력
result = binary_search(array, target, 0, n - 1)
if result == None:
    print('원소가 존재하지 않습니다.')
else:
    print(result + 1)

C++ - 반복문 이용

#include <bits/stdc++.h>

using namespace std;

// 이진 탐색 소스코드 구현(반복문)
int binarySearch(vector<int>& arr, int target, int start, int end) {
    while (start <= end) {
        int mid = (start + end) / 2;
        // 찾은 경우 중간점 인덱스 반환
        if (arr[mid] == target) return mid;
        // 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
        else if (arr[mid] > target) end = mid - 1;
        // 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
        else start = mid + 1; 
    }
    return -1;
}

int n, target;
vector<int> arr;

int main(void) {
    // n(원소의 개수)와 target(찾고자 하는 값)을 입력 받기 
    cin >> n >> target;
    // 전체 원소 입력 받기 
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        arr.push_back(x);
    }
    // 이진 탐색 수행 결과 출력 
    int result = binarySearch(arr, target, 0, n - 1);
    if (result == -1) {
        cout << "원소가 존재하지 않습니다." << '\n';
    }
    else {
        cout << result + 1 << '\n';
    }
}

파이썬 이진 탐색 라이브러리

  • bisect_left(a, x) : 배열 a의 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스를 반환
  • bisect_right(a, x) : 배열 a의 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽 인덱스를 반환
  • bisect을 이용하여 값이 특정 범위에 속하는 데이터 개수 구하기
    # 값이 특정 범위에 속하는 데이터 개수 구하기
    
    from bisect import bisect_left, bisect_right
    
    # 값이 [left_value, right_value]인 데이터의 개수를 반환하는 함수
    def count_by_range(a, left_value, right_value):
        right_index = bisect_right(a, right_value)
        left_index = bisect_left(a, left_value)
        return right_index - left_index
    
    # 배열 선언
    a = [1, 2, 3, 3, 3, 3, 4, 4, 8, 9]
    
    # 값이 4인 데이터 개수
    print(count_by_range(a, 4, 4))
    
    # 값이 [-1, 3] 범위에 있는 데이터 개수
    print(count_by_range(a, -1, 3))
  • 파라메트릭 서치 : 최적화 문제를 결정 문제로 바꾸어 해결하는 기법
    • 예시 : 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제
  • 일반적으로 코딩 테스트에서 파라메트릭 서치 문제는 이진 탐색을 이용하여 해결할 수 있음

이진탐색 문제

문제1 : 떡볶이 떡 만들기


문제 해결 아이디어

  • 적절한 높이를 찾을 때까지 이진 탐색을 수행하여 높이 H를 반복해서 조정하면 된다.
  • ‘현재 이 높이로 자르면 조건을 만족할 수 있는가?’를 확인한 뒤에 조건의 만족 여부(”예” 혹은 “아니오”)에 따라서 탐색 범위를 좁혀서 해결할 수 있다.
  • 절단기의 높이는 0부터 10억까지의 정수 중 하나로, 이렇게 큰 탐색 범위를 보면 가장 먼저 이진 탐색을 떠올려야한다.

솔루션 코드

# 떡볶이 떡 만들기 : 답안 예시

# 입력
n, m = map(int, input().split())
array = list(map(int, input().split()))

# 절단기 길이의 시작점과 끝점 설정
start = 0
end = max(array)

# 이진탐색 수행
result = 0
while(start <= end):
    total = 0
    mid = (start + end) // 2
    for x in array:
        # 잘랐을 때 떡의 양 계산
        if x > mid:
            total += x - mid
    # 떡의 양이 모자란경우 -> 절단기의 크기 줄이기(왼쪽 탐색)
    if total < m:
        end = mid - 1
    # 떡의 양이 같거나 많은 경우 -> 오른쪽 부분 탐색
    else:
        result = mid
        start = mid + 1

print(result)

문제2 : 정렬된 배열에서 특정 수의 개수 구하기


문제 해결 아이디어

  • 선형탐색 → 시간초과
  • 데이터가 정렬되어 있기 때문에 이진탐색 이용 가능

솔루션 코드

from bisect import bisect_left, bisect_right

# 값이 [left_value, right_value]인 데이터의 개수를 반환하는 함수
def count_by_range(a, left_value, right_value):
    right_index = bisect_right(a, right_value)
    left_index = bisect_left(a, left_value)
    return right_index - left_index

n, x = map(int, input().split())
array = list(map(int, input().split()))

count = count_by_range(array, x, x)

if count == 0:
    print(-1)
else:
    print(count)
profile
반성은 하되 후회하지 않는다😎

0개의 댓글