1. 문제 : 겉보기에는 똑같은 동전이 n개 있습니다. 이 중에서 한 개는 싸고 가벼운 재료로 만들어진 ‘가짜 동전’입니다. 좌우 무게를 비교할 수 있는 양팔 저울을 이용해서 다른 동전보다 가벼운 가짜 동전을 찾아내는 알고리즘을 만들어 보세요.
  2. 문제 분석과 모델링
    1. 동전 n개 중에는 무게가 적게 나가는 가짜 동전이 한 개 섞여 있음
    2. 무게를 숫자로 보여 주는 디지털 저울이 있다면 동전 무게를 차례대로 하나씩 재서 가짜 동전을 간단히 판별할 수 있음
    3. 하지만 우리가 사용할 저울은 양팔에 물건을 올리면 어느 쪽이 더 무거운지와 가벼운지만 알려 주는 ‘양팔 저울’
  3. 정형화
  4. weigh() : a~b와 c~d의 무게를 비교하는 함수
  5. 하나씩 비교하는 알고리즘
  6. 반씩 그룹으로 나누어 비교하는 알고리즘
  7. 계산복잡도
    1. 알고리즘 1 : O(n), 순차 탐색과 유사
    2. 알고리즘 2 : O(log n), 이진 탐색과 유사
error: Content is protected !!