14413번 - Poklon
안녕하세요!
Mo's Algorithm을 이용해 문제 14413을 풀었습니다. 다만, 알고리즘 시간 복잡도를 계산할 때 궁금한 점이 있습니다.
Mo's Algorithm의 구간의 길이가 N, 쿼리의 갯수가 Q라고 할 때, 알고리즘의 시간복잡도는
O((N + Q) * sqrt(N) + N) 이라고 알고있습니다.
(출처 : http://www.secmem.org/blog/2019/02/09/mo's-algorithm/)
그런데 이 문제에서 N = 500,000 이고 Q = 500,000 인 상황에서 위 식의 값은
1,000,000 * 707 + 500,000 = 약 7억
입니다.
제한시간이 "5초"인이 문제에서 저는 "값 압축"까지 했는데, 왜 시간초과가 안나왔는지 모르겠습니다.
사실, "1초에 1억번 연산"과 같은 주먹구구식 계산이 항상 정확하지는 않다고도 알고 있습니다.
(출처 : https://book.algospot.com/estimation.html)
그렇다면, 자신이 머릿속에 그린 알고리즘이 제한 시간 안에 풀릴 지 어떻게 알 수 있을까요?
감사합니다.
알고리즘 대회에서 문제를 만들 때, 시간 제한이나 변수의 크기를 정하는 과정에서 어떤 기준으로 정할까요? 그것도 궁금하네요
꼼꼼하게 준비하는 대회라면 여러 테스트를 거쳐서 제한들을 설정합니다. 출제자의 풀이뿐만 아니라 검수진들이 각자 풀이를 짜보고, 출제자가 의도한 방향의 풀이라면 웬만하면 여유있게 통과될 수 있으면서도 의도하지 않은 비효율적인 풀이는 충분히 차단할 수 있는 제한을 설정하기 위해 이리 저리 설정을 바꾸어가면서 적절한 제한을 찾습니다.
또한 저는 개인적으로 1초에 3억보다도, 간단한 연산이 1초에 20억개 정도가 가능하다는 것부터 시작해서 역으로 "1 단위에 몇 개의 복잡한 연산이 필요한가"를 대충 계산해서 속도를 줄여나가는 쪽으로 생각합니다.
댓글 달아주셔서 감사합니다!
"1 단위에 몇 개의 복잡한 연산이 필요한가"에서 속도를 줄여나가는 쪽으로 생각한다는 것은 무엇인지 여쭤봐도 되나요???
다음 두 코드 중에 어느 것이 더 오래 걸릴지 생각해 보세요.
무슨 말씀인지 알겠습니다!
감사합니다!!
댓글을 작성하려면 로그인해야 합니다.
rhtkdwls 6년 전 2
안녕하세요!
Mo's Algorithm을 이용해 문제 14413을 풀었습니다. 다만, 알고리즘 시간 복잡도를 계산할 때 궁금한 점이 있습니다.
Mo's Algorithm의 구간의 길이가 N, 쿼리의 갯수가 Q라고 할 때, 알고리즘의 시간복잡도는
O((N + Q) * sqrt(N) + N) 이라고 알고있습니다.
(출처 : http://www.secmem.org/blog/2019/02/09/mo's-algorithm/)
그런데 이 문제에서 N = 500,000 이고 Q = 500,000 인 상황에서 위 식의 값은
1,000,000 * 707 + 500,000 = 약 7억
입니다.
제한시간이 "5초"인이 문제에서 저는 "값 압축"까지 했는데, 왜 시간초과가 안나왔는지 모르겠습니다.
사실, "1초에 1억번 연산"과 같은 주먹구구식 계산이 항상 정확하지는 않다고도 알고 있습니다.
(출처 : https://book.algospot.com/estimation.html)
그렇다면, 자신이 머릿속에 그린 알고리즘이 제한 시간 안에 풀릴 지 어떻게 알 수 있을까요?
감사합니다.