12 동적 프로그래밍

재귀는 제대로 사용하지 않으면 문제가 발생하기도한다.

재귀는 종종 가장 느린 빅오카테고리의 주된 요인이다.

불필요한 재귀 호출

재귀가 2번나오게 되면 재귀호출이 쇄도하게된다. O(2^N)이 되기 쉽다.

코드가 어떻게 실행되는지 알려면 바닥 호출부터 분석해 따라 올라가야한다.

수정 전 O(2^N)

수정 후 O(N)

 

코드에서 재귀(필요한 함수 호출)을 한번만 수행하고 결과를 변수에 저장한다.

즉 함수를 다시 호출하지 않아도 되게 변경하면 훨씬 효율적이게 된다.

불필요한 재귀호출을 피하는 것이 중요하다.

메모이제이션

하위문제가 중첩될 때 재귀호출을 감소하는 방법

먼저 계산한 함수결과를 기억해 재귀호출을 감소시킨다.

 

결과를 해시테이블에 저장하고 새로운 계산을 할 때마다 해시테이블에 저장하고 나중에 쓸 수 있다.

함수의 두번째 인자로 해시테이블을 전달하면 재귀함수가 접근할 수 있다.

계산결과를 memo 해시에테이블에 저장하므로 다시 계산할 필요가 없다.

상향식을 통한 동적프로그래밍

상향식은 그저 재귀대신 루프같은 다른방식으로 해결한다는 뜻이다.

상향식이 동적프로그래밍의 하나로 간주되는 이유는 재귀적으로 풀 수 있는 문제에 대해 중첩되는 하위문제를 중복호출하지 않게 해주기 때문

상향식 피보나치

O(N)

 

가장 최근값은 a에

두번째로 가장 최근 값은 temp에 할당하고

이 두 수를 합해 b에 할당한다.

메모제이션 대 상향식

일반적으로 상향식을 택하는 방식이 낫다.

재귀가 더 직관적이면 재귀를 사용하고 메모이제이션으로 빠르게 만들자.

더 나은 기법은 문제의 종류와 재귀를 왜 샤용하는지에 따라 다르다.

재귀를 어떻게 사용하든 호출스택을 기록해야하므로 메모리를 소모하고

메모이제이션 자체도 해시테이블을 사용하므로 컴퓨터공간을 추가로 소모한다.

재귀는 종종 가장 느린 빅오카테고리의 주된 요인이다.