알고리즘을 적용해 프로그램을 효율화하자

알고리즘 : 어떤 문제를 풀기 위한 절차나 방법, 구체적으로 어떤 문제가 주어진 '입력' 정보를 원하는 '출력(답)' 정보로 만드는 일련의 과정을 말함.

1부터 n까지 연속한 정수의 합을 구하는 알고리즘1
1부터 n까지 숫자를 차례로 더하는 방법을 사용함

def sum_n(n) :
    s = 0 # 합을 계산할 변수
    for i in range(1, n+1): # 1부터 n까지 반복(n+1은 제외)
        s = s + i
    return s

sum_n(10)

55

1부터 n까지 연속한 정수의 합을 구하는 알고리즘2
수학자 가우스의 계산 방법을 사용함

def sum_n(n):
    return n * (n+1)//2 # 슬래시 두개는 정수 나눗셈을 의미

알고리즘 1과 2를 비교했을 때, 숫자가 커지면 커질수록 알고리즘2가 더 효과적으로 동작한다는 것을 알 수 있다. 
동일한 문제를 해결하는 여러 알고리즘 중 어떤 알고리즘이 더 좋은지 판단하는 것을 '알고리즘 분석'이라고 한다.

1부터 N까지 연속한 정수의 곱을 구하는 알고리즘1

정수의 합을 구하는 알고리즘 1을 고쳐서 작성한다. 1부터 N까지의 곱은 팩토리얼(factorial)이라고 한다. 팩토리얼은 숫자 뒤에 느낌표를 붙여 표기하며 1부터 n까지 연속한 숫자를 차례로 곱한 값을 말한다. '계승'이라고도 한다.

def fact(n):
    f = 1 # 곱을 계산할 변수, 초기값은 1
    for i in range(1, n+1):
        f = f * i
    return f

1부터 N까지 연속한 정수의 곱을 구하는 알고리즘2

재귀 호출(recursion)은 어떤 함수 안에서 자기 자신을 부르는 것을 말한다. 팩토리얼을 재귀 호출로 표현하면, n! = n * (n-1)!로 표현할 수 있다.

def fact(n):
    if n <=1:
        return 1
    return n * fact(n-1)

재귀 호출에는 종료 조건이 꼭 필요하다. 종료 조건이 없으면 RecursionError 또는 Stack Olverflow 등의 에러가 발생할 수 있다.

두 자연수 a와 b의 최대공약수를 구하는 알고리즘1

최대공약수는 두 개 이상의 정수의 공통약수에서 가장 큰 값을 의미한다. 두 수의 약수 중에서, 공통된 것을 찾아, 그 값 중 최댓값을 찾는 것이다. 

def gcd(a, b):
    i = min(a, b) # 두 수 중에서 최솟값을 구하는 함수
    while True:
        if a % i == 0 b % i == 0:
            return i
        i = i -1 # i를 1만큼 감소시킨다

 

두 자연수 a와 b의 최대공약수를 구하는 알고리즘2

수학자 유클리드의 유클리드 알고리즘을 사용해서 문제를 풀 수 있다. 이때 사용하는 것이 재귀 호출이다. 

def gcd(a, b):
    if b == 0: # 종료 조건
        return a
    return gcd(b, a % b) #  좀 더 작은 값으로 자기자신을 호출

재귀 호출은 처음 사용할 때는 혼란스러울 수 있지만, 한번 익혀두면 여러가지 문제를 아주 단순하게 풀 수 있는 강력한 무기가 될 수 있다.

 

위에서 알아본 알고리즘들을 보면, 일련의 순서에 따라 함수를 작성하는 것보다 관련 알고리즘을 사용하는 것이 매우 간단하고 효율성을 높이는 것을 알 수 있다.

가장 핵심적인 알고리즘을 숙지하고 있는 것이 프로그램을 작성하는데 한단계 높은 방법을 제시한다는 것을 알고 있도록 하자.

<참고> 모두의 알고리즘 with  파이썬, 이승찬 저