DP 정복 - 2.2 하위 문제의 반복 계산

이번 절은 지난 절에서 소개했던 '하위 문제의 반복 계산'에 대한 내용이다.

지난 장의 재귀 호출 문제들은 본질적으로 반복 계산이 없는 문제였음.

재귀 호출을 사용하기는 했지만 각 하위 문제들은 두 번 이상 호출되지 않음.

 

이번 절에서는 다소 복잡한 재귀 호출에 초점을 맞출 예정. 완전히 같은 인수를 사용한 반복된 재귀 호출이 여러 번 발생하는 경우이며, 이런 특성을 '하위 문제의 반복 계산'이라고 부름.

이러한 하위 문제의 반복 계산에 가장 간단한 예는 '피보나치수열'을 구하는 알고리즘.

단순 재귀를 사용하면 n이 늘어날수록 추가 메모리가 필요하며 이미 한번 연산했던 행위를 다수 반복 가능.

 

다음으로 소개되는 예제는 '역 사이 최소 비용 구하기'이다.

이 경우는 희소 행렬(대부분 원소 값이 0인 행렬)을 사용하기 알맞은 경우로

시작점에서 다음 역까지 가는 승차권이 최솟값이며, 출발역과 도착역이 같은 경우 두 가지가 종료 조건이 된다.

피보나치수열 문제와 마찬가지로 n이 커질수록(역의 개수가 많아질수록) 반복되는 계산이 늘어나기에 비효율적이다.

 

* 만약 코딩 테스트일 경우는 자원(메모리, 시간 등)에 구애받지 않고(한 번에 설루션을 낼 수 있다면 더 좋겠지만), 일단 재귀적으로 접근하는 방식으로 풀어보라고 저자는 추천한다.

 

연습문제를 고민해 보았으나.. 하위 문제를 어떻게 뽑아야 될지 그림으로 그려서 봐도 잘 모르겠어서 일단 suspend 시켰다. 어차피 나중에 나오는 장에서 다룰 예정이니 그때 다시 한번 보면 될 듯싶다.