이쿼카

I am an amazing Quokka.

9 minute read

이번엔 코딩 테스트에서 자주 출제 되는 이진 탐색에 대해서 개념과 함께 코드에 대해서도 알아보도록 하겠습니다.

1. 탐색이란?

프로그래밍에서 탐색이 필요한 이유

탐색은 방대한 데이터 중에서 내가 필요로 하는 데이터를 찾는 행위입니다. 그런데 이 탐색이 왜 프로그래밍에서 필요할까요?
그 이유는 컴퓨터 프로그램은 대부분 데이터에 기반해서 작동을 하며, 이 데이터에서 사용자가 필요로 하는 데이터를 찾는 작업이 필수적이기 때문입니다. 예를 들면 다음과 같습니다.

  • 데이터베이스에서 특정 회원의 정보를 찾아야 한다.
  • 웹 페이지에서 특정 회원의 정보를 찾아야 한다.
  • 게임에서 플레이어의 위치나 아이템을 찾아야 한다.
  • AI 모델에서 최적의 값을 찾거나, 패턴을 탐색해야 한다.

이처럼 필요한 정보를 즉시 찾아낼 수 있어야 프로그램이 제대로 동작하게 됩니다.

탐색의 중요성

탐색은 단순히 데이터를 찾는 행위를 넘어서, 소프트웨어의 성능, 효율성, 사용자 경험에 영향을 줍니다.

  1. 시간 복잡도의 핵심
    • 탐색 알고리즘은 보통 시간 복잡도로 성능이 평가됩니다.
    • 데이터가 커질수록 탐색 방법의 차이가 성능 차이로 직결됩니다.
  2. 데이터 구조와 함께 발전
    • 탐색 알고리즘은 데이터 구조(배열, 해시 테이블, 트리, 그래프 등)와 맞물려 발전했습니다.
    • 좋은 데이터 구조 없이는 효율적인 탐색이 불가능하고, 탐색 알고리즘 없이는 데이터 구조를 활용할 수 없습니다.
  3. 응용 분야의 다양성
    • 데이터베이스의 쿼리 처리
    • 웹 검색 엔진
    • 파일 시스템의 파일 탐색
    • 네트워크 라우팅 경로 탐색
    • AI 문제 (최적의 해 탐색)
  4. 사용자 경험과 직결
    • 사용자가 “검색” 버튼을 눌렀을 때 빠르게 결과가 나오는 것이 바로 탐색 알고리즘 덕분입니다.
    • 지연이 길어지면 서비스 품질이 떨어집니다.


2. 순차 탐색

우리가 공부할 이진 탐색 전에 알아볼 가장 간단한 탐색 방법은 순차 탐색으로 배열이나 리스트와 같은 선형 자료 구조 안에 있는 모든 데이터들을 하나씩 차례대로 확인하는 방법입니다. 보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용됩니다. 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 데이터를 찾을 수 있다는 장점이 있습니다.
예제 코드를 통해서 알아보도록 하겠습니다.


# 순차 탐색 소스코드 구현
def sequential_search(n, target, array):
    # 각 원소를 하나씩 확인하며
    for i in range(n):
        # 현재의 원소가 찾고자 하는 원소와 동일한 경우
        if array[i] == target:
            return i+1

print("생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요.")

input_data = input().split()
n = int(input_data[0]) # 원소의 개수
target = input_data[1] # 찾고자 하는 문자열

print("앞서 적은 원소 개수만큼 문자열을 입력하세요. 구분은 띄어쓰기 한 칸으로 합니다.")
array = input().split()

# 순차 탐색 수행 결과 출력
print(sequential_search(n, target, array))

위 코드는 리스트에 들어갈 원소의 개수와 함께 찾고자 하는 문자열을 입력으로 받습니다. 그리고 그 이후에는 리스트에 들어갈 원소들을 입력 받아 리스트에 넣어주고 순차 탐색을 진행하는 sequential_search 함수를 통해 리스트에서 찾고자 하는 문자열이 등장하면 해당 인덱스를 반환하는 코드입니다.


3. 이진 탐색

이제 본론인 이진 탐색에 대해서 공부해봅시다. 이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘입니다. 데이터가 무작위일 때는 사용할 수 없지만, 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있다는 특징이 있습니다. 그래서 이진 탐색을 적용하고자 할 때에는 무조건 정렬이 선행되어야 합니다. 이진 탐색은 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 특징이 있습니다.

