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)하노이의 탑

 

 

최대공약수 : 두개 이상의 정수의 공통 약수 중에서 가장 큰 값

문제 : 4와 6읠 최대 공약수 찾기

알고리즘

• 두 수 중 더 작은 값을 i에 저장
• i가 두수의 곹오된 약수인지 확인
• 공통된 약수이면 이 값을 결과값으로 돌려줌
• 공통된 약수가 아니면 i를 1만큼 감소시키고 2번으로 돌아가 반복

def gcd(a, b):

    i = min(a, b)

    while True:

        if a % i == 0 and b % i == 0:

            return i

        i = i - 1

if __name__ == "__main__":

    print("1과 5의 최대공약수 : ", gcd(1, 5))

    print("1과 5의 최대공약수 : ", gcd(3, 6))

    print("1과 5의 최대공약수 : ", gcd(60, 24))

    print("1과 5의 최대공약수 : ", gcd(81, 27))

 

 

 

최대공약수 - 유클리드 호제법

• 규칙 1) a와 b의 최대공약수는 b와 a를 b 로 나눈 나머지의 최대공약수와 같다
  •   gcd(a,b) == gcd(b, a%b)
• 규칙 2)  어떤 수와 0의 최대 공약수는 자기 자신
  • gcd(60,24) = gcd(24,60%24) = gcd(24, 12) = gcd(12, 24%12) = gcd(12,0) = 12

def gcd(a, b):

    if b == 0:

        return a

    else:

        return gcd(b, a % b)

if __name__ == "__main__":

    print("유클리드 호제 1과 5 최대공약수 : ", gcd(1, 5))

    print("유클리드 호제 1과 5 최대공약수 : ", gcd(3, 6))

    print("유클리드 호제 1과 5 최대공약수 : ", gcd(60, 24))

    print("유클리드 호제 1과 5 최대공약수 : ", gcd(81, 27))