다이나믹 프로그래밍 및 다른 알고리즘에서 빼놓을 수 없는 부분이기도 하지요.
"알고리즘과의 싸움은 시간 싸움이다."라는 말처럼, 빠른 속도만큼 그 알고리즘은 최적화가 잘되어있다 보면 좋습니다.
(온라인 저지 사이트의 채점 속도 0.01초 차이가 아닌, 시간 초과 소스를 시간초 내로 들어오는 차이정도? ^^;)
다음 문제를 이용해 최적화를 시도해보겠습니다.
1. 속도를 빠르게 할 수 없을까? 반복문의 횟수를 줄인다는 것은 실행 횟수가 줄어들고, 속도의 향상으로 바로 연결됩니다.
이번 문제에서는 어떻게 시간을 줄일 수 있을까요?
=> 점화식대로 해서 i와 j를 이용해 반복문을 돌리는데 시간초과가 나요.
분명 위의 다이나믹 문제는, i와 j의 반복문을 이용하기 때문에 O(N^2) 이상의 효율을 찾기 힘듭니다.
하지만, 소수의 특성으로 반복문의 횟수를 크게 줄여줄 수 있다면 어떨까요?
if ( not_prime( i ) ) continue;
다음과 같은 문장을 j가 돌기 전에 써준다면, i의 반복횟수가 10000번에서 1229번으로 줄게 되겠죠??
(10000까지의 소수의 개수는 1229개입니다. ^^)
평균 1억번의 횟수를 1초 커트라인으로 생각하고 프로그램을 짠다면, 프로그램을 하는데 도움이 많이 됩니다.
10000 * 10000 (1억) 을 1229 * 10000 (약 1230만) 번으로 줄였다면, 8배정도 빨라지겠군요!
(물론 최적화에 따른 점화식 수정은 충분히 생각해보시길 바랍니다. ^^)
=> 점화식은 이해가 되는데, n을 어디서부터 어디까지 돌려야될지 몰라서 10000부터 1까지 돌렸어요.
위의 경우에는 아무런 최적화가 안되어있을 때 아슬아슬하게 통과하거나, 시간초과에 걸릴 위험이 있습니다.
이러면 어떨까요? 현재까지 구한 소수의 합 중 최대를 미리 저장했다가, 반복문을 돌릴 때 사용하는 겁니다.
예를 들어, 7을 돌릴 때 그 전에 있던 모든 소수의 총 합인 (2+3+5 = 10) 을 저장해놓고, 거기서부터만 돌리는 겁니다.
for(j=0; j<=max ; j++)
{
//내용
}
그러면 프로그램을 돌리는 횟수도 크게 줄어들 수 있겠죠?? 저는 거의 절반정도 줄어들었네요. ^^
최적화는 어느 곳에서도 유용하고, 그 방법도 다양합니다.
안전한 통과를 노린다면, 필요없는 부분은 과감하게 잘라주는 가지치기 과정이 필요합니다.
코딩을 하기전에 필요없는 부분을 사용하지 않으려는 고민을 해보는 건 어떨까요?
출처:pl0892029