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

문제 17. 가짜 동전 찾기 알고리즘

 

방법 1. 하나씩 비교하기 hmmm

- weigh(a, b, c, d) 함수 : 양팔 저울

: fake = k로 가짜 동전 위치 저장함

: -1 (a~b) < (c~d) -> (a~b)쪽에 가짜 동전

: 0 (a~b) = (c~d) -> 가짜 동전 X

: 1 (a~b) > (c~d) -> (c~d)쪽에 가짜 동전

(fake 위치와 비교하여 -1, 0, 1 출력함)

 

여기까진 쉬움

def weigh(a, b, c, d):
  fake = 30
  if a <= fake <= b:
    return -1
  elif a and c <= fake and b and d >= fake:
    return 0
  elif c <= fake <= d:
    return 1

* find_fakecoin(start, end)

-> for문을 이용해 위치를 찾아간다. 

올 풀었다. 

def weigh(a, b, c, d):
  fake = 30
  if a <= fake <= b:
    return -1
  elif a and c <= fake and b and d >= fake:
    return 0
  elif c <= fake <= d:
    return 1

def find_fakecoin(start, end):
  #예를 들면 (0, n)
  for i in range(start+1, end):
    result = weigh(start, start, i, i)
    if result == -1:
      return start
    elif result == 1:
      return i     
    
  return "No fake coin"

print(find_fakecoin(0, 33))

 

cf) 순차 탐색 

def search_list(a, x):
  n = len(a)
  for i in range(0, n):
    if x == a[i]:
      return i

  return -1

v = [18, 22, 1, 10, 5]
print(search_list(v, 18))

예제 코드

def weigh(a, b, c, d):
  fake = 29
  if a <= fake and fake <= b:
    return -1
  if c <= fake and fake <= d:
    return 1
  return 0

def find_fakecoin(left, right):
  for i in range(left +1, right+1):
    result = weigh(left, left, i, i)
    if result == -1:
      return left
    elif result == 1:
      return i
  return -1

n = 100
print(find_fakecoin(0, n-1))

방법 2. 반씩 나누어 비교하기

 

 

cf) 이분 탐색

def binary(a, x, start, end):
  mid = (start + end) // 2
  if x == a[mid]:
    return mid
  elif x > a[mid]:
    return binary(a, x, mid +1, end)
  else:
    return binary(a, x, start, mid-1)

def binary_search(a, x):
  return binary(a, x, 0, len(a) -1)


a = [1, 2, 3, 4, 5, 6]
print(binary_search(a, 1))

 

알고리즘

def weigh(a, b, c, d):
  fake = 29
  if a <= fake and fake <= b:
    return -1
  if c <= fake and fake <= d:
    return 1
  return 0

def find_fakecoin(left, right):
  if left == right:
    return left
  half = (right - left + 1) // 2
  g1_left = left
  g1_right = left + half - 1
  g2_left = left + half
  g2_right = g2_left + half - 1

  result = weigh(g1_left, g1_right, g2_left, g2_right)
  if result == -1:
    return find_fakecoin(g1_left, g1_right)
  elif result == 1:
    return find_fakecoin(g2_left, g2_right)
  else:
    return right

n = 100
print(find_fakecoin(0, n-1))