top-down, 재귀, 메모이제이션

앞에서 풀었던 문제(네트워크 선 자르기)를 재귀로도 풀 수 있다!! 진짜 재미있다..!!ㅎㅎㅎ

이 접근 방식이 동적 계획법으로서의 빛을 발하는 부분은 "메모이제이션 memoization"이다.

동일한 계산을 반복하지 않도록, 이전에 계산한 값을 저장해두는 것으로, 이 문제에서는 불필요한 재귀의 호출을 방지해준다.

재귀를 열심히 연습하면서 종종 내가 너무 모든 경우를 다 돌고 있다는 느낌이 들고는 했는데,

이번에 이걸 배우고 나니 다른 재귀문제를 풀 때도 메모이제이션을 통해 엣지를 탁탁 컷해보고 싶다는 생각이 든다!ㅎㅎ

1. 손 정리

2. 코드로 써보기

n = 7

# 메모이제이션을 위한 공간! 이 리스트의 인덱스번호에 해당하는 길이를 몇 가지 방식으로 자를 수 있는지 구하면 거기에 값을 넣어두기.
# 또 다른 곳에서 같은 길이에 대한 재귀적 호출을 하지 않도록 하기 위함.
obtained = [0] * (n+1)

def DFS(length:int):
    # 직관적으로 알 수 있어 미리 정해줄 수 있는 return 값들
    if length == 2:
        return 2
    if length == 1:
        return 1

    else:
        # 이게 이번에 중요하게 배운 포인트! 바로 메모이제이션!
        # 이미 계산한 값이 존재한다면! 초기화해둔 값인 0 이 아닐 것이다.
        # 그렇다면 재귀적 호출 필요 없이 거기서 바로 값을 가져온다.
        if obtained[length] != 0:
            return obtained[length]
        else:
            # 계산한 값이 없다면 하부로 내려가서 구한 값끼리 더해주어야 한다.
            # 그리고 구함과 동시에 그 값을 obtained 에 넣어주어 나중에 같은 계산을 안 하도록 한다.
            obtained[length] = DFS(length-1) + DFS(length-2)
            return obtained[length]

print(DFS(n))