이진 탐색은 위치를 나타내는 변수 3개를 사용하는데 탐색하고자 하는 범위의 시작점, 끝점, 중간점을 사용합니다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색 과정입니다. 다음 이미 정렬된 10 개의 데이터 중에서 값이 4인 원소를 찾는 예시를 살펴보겠습니다.

이진 탐색 과정

  • 리스트 : list = [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]
  • 찾고자 하는 값 : 4

Step 1.

  • 시작점 : 0
  • 끝점 : 9
  • 중간점 계산 : (시작점 + 끝점) // 2 -> (0+9) // 2 = 4
  • 중간값 : 리스트의 4번째 요소의 값이므로 8
  • 비교 : 4 < 8 이므로, 오른쪽 범위를 줄여야 합니다. 그러므로 끝점 업데이트를 진행합니다.
  • 끝점 업데이트 : 끝점을 중간점에서 1을 뺀 값으로 업데이트 해서 다음 과정을 진행합니다.

Step 2.

  • 시작점 : 0
  • 끝점 : 3
  • 중간점 계산 : (0+3) // 2 = 1
  • 중간값 : list[1] = 2
  • 비교 : 4 > 1 이므로, 왼쪼 범위를 줄여야 합니다. 그러므로 시작점 업데이트를 진행합니다.
  • 시작점 업데이트 : 시작점을 중간점에서 1을 더한 값으로 업데이트 해서 다음 과정을 진행합니다.

Step 3.

  • 시작점 : 2
  • 끝점 : 3
  • 중간점 계산 : (2+3) // 2 = 2
  • 중간값 : list[2] = 4
  • 비교 : 4 == 4 이므로 탐색 완료

전체 데이터의 개수는 10개이지만, 이진 탐색을 이용해 총 3번의 탐색으로 원소를 찾을 수 있었습니다. 이진 탐색은 한 번 확인할 때마다 확인하는 원소의 개수가 절반씩 줄어든다는 점에서 시간 복잡도가 $O(\log_{2} N)$입니다. 절반씩 데이터를 줄어들도록 만든다는 점은 앞서 다룬 퀵 정렬과 공통점이 있습니다.
이진 탐색을 구현하는 방법에는 2가지가 있는데 하나는 재귀 함수를 이용하는 방법이고, 다른 하나는 단순하게 반복문을 이용하는 방법입니다. 먼저 재귀 함수를 이용한 코드를 보도록 하겠습니다.

"""
10 7
1 3 5 7 9 11 13 15 17 19
4
"""

import sys

#이진 탐색 소스코드 구현(재귀 함수)
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 = map(int, input().split())
array = list(map(int, sys.stdin.readline().rstrip().split()))

# 이진 탐색 수행 결과 출력
result = binary_search(array, target, 0, n-1)

다음은 단순하게 반복문을 사용한 코드입니다. 실행 결과는 재귀 함수와 같습니다.

"""
10 7
1 3 5 7 9 11 13 15 17 19
4
"""

# 이진 탐색 소스코드 구현(반복문)
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
    
    # 만약 start 값이 end 값보다 커지게 되면 찾고자 하는 원소가 없다는 것이므로 None 반환
    return None

# n(원소의 개수)과 target(찾고자 하는 문자열)을 입력받기
n, target = 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)

4. 이진 탐색을 이용한 매개변수 탐색

코딩 테스트에서 이진 탐색(Binary Search)을 단독으로 묻는 문제는 드뭅니다. 대신, 이진 탐색의 원리를 응용하여 문제의 정답을 찾아내는 매개변수 탐색(Parametric Search)이 변별력을 기르는 핵심 유형으로 자주 출제됩니다.

4.1 매개변수 탐색(Parametric Search)이란?

매개변수 탐색은 “최적화 문제”를 “결정 문제(Yes or No)”로 바꾸어 푸는 강력한 알고리즘 기법입니다.

  • 최적화 문제: 주어진 조건에서 가능한 정답 중 최댓값 혹은 최솟값을 구하시오.
  • 결정 문제: 어떤 기준 값(Mid)이 주어졌을 때, 이 값이 “조건을 만족하는가? (Yes or No)”

일반적인 이진 탐색이 정렬된 배열에서 “특정 값(Target)의 위치”를 찾는 것이 목적이라면, 매개변수 탐색은 조건을 만족하는 최적의 경계값을 찾는 것이 목적입니다. 정답이 될 수 있는 값들의 범위를 이진 탐색으로 좁혀 나가면서, 조건을 만족하는 최대 또는 최소 지점을 찾아내는 원리입니다.

