정말 오랜만에 보는 사마귀를 보았다.어서와 우리 집은 처음이지?
올라오느라 힘들었겠다는 생각을 했는데 우리 기숙사가 2층이었다는 걸 깜빡했다.😅
정글의 마지막 알고리즘 주차가 시작되었는데 다들 후회없이 마무리하는 한주가 되었으면 좋겠고, 응원한다😘

DP (다이나믹 프로그래밍) - 1

DP, 즉 다이내믹 프로그래밍은 중복되는 연산을 줄이기 위해 사용한다.
최적의 해를 구하기에 시간이 매우 많이 필요하거나 메모리 공간이 많이 필요한 문제 등이 컴퓨터로도 해결하기 힘들다.
쉽게 말해 시간 복잡도나 공간 복잡도 측면에서 한계가 있다.
그렇기 때문에 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘인 DP를 사용한다.

DP에는 흔히 '보텀업 방식'과 '탑다운 방식'으로 구성되어 있는데
오늘은 TIL의 작성에 한계가 있기에 개인적으로 신기했던 탑다운 방식을 소개해 볼까 한다.
먼저 코드를 보고 이해해 보자!

탑다운 방식(메모이제이션)

# 피보나치 탑다운 방식 
d = [0] * 100   # 한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화
# 피보나치 함수를 재귀함수로 구현(탑다운)
def fibo(x):
    # 종료 조건(1 혹은 2일 때 1을 반환)
    if x == 1 or x == 2:
        return 1
    # 이미 계산한 적 있는 문제라면 그대로 반환
    if d[x] != 0:
        return d[x]
    # 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
    d[x] = fibo(x-1) + fibo(x-2)
    return d[x]
# 결과값 출력
print(fibo(99))

내가 만약 재귀를 이해하지 못했더라면 이게 뭐지 싶었을텐데 나름 재귀를 잘 이해한 듯(?) 싶은지 '아하!' 소리쳤다.
혹여 이해가 어려운 분들에게 도움이 되고자 급하게 아이패드로 끄적여봤다..😂

탑다운 방식은 말 그대로 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식이다.
그래서 목적지인 fibo(6)부터 시작해서 답을 찾는 모험을 시작하는 것이다.
모험의 결과부터 스포(?) 하겠다.
이 모험은 fibo(6) > f(5) > f(4) > f(3)로 끝이 난다.
이게 무슨 소리인가 싶을 텐데 실선의 과정들은 각각의 재귀인데 메모이제이션을 통해 저장된 연산 결과를 사용할 뿐이지 직접 연산하지 않는다.

    # 이미 계산한 적 있는 문제라면 그대로 반환
    if d[x] != 0:
        return d[x]

이 과정에서 한번 연산되었기에 바로 리턴해줘서 한번 더 연산을 하지 않는다.
연산 결과를 저장하는 과정은

# 한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화
d = [0] * 100

위의 코드에서 리스트를 초기화해두고, fibo(6)에서 왼쪽 아래의 f(3)까지의 과정에서 연산 결과를 DP 테이블에 저장해준다.
결과적으로 위의 두 과정을 통해서 연산 결과를 기억해서 시간, 공간 복잡도를 최소화한다.
다음 DP 작성으로는 아마 바텀업 방식이 될 텐데 DP에서 가장 많이 사용하기 때문에 좀 더 주의 깊게 들여다봐야겠다. DP 은근 재밌을지도?

오늘의 추천곡 🎶

slchld - 'camellia' 🎵
가을이다보니 가을 플리를 듣고 있었는데 이 노래가 떠올라서 반복해서 듣다가 이건 오늘의 추천곡이다 싶었다.😊

내일의 나에게 👍

• DP 상까지