일상코딩/노트

Python : 재귀호출, Memoization, Dynamic Programming

코딩애벌레 2024. 2. 11. 17:13

Recusion (재귀호출)

: 필요한 함수가 자신과 같은 경우 자신을 다시 호출하는 구조. 얼마전에도 간단하게 Factorial을 예시로 다룬적이 있다. https://codinglarva.tistory.com/21 에서 확인 할 수 있다. 간단하게 더 설명하자면, 일반적인 호출 방식보다 재귀 호출 방식을 사용해 메모리, 시간을 줄이고 가독성이 더 좋게 작성이 가능하다.

factorial 함수를 재귀할 때 진행되는 과정을 도식화 한 것

 

이번엔 코드로 살펴보자


# 재귀함수를 이용한 피보나치 구현
def fibo(n):    
    if n < 2:       # 기저조건
        return n    # n = 1, n = 0 일때를 표현
    else:
        return fibo(n-1) + fibo(n-2)    # 피보나치 식
   
n = int(input())
print(fibo(n))

 

어렵게 생각하지 않아도 된다. 기저조건(종료조건)과 식만 잘 표현해주면 재귀 호출은 누구나 할 수 있다. 하지만 이는 메모리, 실행시간에서 불리하기때문에 앞으로 나올 코드를 보게되면 굉장히 그리워질 것이다.

Memoization (메모이제이션)

: 동적 프로그래밍에서 이전에 계산된 결과를 저장하여 중복 계산을 방지하는 기법이며 재귀호출을 통한 재귀함수 등에서 중복이되어 불필요한 호출을 하지 않겠다. 컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 따로 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행 속도를 빠르게 하는 기술이다. 이후 나올 동적 계획법(DyP)의 핵심이다.

메모'이'제이션임을 기억하자. 물론 파생된 곳은 같지만 자주 헷갈린다.

 

피보나치수열의 재귀 호출 그림이다. 수가 커지면 불필요한 데이터 생성이 많아지는 것을 볼 수 있다. 시간복잡도 : BigO(2**n)

 

해당 알고리즘에서 fibo(n)의 값을 계산한 데이터들을 따로 메모이제이션한다면 실행 시간을 BigO(n)으로 줄일 수 있다. 

파이썬 코드로는 아래와 같다.


# 0으로 초기화 되어있는 memo 배열을 생성한다.
# 미리 fibo(0) = 0, fibo(1) = 1 처럼 종료조건(기저조건)을 설정해준다.
# memo[0] = 0, memo[1] = 1 이다.

def fibo(n):    # 피보나치 함수 정의
    global memo # global 선언을 통해 memo 변수를 끌고온다.
    if n >= 2 and memo[n] == 0:
        memo[n] = fibo(n-1) + fibo(n-2) # 재귀호출 형태 확인
    return memo[n]  # memo에 저장할 데이터 리턴하여 자동으로 넣는다.

n = int(input())
memo = [0] * (n + 1)    # 저장할 데이터 공간 설정
memo[0] = 0             # 기저조건, 종료조건은 미리 넣어둔다
memo[1] = 1             # 이하동문
 
print(fibo(n))          # 출력

 

처음에는 memo에 피보나치수열의 데이터가 모두 저장되어 출력되는가 싶었으나, 저장공간을 함수가 사용하기 위함이지 리스트 자체가 리턴되진 않아서 [0, 1, 0, 0, 0, 0]으로 출력된다. 호기심이 있다면 출력 해보는 것도 좋은 것 같다. (함수 안에 memo 데이터를 확인하면 제대로된 피보나치 데이터들을 확인할 수 있을 것이다)

 

 

DP(Dynamic Programming)

: 메모이제이션과 유사한 의미로 동적 계획 알고리즘이다. 만든사람이 멋있게 보이기 위해 이런 단어를 썼다고 한다. DP는 그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘이라고 보면 된다. 입력 크기가 작은 부분의 문제들을 모두 해결한 후에 해결한 해들을 이용해서 보다 큰 크기의 문제들을 해결하여 최종적으로 주어진 입력의 문제를 해결하는 알고리즘이다. 재귀와 유사한 의미를 갖는 것 같다.

  • memoization을 재귀적 구조에 사용하는 것보다 반복적 구조로 DP를 구현한 것이 성능면에서 효율적
  • 재귀적 구조는 내부에 시스템 호출 스택을 사용하는 오버헤드가 발생 
  • 쉽게 말하면 DP가 짱이다~

만만한 피보나찌(Fibonacci)의 문제로 해결해보자.

 

1) 큰 문제를 작은 부분 문제로 분할

목표는 Fibo(n)의 값을 구한다고 보자.

Fibo(n) = Fibo(n-1) + Fibo(n-2)

Fibo(n-1) = Fibo(n-2) + Fibo(n-3)

Fibo(n-2) = Fibo(n-3) + Fibo(n-4)

...

Fibo(2) = Fibo(1) + Fibo(0) 임을 알 수 있다.

내가필요한 데이터는 Fibo(n), Fibo(n-1), ..., Fibo(1), Fibo(0) 이라는 부분집합으로 나뉘게 된다.

 

2) 부분 문제로 나뉘어져 있다면 가장 작은 부분의 문제 해를 추적

Fibo(0) = 0, Fibo(1) = 1

Fibo(2) = 0 + 1 = 1

Fibo(3) = 1 + 1 = 2

Fibo(4) = 1 + 2 = 3

Fibo(5) = 2 + 3 = 5

...

 

3) 작은 부분 문제의 결과를 모두 테이블에 저장하고, 저장된 부분 문제의 해를 통해 상위 문제의 해를 추적

좌측 데이터부터 우측방향으로 추적


def fibo(n):            # 피보나치 함수 정의
    f = [0] * (n + 1)   # 저장할 수 있게 0으로 초기화되어있는 배열 설정
    f[0] = 0            # 기저조건
    f[1] = 1            # 이하동문
    for i in range(2, n + 1):   # 반복문을 통해 f[n] 을 구하러 올라간다
        f[i] = f[i-1] + f[i-2]  # 피보나치 식
    return f[n]         # 최종 목적지인 f[n] 을 반환

n = int(input())
print(fibo(n))

 

위와 같이 코드로 나타내보면 메모이제이션과 다이나믹 프로그래밍은 큰 틀에서 보게되면 개념 자체는 동일하나 차이점도 존재한다. 총 피보나치로만 3가지가 정의 되었는데, 일반 재귀함수호출, 메모이제이션, 다이나믹 프로그래밍이다.

피보나치 수열을 다루었던 방식 세가지를 한번에 비교하면 위의 정리와 같다.

 

memoization이 Top-Down, dynamic programming이 Bottom-Up 이라고 생각하면 편하다. 이 단어 분명 어디서 많이 들어본거같은데 건축 공학에서 시공 공부할때, 탑다운 공법과 바텀업 공법과 유사한거같아서 웃겼다.

다음은 DFS로 깊이 우선 탐색 파트이다. 여기서 한번 더 고비가 오는 것 같다.. 화이팅!!

728x90