[응용 문제] 가짜 동전 찾기 알고리즘

문제

좌우 무게를 비교할 수 있는 양팔 저울을 이용해 겉보기에 똑같은 동전 n개 중, 싸고 가벼운 재료로 만들어진 가짜 동전을 찾아라.

 

조건

저울질에 해당하는 부분은 아래 함수와 같다. 구현하고자 하는 알고리즘은 아래의 weight 함수를 통해 가짜 동전의 위치를 찾아야 한다.

def weight(a, b, c, d):
    fake = 29
    if a <= fake <= b:
        return -1 # a와 b 사이에 가짜 동전이 있음
    if c <= fake <= d:
        return 1 # c와 d 사이에 가짜 동전이 있음

    return 0 # 저울에 올린 동전 중 가짜 동전이 없음

 

방법 1. 한 개씩 비교

순차 탐색과 유사한 방식으로 가짜 동전을 찾는다.

def find_fake_coin_selection(start, end):
    for i in range(start + 1, end + 1):
        result = weight(start, start, i, i)
        if result > 0:
            return i
        elif result < 0:
            return start
    return -1

 

방법 2. 반씩 나눠 비교

재귀 호출을 이용한다.

def find_fake_coin_divide(start, end):
    if start == end:
        return start

    mid = (end - start + 1) // 2
    f_end = start + mid - 1
    b_start = start + mid
    b_end = b_start + mid - 1

    if weight(start, f_end, b_start, b_end) < 0:
        return find_fake_coin_divide(start, f_end)
    elif weight(start, f_end, b_start, b_end) > 0:
        return find_fake_coin_divide(b_start, b_end)
    else:
        return end