[STUDY] 동적계획법 (dynamic programming)

동적계획법을 배우고 나서 백준에서 문제를 풀어보았고 어느정도 머리에 지식이 생긴것 같아서

생각도 정리 할 겸 포스팅 하기로 했다.

---

예제로 풀 문제가 필요하여 chatGPT에게 간단한 문제를 받아보았다.

우선 해당 코드를 재귀함수로 풀어보자면 

---

재귀함수를 이용한 코드

def count_ways(n):
    if n == 0:
        return 1
    elif n < 0:
        return 0
    else:
        return count_ways(n-1) + count_ways(n-2) + count_ways(n-3)

n = 4
result = count_ways(n)
print(result) # 7

return 문을 보면, count_way() 내부에서 다시 해당 함수를 호출한다.

이 코드는 재귀적으로 호출을 하기 때문에 시간 복잡도를 보면 지수적으로 해결 시간이 상승한다.

 

따라서, 이를 효율적으로 해결할 방법을 찾게 되었다.

---

동적 계획법을 이용한 코드

def count_ways(n, memo):
    if n < 0:
        return 0
    elif n == 0:
        return 1
    elif memo[n] > -1:
        return memo[n]
    else:
        memo[n] = count_ways(n-1, memo) + count_ways(n-2, memo) + count_ways(n-3, memo)
        return memo[n]

n = 4
memo = [-1] * (n+1)
ways = count_ways(n, memo)
print(ways) # 출력값: 7

코드를 확인해 보면 memo 배열에 한 번 사용 된 수식은 memo배열에 저장하여 더 이상 연산을 진행을 하지 않는다.

따라서 1+3과 3+1은 같은 식이기 때문에 중복 연산을 하지 않는다.

때문에 연산 수행 시간이 더 줄어든다.

 

이렇게 memo배열에 저장하여 중복 식을 배제 하는 기법을 memorization이라고 부른다.