재귀에서 함수 호출 비용

https://www.acmicpc.net/problem/10830

10830번: 행렬 제곱

 

이 문제를 풀면서 천억단위의 행렬 제곱을 실행하는 알고리즘을 짜야 했다. 처음에 DP를 생각해서 작성하였는데 시간초과가 떴다. 그 후 다른 풀이가 생각나지 않아 결국 검색하여 A^5 = (A^2)^2 * A 와 같이 행렬의 제곱을 부분적으로 나눠서 계산하는 분할정복 알고리즘으로 해결하였다.

 

그런데 나중에 테스트 해보니 기존의 DP를 활용한 알고리즘과 분할정복을 사용한 알고리즘끼리 10억 단위의 테스트에도 배열 곱셉 함수 호출 횟수가 각각 49회와 41회로 10회도 차이가 나지않음을 확인했다.

 

그렇다면 어디선가 지연이 크게 일어나는 부분이 있을 것이라 생각하고, 구하려는 행렬제곱수가 이미 계산했던 제곱수이면 반환하는 조건문을 함수의 밖에 호출하는 부분으로 옮겨봤다. 결과는 시간초과없이 성공적으로 통과했다. 코드는 아래와 같다.

 

기존 코드(multiplyMatrix에서 조건문 실행)

 

수정한 코드(multiplyMatrix를 호출하기 전에 조건문 실행)

 

이를 통해 반복횟수가 매우 커지면 단순히 함수를 호출하는 횟수가 많아지는 것 만으로도 속도가 크게 저하될 수 있다는 것을 깨달았다. 아래는 전체 풀이 코드이다.

 

 

DP를 이용한 코드:

https://github.com/intensive-study/backend-study/blob/main/problem-solving/study_01/yunhwan/BOJ10830-failed-modify.java

GitHub - intensive-study/backend-study

 

분할 정복 코드:

https://github.com/intensive-study/backend-study/blob/main/problem-solving/study_01/yunhwan/BOJ10830.java

GitHub - intensive-study/backend-study

 

 

 

문제 풀이 참고:

https://st-lab.tistory.com/251

[백준] 10830번 : 행렬 제곱 - JAVA [자바]