4.2 어떤 문제에서 사용해야 할까 (출제 시그널 파악)

코딩 테스트 지문을 읽을 때 다음 두 가지 시그널이 보인다면 매개변수 탐색을 강력하게 의심해 보아야 합니다.

지문의 핵심 키워드

조건을 만족하는 ~의 최댓값 혹은 최솟값을 구하시오.

이처럼 무언가의 최대/최소를 묻는 문제 중에서, 그 값을 하나씩 증가시키거나 감소시켜 보았을 때 어느 순간을 기점으로 “가능”에서 “불가능”으로 상태가 반전되는 구조라면 100% 매개변수 탐색 문제입니다.

입력 조건의 범위가 비정상적으로 클 때

탐색해야 하는 정답의 범위나 입력으로 주어지는 숫자의 범위가 10억, 20억 이상으로 매우 큰 경우가 많습니다. 이렇게 범위가 클 경우에는 일반적인 $O(N)$의 선형 탐색으로는 무조건 시간 초과가 발생하므로, 시간 복잡도를 $O(\log N)$으로 줄일 수 있는 매개변수 탐색이 필수적입니다.

4.3 매개변수 탐색을 설계하는 3가지 핵심 로직

매개변수 탐색 문제는 다음 3가지 단계만 거치면 기계적으로 풀어낼 수 있습니다.

  1. 정답이 될 수 있는 최소/최대 범위(Left, Right) 설정:

    정답이 될 수 있는 가장 작은 값을 left 가장 큰 값을 right로 설정합니다. 이 두 값의 중간값이 mid가 바로 우리가 검증해 볼 매개변수(Parameter)가 됩니다.

  2. 조건을 판별하는 is_possible(mid) 함수 설계:

    매개변수 탐색에서 가장 중요한 부분입니다. 현재 설정된 mid값을 기준으로 문제의 조건을 시뮬레이션했을 때, 조건을 만족하면 True 만족하지 못하면 False를 반환하도록 로직을 작성합니다.

  3. 이진 탐색 수행 및 최적해 갱신:

    is_possible(mid)의 결과에 따라 탐색 범위를 절반씩 날려버립니다. 조건을 만족할 때마다 answer 변수에 mid 값을 갱신해 두고, 더 최적의 값이 있는지 탐색을 계속 이어갑니다.

4.4 실전 코드 템플릿 및 주의사항

Python으로 매개변수 탐색을 구현할 때 사용하는 표준 템플릿입니다. 이 구조를 외워두면 어떤 문제든 is_possible 함수만 수정하여 대입할 수 있습니다.

# 조건을 만족하는지 확인하는 결정함수
def is possible(mid):
    # TODO: mid 값을 기준으로 문제의 조건을 시뮬레이션
    # 조건을 만족하면 True, 아니면 False 반환
    return True

def parametric_search():
    # Step1: 탐색 범위 초기화 (문제 조건에 맞게 설정)
    left = 0
    right = int(1e9)
    answer = 0

    # Step3: 이분 탐색 수행
    while left <= right:
        mid = (left + right) // 2

        #Step2: 결정 함수로 mid 값 검증
        if is_possible(mid):
            answer = mid
            left = mid +1
            되는 지 확인
        else:
            right = mid -1
    return answer

4.5 매개변수 탐색 대표 문제 풀이 및 복기: 나무 자르기

이진 탐색을 활용한 매개변수 탐색의 가장 대표적인 문제인 나무 자르기를 통해 실전 적용 과정을 살펴보도록 하겠습니다. 문제의 내용과 입출력은 다음과 같습니다.

  • 문제:

    나무꾼 미르코는 나무가 M미터 필요한데, 특수한 절단기를 가지고 있다. 나무꾼 미르코의 ​절단기는 높이 H를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다.

    예를 들어, 한 줄에 연속해있는 나무의 높이가 4, 10, 7, 6, 10 이라고 하자. ​나무꾼 미르코가​ 높이를 6으로 지정했다면, 나무를 자른 뒤의 높이는 4, 6, 6, 6, 6 이 될 것이고, ​나무꾼 미르코는 ​길이가 4인 나무와 1인 나무와 4​인 나무를 들고 집에 갈 것이다. (총 9미터를 집에 들고 간다) 절단기에 설정할 수 있는 높이는 0 이상의 정수이다. M미터의 이상의 나무를 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.​

  • 입력:

    첫 번째 줄에 나무의 수 N과 나무꾼 미르코​가 벌목해야 하는 나무의 길이 최솟값 M이 주어진다. 두 번째 줄에는 나무의 높이 H_i가 공백을 기준으로 N개 주어진다. 나무의 높이의 합은 항상 M보다 크거나 같기 때문에, 나무꾼 미르코​는 집에 필요한 나무를 항상 가져갈 수 있다.

    [제약 조건] 1 ≤ N ≤ 1\,000\,000 1 ≤ M ≤ 2\,000\,000\,000 0 ≤ H_i ≤ 1\,000\,000\,000 (1 \le i \le N)

  • 출력:

    나무꾼 미르코​가 M미터 이상의 나무를 집에 가져가기 위해서 설정해야하는 절단기 높이의 최댓값을 출력하시오.

