꼭 알아야하는 코딩 테스트 유형: 13) #Binary_Search

• 이번에는 코딩 테스트에서 꼭 알아야하는 유형 중 하나인 이분 탐색(Binary Search)에 대해 알아보겠습니다. 이분 탐색은 정렬된 배열 또는 리스트에서 원하는 값을 찾는 데에 사용되는 강력한 알고리즘입니다. 이분 탐색은 매우 효율적이며, O(logN)의 시간 복잡도를 가지므로 많은 문제에서 활용됩니다.

 

이분 탐색(Binary Search)의 개념

 

• 이분 탐색은 주어진 정렬된 배열(또는 리스트)에서 중간값을 기준으로 찾고자 하는 값이 왼쪽 부분 배열에 위치하는지 오른쪽 부분 배열에 위치하는지를 판단하여, 찾고자 하는 값이 있을 범위를 반으로 줄여가며 검색합니다. 이 과정을 반복하여 최종적으로 원하는 값을 찾게 됩니다.
• 일반적인 이분 탐색의 과정은 다음과 같습니다.

 

1. 시작 인덱스(left)와 끝 인덱스(right)를 설정합니다.
2. 중간 인덱스(mid)를 계산하고, 중간 값과 찾고자 하는 값을 비교합니다.
3. 만약 중간 값이 찾고자 하는 값과 일치하면 검색을 종료합니다.
4. 만약 중간 값이 찾고자 하는 값보다 작으면, 시작 인덱스(left)를 mid+1로 업데이트합니다.
5. 만약 중간 값이 찾고자 하는 값보다 크면, 끝 인덱스(right)를 mid-1로 업데이트합니다.
6. 위의 과정을 시작 인덱스(left)가 끝 인덱스(right)보다 커질 때까지 반복합니다.

 

코딩 테스트에서의 이분 탐색 문제 접근 방법

 

• 코딩 테스트에서 이분 탐색 문제를 접했을 때 어떻게 접근해야 할까요? 다음은 일반적인 접근 방법입니다.

 

1. 문제 파악: 문제의 조건과 요구사항을 정확히 파악해야 합니다. 어떤 값을 기준으로 이분 탐색할 것인지, 어떤 조건에서 종료할 것인지 등을 확인해야 합니다.
2. 정렬: 대부분의 이분 탐색 문제는 정렬된 배열 또는 리스트에서 이루어지므로, 입력 데이터가 정렬되어 있는지 확인해야 합니다. 만약 정렬되어 있지 않다면, 데이터를 먼저 정렬해야 합니다.
3. 이분 탐색 구현: 위에서 설명한 이분 탐색 알고리즘을 구현합니다. 시작 인덱스(left)와 끝 인덱스(right)를 설정하고, 중간 인덱스(mid)를 계산하여 값을 비교하고 범위를 조정하는 과정을 반복합니다.
4. 종료 조건: 이분 탐색은 시작 인덱스(left)가 끝 인덱스(right)보다 커질 때까지 반복됩니다. 종료 조건을 설정하여 원하는 값을 찾거나, 원하는 값이 없는 경우에도 적절히 처리할 수 있도록 해야 합니다.
5. 문제 해결: 이분 탐색을 통해 원하는 값을 찾았다면 해당 위치나 결과값을 반환하거나 필요한 처리를 수행합니다.
6. 시간 복잡도 분석: 이분 탐색의 시간 복잡도는 O(logN)입니다. 따라서 입력 크기에 따라 얼마나 효율적인지 파악하고 최적의 알고리즘을 선택할 수 있어야 합니다.

• 이외에도 특정 문제 유형에 따라 추가적인 고려사항이 있을 수 있으므로, 문제의 요구사항과 제약조건에 맞게 접근 방법을 조정해야 합니다.

 

2512번: 예산

  문제  
 

• 국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것이다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정한다.

1. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.
2. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다.

 

