재귀호출을 2번씩 하면 for (int i = 0; i < c; i++) temp = temp * a % b;와 똑같은 시간복잡도가 됩니다.
1629번 - 곱셈
재귀호출을 2번씩 하면 for (int i = 0; i < c; i++) temp = temp * a % b;와 똑같은 시간복잡도가 됩니다.
감사합니다! 어떻게 보면 DP + 재귀에서 탑 다운 방식으로 동작할 때 메모이제이션 한다는 개념으로 이해하면 될까요??
감사합니다!!
댓글을 작성하려면 로그인해야 합니다.
codingismylife 1년 전
b == 1일 때를 base 조건으로 잡고 동작하는 건 당연한데, 여기서 temp = pp(a, b/2, c)를 호출하고 temp를 temp * temp 방식으로 처리하는 이유가 불필요한 재귀 함수의 호출을 막기 위함인가요??