zheld1217   9달 전

안녕하세요. 문제 풀다가 코드는 짰는데 저는 이중 for문으로 구현하여서 O(N2)이라서 자꾸 시간 초과가 나는 것을 알았습니다. 그렇다면 이 문제는 꼭 O(N)으로만 짜야 통과할 수 있는 문제인건가요?? 그렇다는 것을 문제 풀기 전에 어떻게 알 수 있는 것인가요.. 

sinderella   9달 전

이 문제는 의도적으로 O(N) 또는 O(N log N) 풀이만 통과하게 설계된 문제입니다.

문제를 풀기 전에 “아, 이건 O(N²) 안 되겠구나”를 어떻게 알 수 있을까?
N의 크기를 먼저 본다 (가장 중요)
N의 범위 허용 시간 복잡도
N ≤ 2,000 O(N²) 가능
N ≤ 10⁵ O(N log N)
N ≤ 5×10⁵ O(N)

이 문제는 N = 500,000
 O(N²) 시도 자체가 탈락

zheld1217   9달 전

너무 감사드립니다! 앞으로 N을 먼저 보고 풀이법을 생각해야겠네요.

댓글을 작성하려면 로그인해야 합니다.