제약 조건을 읽고 복잡도 선택하기

각 문제에는 n과 값의 제한이 제시됩니다. 이러한 제약 조건은 출제자가 기대하는 복잡도를 조용히 알려 줍니다. 🔍

무엇이든 설계하기 전에 제약 조건에서 가장 큰 n을 확인하십시오. n의 크기에 따라 이차, 선형, 로그 복잡도 중 무엇이 필요한지 결정됩니다.

n이 최대 20이면 지수 시간 완전 탐색도 맞습니다. 제한이 작다면 모든 조합을 부담 없이 시도해 볼 수 있습니다.

n이 수백에 이르면 O(n^3) 해법도 여전히 통과합니다. 여기서는 삼중 반복문이나 쌍을 대상으로 하는 기본 DP를 사용할 수 있습니다.

n = 5000 정도라면 O(n^2)을 목표로 하십시오. 배열을 중첩 반복문으로 순회하면 약 2.5 × 10^7단계가 필요하며, 이는 여전히 예산 안에 들어옵니다.

n이 10^5 또는 10^6에 이르면 O(n log n) 또는 O(n)이 필요합니다. 정렬, 누적 합, 투 포인터가 주력 도구가 됩니다.

n이 10억이면 n에 대한 반복문은 어떤 것도 버틸 수 없습니다. 수학이나 정답에 대한 이진 탐색을 사용하여 O(log n) 또는 O(1)을 달성해야 합니다.

값에 대한 제약 조건도 중요합니다. 큰 수는 다른 언어에서 오버플로가 발생할 수 있음을 경고하며 모듈러 연산을 암시하기도 합니다.

여러 테스트 문제에서는 각 n이 아니라 n의 합을 제한하는 경우가 많습니다. 반복문을 얼마나 크게 사용해도 안전한지 달라지므로 주의 깊게 읽으십시오.

n에서 목표 복잡도를 정한 다음 그 목표를 달성하는 알고리즘을 선택하십시오. n이 설계를 안내하도록 하면 추측하고 나중에 다시 작성하는 것보다 효과적입니다.

이 표를 머릿속에 기억해 두십시오. 제약 조건-복잡도 대응표가 있으면 대회 중 제한을 빠르게 확인하고 즉시 계획을 세울 수 있습니다.

n을 보고 알맞은 복잡도를 선택해 보십시오.

이제 제약 조건을 목표로 읽을 수 있습니다. n이 작으면 완전 탐색이 가능하고, 10^5에는 n log n이 필요하며, 10^9에는 로그 복잡도나 수학이 필요합니다. n이 접근법을 결정하게 하십시오. 🗺️