문제 풀이 강의 과정을 들으면서 강사님이 했던 말을 정리해 봅니다.
* 강의 주제는 No internet, No 참고자료, 제한시간 상황에서 특정 알고리즘을 이용해서 푸는 방식이 아닌, 문제 코드를 잘 분석해서 요구하는 기능을 최적화해서 구현하는 스타일의 문제에 대한 강의
... 여러 문제 상황에 대해서 접근하기 쉽고 변형이 쉬운 방법을 익혀두는 것이 좋습니다. 예를 들어, 구간 합 구하기 문제를 봅시다.
구간 합 구하기 / https://www.acmicpc.net/problem/2042
이 문제의 경우에 펜윅 트리를 이용할 수 있으면 좋겠지만, 구현하기도 어렵고, 응용이 필요한 경우에 변경이 쉽지도 않습니다. 하지만, Sqrt Decomposition 을 이용하면 구현하기도 더 쉽고 상황에 따라서 속도도 더 빠르게 됩니다. Sqrt Decompostion 을 잘 익혀두면 이 문제뿐만 아니라 다른 여러 타입의 문제에 대해서도 적용할 수 있으니 꼭 익혀두시기 바랍니다 ...
Sqrt Decomposition 을 익어 두어라.
관련 참고 자료: https://david0506.tistory.com/57
