[알고리즘] 연산량 줄이기(feat. 가지치기)

https://dnf-lover.tistory.com/2

이전에 우리는 '시간복잡도'의 개념에 대해 배웠다.

그렇다면 이 시간복잡도 즉, 연산량을 줄이는 방법은 무엇이 있을까?

1. 시간 복잡도의 한계

실제 연산량을 계산할 때, 함수의 계수와 낮은 랭크의 항을 무시하게 되기 때문에 실제 연산량과 시간 복잡도를 통해 계산한 연산량의 차이가 클 수 있다.  또, 함수들은 값의 범위에 따라 대소 관계가 다르다는 점때문에 낮은 랭크의 시간 복잡도가 항상 높은 랭크의 시간 복잡도보다 적은 연산량을 보장하지 않는다.

위의 그래프를 보면, 길게 보았을 때에는 제곱근들에 비해 Y = X가 더 퍼포먼스가 좋지만, X축이 1이하일 때 퍼포먼스는 y = X 보다 y = X^2 혹은 X^3의 퍼포먼스가 더 좋다는 것을 확인할 수 있다.

시간 복잡도는 매우 큰 연산량을 요구하는 알고리즘을 분간하는 데에는 큰 도움이 될 수 있지만, 같은 시간 복잡도를 가지는 알고리즘이나 입력 데이터 수가 작은 알고리즘의 구체적인 성능을 예측하기에는 시간 복잡도 이외의 추가적인 지식과 감이 필요할 수 있다.

그렇기 때문에 알고리즘 계산을 할 시, 최상의 경우 최악의 경우 평균을 나눠 계산한다.

(요새는 하드웨어가 하도 좋아져서 시간 복잡도 보단 공간 복잡도를 더 신경쓴다는 이야기도 있다.)

2. 가지치기

가지치기란, 불필요한 반복이나 함수의 호출을 도중에 빠져나오거나 차단하는 기술을 이야기 한다.

return이나 break문 등을 통해 함수나 반복문을 수행하는 도중에 더 이상 수행할 가치가 없다고 판단되는 연산들을 생략하면 성능상 좋은 퍼포먼스를 낼 수 있다.

그러나 가지치기를 통해 생략한 연산으로 인해 실제 얻을 수 있는 출력 값이 달라지면 안되기 때문에 연산들을 생략해도 정답을 구하는 데에 전혀 지장이 없다는 확신이 있어야 한다.

가지치기는 알고리즘을 시간 복잡도를 효과적으로 개선하는 데에 사용할 수 있지만 알고리즘 자체를 개선할 수 있는 방안은 아니다. 가지치기가 알고리즘에 필수적으로 들어가야 하는 요소는 아니라는 뜻이다.

풀어야 하는 문제에 집중하여 제약들에 맞추며 문제를 풀도록 하자.