codingismylife   1년 전

b == 1일 때를 base 조건으로 잡고 동작하는 건 당연한데, 여기서 temp = pp(a, b/2, c)를 호출하고 temp를 temp * temp 방식으로 처리하는 이유가 불필요한 재귀 함수의 호출을 막기 위함인가요?? 


zenith82114   1년 전

재귀호출을 2번씩 하면 for (int i = 0; i < c; i++) temp = temp * a % b;와 똑같은 시간복잡도가 됩니다.

codingismylife   1년 전

감사합니다! 어떻게 보면 DP + 재귀에서 탑 다운 방식으로 동작할 때 메모이제이션 한다는 개념으로 이해하면 될까요??

zenith82114   1년 전

네. 보통 배열을 사용하는 것과 달리, 변수 1개(temp)로 충분한 특수한 상황이라고 이해하시면 됩니다.

codingismylife   1년 전

감사합니다!! 

댓글을 작성하려면 로그인해야 합니다.