[ALGORITHMS]문제 17 가짜 동전 찾기 알고리즘

문제 17

가짜 동전 찾기 알고리즘

겉보기에는 똑같은 동전이 n개 있습니다. 이중에서 한 개는 싸고 가벼운 재료로 만들어진 '가짜 동전'입니다. 좌우 무게를 비교할 수 있는 양팔 저울을 이용해서 다른 동전보다 가벼운 가짜 동전을 찾아내는 알고리즘을 만들어보세요.

1. 문제 분석과 모델링

동전 n개 중에는 무게가 적게 나가는 가짜 동전이 한 개 섞여 있습니다. 무게를 숫자로 보여주는 디지털 저울이 있다면 동전 무게를 차례대로 하나씩 재서 가짜 동전을 간단히 판별 할 수 있습니다. 하지만 우리가 사용할 저울은 양팔에 물건을 올리면 어느 쪽이 더 무거운지와 가벼운지만 알려주는 양팔저울입니다.

문제를 좀 더 정형화 해보면, 동전 개수는 n개이므로 왼쪽에서 오른쪽으로 동전을 일렬로 나열한 다음 맨 왼쪽을 0번으로 하여 차례대로 번호를 붙여 봅시다.

그럼 가장 오른쪽에 있는 동전은 n-1번이 됩니다.

정리하면, 0번부터 n-1번까지 동전이 있고 이 중에 가짜동전이 한개 있는데

우리가 만들 알고리즘은 양팔 저울로 저울질하여 가짜 동전의 위치번호를 알아내는 것입니다.

'저울질'에 해당하는 기능을 프로그램으로 구현할 수 있는 함수를 하나 만들겠습니다.

def weigh(a,b,c,d):

weigh() 함수는 a부터 b까지 동전을 양팔 저울의 왼쪽에, c부터 d까지 동전을 저울의 오른쪽에 올리고 저울질 하는 함수입니다. 이 때 비교하는 동전의 갯수는 같다고 가정하였습니다.(b-a=d-c)

이 함수 안에 변수 fake를 만들고 우리가 찾아야 할 가짜 동전의 위치를 저장합니다.

가짜 동전 찾기 알고리즘은 fake 변수의 값을 직접 알 수는 없고, weigh()함수를 호출해서 이 값을 찾아야만합니다.

weigh() 함수의 결과값은 -1,0,1 세 가지중 하나 입니다. 

-a~b 쪽이 가볍다면 a와 b 사이에 가짜 동전이 있다는 뜻이고, 결괏값으로 -1을 돌려줍니다. 

-마찬가지로 c~d쪽이 가볍다면 c와 d사이에 가짜동전이 있다는 뜻이고, 결과값으로 1을 돌려줍니다. 

-양 쪽 무게가 같다면 어느 쪽도 가짜 동전이 없다는 뜻이고, 결과 값으로 0을 돌려줍니다. 이 때는 저울에 올리지 않은 동전 중에 가짜 동전이 있다는 의미가 됩니다.

2. 방법 1: 하나씩 비교하기

동전 n개에 0부터 n-1까지 번호를 매기고 weigh() 함수를 이용해서 각 동전의 무게를 비교할 수 있도록 모델링을 마쳤습니다.

무게가 적게 나가는 가짜 동전이 한개만 있다고 했으므로 각 동전의 무게를 비교해서 가벼운 동전이 나온다면 그 동전이 바로 가짜 동전입니다. 0번 동전을 저울의 왼쪽에 올려놓고, 오른편에는 1번동전부터 차례로 바꿔가면서 저울질해보면 가짜 동전을 쉽게 찾을 수 있습니다.

0번과 1번 동전을 비교하는 첫 번째 저울질에서 왼쪽이 가볍다면 0번 동전이 가짜 동전이고, 오른쪽이 가볍다면 1번 동전이 가짜 동전입니다. 두 동전의 무게가 같다면 둘 다 가짜 동전이 아니므로 오른쪽에 2번 동전을 올리고 이 과정을 반복합니다

이렇게 저울질을 반복하면 n-1이 가짜 동전일경우(최악일 경우) 저울질을 n-1번해야 가짜 동전을 찾을 수 있습니다

* 가짜 동전을 찾는 알고리즘 1

3. 방법 2: 반씩 그룹으로 나누어 비교하기

앞에 보인 알고리즘으로도 가짜 동전을 쉽게 찾아 낼수 있습니다. 

하지만 저울질을 훨씬 덜 하고도 가짜 동전을 찾아낼 수 있는 방법이 있습니다.

아이디어는 바로 동전을 절반씩 나눠서 무게를 재보는 것입니다.

주어진 동전을 절반씩 두 그룹으로 나눠서 양팔 저울에 올렸을 때 한쪽이 가볍다면 그 가벼운 쪽에 가짜동전이 있다는 뜻입니다. 따라서 반대쪽에 있는 절반의 동전은 더는 생각할 필요가 없습니다. 가벼운 쪽에 있는 동전만을 대상으로 다시 가짜 동전을 찾으면 됩니다.

남은 동전 개수가 홀수 일때는 어떻게 반으로 나눌까요? 예를 들어 가짜동전 후보로 동전이 7개 남았다고 가정해 보면 7개는 홀수이므로 똑같은 수의 두 그룹으로 나누는것은 불가능합니다.

하지만 3개, 3개, 1개 이렇게 세 그룹으로 나눌 수 있습니다. 

세 그룹으로 나눈 후 개수가 세개로 같은 두 그룹만 저울에 올려보겠습니다.

왼쪽이 가볍다면 왼쪽에 올린 동전 3 개중 가짜 동전이 있을겁니다

오른쪽이 가볍다면 오른쪽에 올린 동전 3개 중 가짜 동전이 있을겁니다.

두 그룹의 무게가 같다면 저울에 올리지 않은 나머지 동전 하나가 가짜 동전이라는 뜻이 됩니다.

* 가짜 동전을 찾는 알고리즘 2

4. 알고리즘 분석

이 문제의 알고리즘 효율성을 '저울질 횟수'를 기준으로 생각해 보겠습니다.

알고리즘1은 저울질이 최대 n-1번이 필요하므로 계산복잡도가 O(n)입니다

알고리즘2는 저울질이 n개를 절반씩 나누어 후보를 좁히므로 계산복잡도가 O(logn)입니다

알고리즘을 보았을때 리스트 탐색문제랑 가짜 동전 문제는 구조가 비슷한 문제라고 볼 수 있습니다

읽어주셔서 감사합니다