Shorten-Time Techniques : LR 테크닉

시간을 줄이는 기술은 대체로 향후 수행할 연산의 패턴을 이해하고, 미리 해당 연산에 사용할 수 있는 값들을 구해놓은 뒤 나중에 조회만으로 값을 도출하는 방식입니다.

 

누적합의 경우에도 구간합 또는 연속성, 그리고 구간 내의 점의 개수 등을 파악하기 위해 미리 연속된 구간에 해당하는 값을 구해둔 뒤, 나중에 해당 배열에 대한 값을 조회하는 것으로 시간복잡도를 줄입니다.

 

LR 테크닉은 누적합을 응용한 버전이라고 볼 수 있습니다. 누적합을 양방향으로 따둔 뒤에 사용하는 것이죠.

 

뭔가 단순히 상상했을 때에는, 미리 구해둔다라는 개념이 "어차피 연산을 해야 하는거라면 완전탐색처럼 하는것이나 누적합이나 시간복잡도가 똑같아야 하는 것 아닌가?" 할 수 있겠지만,

 

완전탐색은 경우의 수를 나눠서 매번 그 연산을 수행해야 하는 것일 텐데, 누적합은 경우를 나누지 않고 특정 상황에 대한 값을 미리 저장해 둔 뒤에 나중에 해당 값을 이용하여 원하는 값을 도출하는 것이므로 시간복잡도가 더 낮게 됩니다.

 

이를 적절히 활용하면 그냥 생짜로 완전탐색을 사용할 때 보다 더욱 효율적인 연산이 가능해집니다.