보통 원하는 원소를 찾고자 할 때 처음부터 끝까지 탐색하는 선형 탐색을 주로 사용한다.

선형 탐색은 데이터의 크기가 너무 크지 않다면 딱히 고려할 조건이 없기 때문에 구현이 쉽기 때문이다.

하지만 데이터의 크기가 너무 커진다면 얘기가 달라진다.

그래서 나온 탐색 방법이 이진 탐색이다.(이분 탐색도 같은 말)

먼저 기본적인 개념은 순차적으로 정렬이 된 상태에서 특정 원소를 찾을 때까지 범위를 절반씩 줄이고 더 이상 찾을 범위가 없으면 해당 원소는 없다고 판단하는 알고리즘이다.

N개의 Data가 있을 때 범위를 절반씩 줄여나가므로 O(logn)의 아주 효율적인 시간 복잡도를 가지는데 여기서 중요한 점은 정렬된 상태여야 한다는 것이다.

왜냐하면 범위를 줄여나갈 때 찾고자 하는 원소와 현재 범위의 중간값을 비교해서 일치하면 중단, 일치하지 않으면 절반에 해당하는 범위엔 찾고자 하는 원소가 없다는 전제하에 범위를 줄여나가는 방식인데 정렬된 상태가 아니라면 이처럼 범위를 줄여나갈 수가 없다.

따라서 정렬된 Data를 탐색하거나 정렬하여 탐색할 수 있는 범위가 주어진다.

참고로 Python의 sort함수를 쓰면 O(nlogn)의 시간 복잡도를 가지므로 100만의 Input정도는 충분히 정렬 후 탐색할 수 있다.

그림의 예시를 따라가다 보면 쉽게 이해할 수 있을 것이다. (예시는 오름차순 리스트를 하며 내림차순은 반대로 하면 된다)

먼저 리스트의 전체 범위에서 시작해야 하므로 Left와 Right 두 개의 변수가 필요하다.

Left는 시작을 뜻하는 0(0번째 인덱스), Right는 끝을 뜻하는 len(data)-1로 선언하면 된다.

이제 아주 간단한 사전 준비는 끝났다.

Left와 Right의 위치가 역전된다면 더 이상 탐색할 범위가 없다는 뜻이므로 Left <= Right인 동안 반복을 계속 돌려주면 된다.

예시로 2와 7을 찾도록 해보겠다.

빨간색 화살표는 중앙값(변수명은 mid)을 뜻하고 찾고자 하는 원소가 mid에 있는 원소보다 작으므로 왼쪽 범위를 찾아야 한다는 뜻이 된다.

이때 이미 mid에 위치한 원소는 탐색했으므로 Right는 mid-1로 변경해서 조금이라도 탐색 횟수를 줄여준다.

Right=mid-1로 범위를 바꾼 뒤 다시 중앙값(mid)을 비교해보면 2를 찾을 수 있다.

해당 위치의 인덱스를 저장한 뒤 반복문을 빠져나오면 된다.

다음은 리스트에 없는 7을 찾아보겠다.

찾고자 하는 원소가 중앙값보다 크므로 오른쪽 범위에 있단 의미고 마찬가지로 중앙값은 탐색했으므로 탐색 횟수를 줄이기 위해 Left는 mid+1로 변경한다.

오른쪽 범위로 이동해서 다시 중앙값을 비교해보니 찾고자 하는 원소보다 중앙값이 더 크다.

이 말은 왼쪽 범위에 있단 뜻이므로 Right를 mid-1로 변경한다.

다시 왼쪽 범위로 이동해서 중앙값을 비교해보니 찾고자 하는 원소가 중앙값보다 더 크다.

이 말은 중앙값보다 오른쪽 범위에 있단 뜻이므로 Left는 mid+1로 변경한다.

이때 Left는 Right보다 커져서 역전되므로 결국 원소를 찾지 못한 채 반복문을 빠져나오게 된다.

이 알고리즘이 이진 탐색이며 7개의 Data에서 2를 찾는데 2번 연산, 7이 있는지 확인하는데 3번 연산밖에 하지 않았다.

만약 선형 탐색이었다면 최악의 경우 7번(Data의 크기만큼)의 연산을 할 것이고 확실히 이진 탐색을 통해 연산 횟수가 줄어든 것을 알 수 있다.

지금은 Data의 크기가 작기 때문에 몇 번 차이가 없지만 Data의 크기가 막대하게 커지면 상당히 효율적인 알고리즘이란 사실을 체감할 수 있을 것이다.

다음은 위의 설명대로 구현한 전체 코드이다.

data=[1,2,4,5,6,8,9]

