Python algorithm 개념 및 실습 - 가짜 동전

알고리즘이란 ?

• 어떤 일을 하기 위한 명령의 집합
• 문제 해결 방법을 추상화하여 각 절차를 논리적으로 기술해 놓은 것
• 어떤 문제를 해결하기 위한 절차나 방법

 

알고리즘 복잡도

• Complexity
  • 어떤 알고리즘이 문제를 풀기 위해 해야하는 계산이 얼마나 복잡한가?
• 알고리즘의 성능을 객관적으로 평가하는 기준
  • 시간복잡도(time complexity) : 실행 횟수로 판단
  • 공간복잡도(space complexity) : 기억공간과 파일 공간의 사용량
• 빅오 표기법 ( Big O Notation)
  • 알고리즘이 얼마나 빠른지 표시하는 방법
  • 입력 데이터 크기 증가할 때 알고리즘 연산 시간(횟수)의 증가 방식
  • 연산의 횟수를 비교함
  • O(n) : 계산 복잡도 
    • O : 빅 O
    • n : 연산 횟수
    • O(1) : 입력 크기 n과 계산 복잡도가 무관 할때 ex) n(n+1)/2
    • O(logn) : 입력 크기 n의 로그 값에 비례하여 증가 ex) 이분탐색
    • O(n) : 입력 크기 n에 비례하여 복잡도 증가 ex) 최댓값, 순차탐색
    • O(nlogn) : 입력 크기 n과 로그 n 값의 곱에 비례하여 복잡도 증가 ex) 병합정렬, 퀵정렬
    • O(n²) : 입력 크기 n의 제곱에 비례하여 복잡도 증가 ex) 선택정렬, 삽입정렬
    • O(n₂) : 입력 크기가 n 일 때, 2의 n 제곱 값에 비례하여 복잡도 증가 ex)하노이의 탑

 

가짜 동전 찾기 : 겉보기에 똑같은 동전 n개 중 한개는 가벼운 재료로 만들어진 가짜 동전일 때, 좌우 무게를 비교할 수 있는 양팔 저울을 이용해서 다른동전보다 가벼운 가짜 동전 찾아내기

 

# 입력 : 전체 동전 위치의 시작과 끝

# 출력 : 가짜 동전의 위치 번호

# 양팔 저울

# 두개의 그룹 :  a ~ b까지 동전,  c ~ d까지 동전

# a ~ b에 가짜 동전이 있다면 -1 리턴

# c ~ d에 가짜 동전이 있다면 1 리턴

# 가짜 동전이 없다면 0 리턴

# for문으로 weight을 계속 돌려야함.

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

    # 임의의 fake 동전 위치

    fake = 29

    if a <= fake and fake <= b:  # a <= 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  # 반나눠서 두그룹 생성

    # 100개의 동전이 있다고 할 때 0~ 49 가 g1,

    # 50 ~ 99가 g2

    # 왼쪽 그룹 g1

    g1_left = left

    g1_right = left + half - 1

    # 오른쪽 그룹 g2

    g2_left = left + half

    g2_right = g2_left + half - 1

    # result == -1 or 0 or 1

    result = weight(g1_left, g1_right, g2_left, g2_right)

    if result == -1:  # 그룹1에 가짜 동전 있음. g1 그룹에서 또 나누기

        return find_fakecoin(g1_left, g1_right)

    elif result == 1:  # 그룹 2에 가짜 동전 있음. g2 그룹에서 또 나누기

        return find_fakecoin(g2_left, g2_right)

    else:  # 두 그룹에 가짜 동전 없음

        return right  # 두 그룹으로 나뉘지 않고 남은 나머지 한개의 동전이 가짜

if __name__ == "__main__":

    n = 100

    print("가짜 동전 위치 : ", find_fakecoin(0, n - 1))