어쨌든 반복문이 가장 큰 핵심

그래도 핵심은 변하지 않습니다. 가장 오래 걸리는 반복문을 찾는 것이 핵심이고, 이 반복문의 시간 복잡도를 구하는 것이 제일 먼저 해야 할 일입니다. 다르게 말하면 함수별로 걸리는 시간 복잡도를 예측해 가장 오래 걸리는 함수가 있다면 다른 작업을 줄일지, 아니면 해당 함수를 최적화할지 전략을 짜는 겁니다.

조금 복잡한 문제를 풀기 위해 여러 가지 함수를 사용한다고 가정해봅시다. A 함수는 배열을 정렬하고, B 함수는 배열을 순회하면서 계산하고, C 함수는 두 배열을 함께 사용하여 값을 만들어내는 연산을 한다고 할게요. A 함수는 정렬이기 때문에 O(nlogn)만큼 시간이 소모될 것이고, B 함수는 배열을 순회하기 때문에 O(n)만큼 시간이 소모될 것이며, C 함수는 두 배열을 함께 사용하므로 O(n²)만큼 시간이 소모될 것입니다.

만약 이 문제를 시간 초과로 통과하지 못했다면 가장 오래 걸리는 작업이 C 함수라는 사실을 알고 있으니 자료 구조를 바꿔서 개선할지, 아니면 다른 함수의 논리를 변경해 작업량을 줄이는 방식으로 개선할지 선택하면 됩니다.