def binary(n):
    index=-1
    left=0
    right=len(data)-1
    
    print("이진 탐색 과정 :",end=" ")

    while left<=right:
        mid=(left+right)//2
        print(data[mid],end=" ")
        if data[mid]==n:
            index=mid
            break
        elif n<data[mid]:
            right=mid-1
        else:
            left=mid+1
    print()
    return index

first=binary(2)

if first==-1:
    print("없는 원소입니다.")
else:
    print(first,"번째 인덱스에 있습니다.")

second=binary(7)

if second==-1:
    print("없는 원소입니다.")
else:
    print(second,"번째 인덱스에 있습니다.")

초기 Index는 -1로 지정하고 찾는 원소가 있다면 해당 원소의 인덱스로 갱신한다.

즉 여전히 Index가 -1이라면 찾는 원소가 없단 뜻이다.

그림을 참고하여 코드를 한 줄씩 따라가다 보면 쉽게 이해할 수 있을 것이다.

혹시나 해서 알고리즘 구현 자체를 접한 지 얼마 안 된 사람들께 덧붙이자면 이번 코드에서는 예시를 위해 인덱스를 반환하도록 구현했지만 당연하게도 각자 접하는 문제에 맞게끔 변형하여 구현해야 된다.

끝으로 이진탐색을 연습할 수 있는 문제를 몇가지 추천한다.

https://www.acmicpc.net/problem/1920

https://www.acmicpc.net/problem/1654

https://www.acmicpc.net/problem/1072

전형적으로 이진 탐색을 사용하는 문제이다.

혹시 이진 탐색을 처음 접하거나 익숙하지 않다면 관련 포스팅을 보고 이해한 뒤 문제를 푸는게 좋을 것 같다.

2021.12.02 - [알고리즘/알고리즘 강의] - (알고리즘) 이진탐색 / 이분탐색 (Binary Search)

문제 풀이

문제에서 전체 게임 횟수 : X, 이긴 게임 횟수 : Y, 승률 : Z이다.

주의해야 할 조건은 3가지다.

1. 승률을 뜻하는 Z는 소수점을 버린다.(반올림이 아니다)
2. Z가 절대 변하지 않으면 -1을 출력한다.
3. X는 최대 1,000,000,000 (10억)까지 가능하다.

Z에 대한 식을 나타내 보면 Z=(Y*100)/X이고 a만큼 수행했을 때 Z+1=((Y+a)*100)/(X+a)가 성립하는 최소 a를 구하는 문제이다. (승률 = 이긴 횟수/전체 횟수)

참고로 Python의 계산 방식 때문인지 처음에 Z=(Y//X)*100로 작성했더니 틀렸었다.

꼭 Z=(Y*100)//X로 작성해야하고 이 부분에 대해서 정확히 아시는 분이 계시다면 피드백 해주시면 감사합니다!!

이때 Z가 99 이상이라면 승률은 절대 변하지 않으므로 -1을 출력하고 98일 때 생각하면 X번만큼 추가할 때 99로 변하기 때문에 최대 X번까지만 반복하면 된다는 것을 알 수 있다.

이때 X는 최대 10억까지 가능하므로 순차적으로 탐색하는 O(n)의 시간 복잡도를 적용한다면 반드시 시간 초과가 날 수밖에 없다.

즉 1부터 X까지 오름차순인 상태에서 탐색 가능한 이분 탐색(이진 탐색)을 적용하면 풀 수 있을 것이다.

다음은 전체 코드다.

x,y=map(int,input().split()) 
z=(100*y)//x 
left=0 
right=x 
res=x 
if z>=99: 
    print(-1)
else: 
    while left<=right: 
        mid=(left+right)//2 
        if (100*(y+mid))//(x+mid)>z: 
            res=mid 
            right=mid-1 
        else: 
            left=mid+1
    print(res)

res는 정답인 최소 게임 수를 의미하는 변수로 최대 X번을 저장해놓고 더 작은 수가 있으면 갱신하는 방식으로 구현하였다.

승률이 99 이상이면 바로 -1을 출력하고 98 이하라면 이진 탐색을 실행한다.

초기 left는 0, right는 X로 설정하고 left와 right가 역전되지 않을 때까지 반복한다.

이때 left와 right 중간값을 기준으로 승률(Z)이 변하면 res를 갱신한 뒤 right는 중간값-1로, 변하지 않으면 left를 중간값+1로 변경함으로써 탐색해야 되는 범위를 절반씩 줄여준다.

즉 탐색 범위가 N이라면 범위를 절반씩 줄이므로 O(logn)의 시간 복잡도를 갖고, 10억의 Input이 들어와도 충분히 연산 가능해진다.

※조건을 잘 보고 Input의 크기에 따라 적절한 알고리즘을 적용하는 것이 중요한 것 같다.※