• 예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120, 110, 140, 150이라고 하자. 이 경우, 상한액을 127로 잡으면, 위의 요청들에 대해서 각각 120, 110, 127, 127을 배정하고 그 합이 484로 가능한 최대가 된다. 
• 여러 지방의 예산요청과 국가예산의 총액이 주어졌을 때, 위의 조건을 모두 만족하도록 예산을 배정하는 프로그램을 작성하시오.

 
  해결 방법  
 

• 이 문제는 정부가 지방에 보낼 수 있는 총 예산이 주어지고, 각 지방의 요청 금액이 주어졌을 때, 상한선을 설정하여 최대한 많은 요청을 만족시키는 문제입니다.
• 문제의 접근 방식은 다음과 같습니다.

1. 문제 파악: 각 지방에서 요구하는 금액들 중 가장 큰 값을 상한선으로 설정합니다.
2. 정렬: 모든 지방의 요구 금액들을 오름차순으로 정렬합니다.
3. 이분 탐색 구현: 시작점은 0, 끝점은 가장 큰 요구 금액으로 설정하고, 이분 탐색을 시작합니다.
4. 중간 값 계산 및 비교: 중간값(mid)를 계산하고 그 값을 상한선으로 할 때 배정된 예산의 합계가 총 예산보다 작거나 같으면 결과값(result)를 업데이트하고 시작점(left)를 mid+1로 변경합니다.
5. 종료 조건: 위 과정을 시작 인덱스(left)가 끝 인덱스(right)보다 클 때까지 반복합니다.

N = int(input())
request = list(map(int,input().split()))
M = int(input())

left, right = 0, max(request)
result = 0

while left <= right:
    mid = (left + right) // 2
    total = sum(min(mid, x) for x in request)
    
    if total <= M:
        result = mid
        left = mid+1
    else: right = mid-1
        
print(result)

 

1253번: 좋다

  문제  

 

• N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.
• N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.
• 수의 위치가 다르면 값이 같아도 다른 수이다.

N = int(input())
numbers = sorted(list(map(int, input().split())))

count = 0
for i in range(N):
    left, right = 0, N-1
    while left < right:
        if numbers[left] + numbers[right] == numbers[i]:
            if i != left and i != right:
                count += 1
                break
            if i == left:
                left += 1
            elif i == right:
                right -= 1
        elif numbers[left] + numbers[right] < numbers[i]: left += 1
        else: right -= 1
            
print(count)

• 위 코드에서 while 반복문은 각 인덱스 i에 대해 numbers[i]가 다른 두 요소의 합으로 나타낼 수 있는지 확인하는 역할을 합니다. 만약 그러한 경우를 발견하면 카운트를 증가시키고 해당 인덱스에 대한 검사를 종료합니다.

 

• 이처럼 이분 탐색은 정렬된 데이터에서 특정 값을 찾거나, 최적화 문제 등에 널리 활용되며 매우 효율적인 알고리즘입니다. 이분 탐색에 익숙해지면, 많은 코딩 테스트 문제를 효과적으로 해결할 수 있습니다. 다양한 유형의 문제를 풀어보면서 이분 탐색에 대한 이해도를 높이고, 실제 코딩 테스트에서는 문제의 요구사항과 제약조건을 잘 파악하여 적절한 알고리즘을 선택하고 구현하는 능력이 중요합니다.
• 특히, 이분 탐색을 활용할 때는 검색 범위의 설정, 종료 조건의 정의, 그리고 중간값과 목표값 간의 비교 방식 등 세심한 주의가 필요합니다. 이들 요소를 잘 고려하면서 알고리즘을 구현한다면, 효율적이고 정확한 해결책을 도출해낼 수 있습니다.
• 마지막으로, 위에서 다룬 예시 문제들은 각각 다른 유형의 문제로서 이분 탐색을 활용하는 방법을 보여줍니다. '2512번: 예산' 문제는 최적화 문제를 해결하는데 이분 탐색이 어떻게 사용될 수 있는지 보여주며, '1253번: 좋다' 문제는 숫자 배열에서 특정 조건을 만족하는 요소를 찾는데 이분 탐색이 어떻게 사용될 수 있는지 보여줍니다.