메모화를 배운

사전 쓰기

최근 Web계 기업의 인턴 전형이나 본 전형을 받을 기회가 몇번이나 있었습니다.
많은 기업의 전형에서 코딩 테스트가 있었고, 이번 조금 공부했기 때문에 아웃풋 연습도 겸해 비망록적인 느낌으로 남겨 둡니다.

이번은 메모화에 대해입니다.

메모화란?

간단히 말하면 프로그램 속도를 높이는 기술입니다.

「재귀 처리 등으로 몇번이나 같은 함수가 불릴 때에 계산 결과를 캐시(메모)에 기록해 두고, 전에 계산한 것에 관해서는 캐시된 값을 돌려준다」라고 하는 느낌의 테크닉입니다.

구현 예

이번에는 구현 예로서 피보나치 수열의 n번째 숫자는 무엇인가를 요구하는 프로그램을 소개합니다.

피보나치 수열

a_1=a_2=1 \\
a_n=a_{n−1}+a_{n−2}\\
(1\leqq n)

피보나치 수열을 점화식으로 나타내면 위와 같이 됩니다.
자세한 설명은 생략하지만 처음 두 항은 1을 반환하고 이후에는 이전 두 항의 합을 반환합니다.

그냥 재귀로 구현

def fibonacci(n):
    if n == 1 or n == 2:
        return 1

    return fibonacci(n - 2) + fibonacci(n - 1)

print(fibonacci(6))  # 8

메모화로 구현

memo = {1: 1, 2: 1}

def fibonacci(n):
    # memoの中にnが記録されている場合は、その値を返す
    if n in memo:
        return memo[n]

    # ない場合はメモに記録して、その値を返す
    memo[n] = fibonacci(n - 2) + fibonacci(n - 1)
    return memo[n]

print(fibonacci(6))  # 8

이미지

단지 재귀로 실장했을 경우의 n=6은, fibonacci(4)가 2회, fibonacci(3)가 3회 불리고 있습니다.
n이 점점 커지면 계산하는 횟수가 늘어나는 것을 이미지 할 수 있다고 생각합니다.
메모화를 하면 1번 계산한 것에 대해서 2회째 이후는 계산하지 않아도 되므로 계산 횟수를 대폭 줄일 수 있습니다.

요약

메모화는 프로그램의 고속화를 위한 기법의 하나.

n이 커질수록 유효합니다.