4.5.1 문제 분석 및 출제 시그널 파악

이 문제에서 우리가 주목해야 할 출제 시그널은 다음과 같습니다.

  • 결정적인 시그널:

    “M 미터 이상의 나무를 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하시오.

  • 탐색 범위의 방대함:

    나무의 높이는 최대 $1,000,000,000$ 입니다. 이 높이를 1부터 10억까지 1씩 줄여가며 선형 탐색($O(N)$)을 한다면 무조건 시간 초과가 발생합니다. 따라서 탐색 범위를 절반씩 쪼개어 나가는 이진 탐색($O(\log N)$)이 필수적입니다.

4.5.2 상태 공간 정의 및 is_possible 함수 설계

앞서 배운 3단계 로직을 그대로 이 문제에 대입해 보도록 하겠습니다.

  • 매개변수: 절단기에 설정할 높이 H
  • 결정 문제로의 전환: “절단기 높이가 mid 일 때, 잘려진 나무들의 총합이 M미터”
  • is_possible 로직: 모든 나무를 순회하며 mid보다 큰 나무의 경우 나무 높이 - mid 값을 누적하여 더합니다. 이 총합이 M이상이면 True 아니면 False를 반환하도록 설계합니다.

4.5.3 전체 코드 정답

파이썬 환경에서 시간 초과를 방지하고 가독성을 높인 정답 코드입니다.

import sys

# Step 2: 조건을 판별하는 결정 함수
def is_possible(trees, target_wood, mid):
    total_wood = 0
    for tree in trees:
        if tree > mid:
            total_wood += (tree - mid)
            
    # 잘라낸 나무의 총합이 목표치(target_wood) 이상인지 확인
    return total_wood >= target_wood

def solve():
    input = sys.stdin.readline
    
    # N: 나무의 수, M: 필요한 나무의 길이
    n, m = map(int, input().split())
    trees = list(map(int, input().split()))
    
    # Step 1: 탐색 범위 설정 (최소 높이는 0, 최대 높이는 가장 높은 나무)
    left = 0
    right = max(trees)
    answer = 0
    
    # Step 3: 이분 탐색 수행
    while left <= right:
        mid = (left + right) // 2
        
        # 결정 함수를 통해 조건 만족 여부 확인
        if is_possible(trees, m, mid):
            answer = mid       # M미터 이상 가져갈 수 있으므로 정답 후보로 기록
            left = mid + 1     # '최댓값'을 찾아야 하므로 절단기 높이를 더 높여봄
        else:
            right = mid - 1    # 나무가 부족하므로 절단기 높이를 낮춰서 더 많이 잘라야 함
            
    print(answer)

if __name__ == '__main__':
    solve()

마치며

코딩 테스트 준비 및 알고리즘 재학습을 위하여 코딩 테스트에서 자주 출제되는 이진 탐색과 이진 탐색을 이용한 매개변수 탐색의 개념에 대해서 정리해 보았습니다.

긴 글 읽어주셔서 감사드리며 오타나 잘못된 내용이 있다면 댓글 달아주시기 바랍니다 감사합니다!

Comments

You May Also Enjoy

[AlgorithmTheory] 투포인터(Tow Pointers) 핵심 요약 및 실전 공략법

2 minute read

최근 다시 알고리즘 공부를 하며 다양한 문제를 풀고 있는데 난이도가 올라갈 수록 투포인터와 연계된 문제가 생각보다 많은 듯 하며, 투포인터의 개념은 조금만 공부하면 굉장히 쉽게 느껴져서 필요할 때만 대충 찾아보고 “아 이런거였지” 하며 반복하다 보니 머릿속에 제대로 정리가 안돼서 ...