1766번 - 문제집
@zenith82114
그렇군요.. 친절히 알려주셔서 감사합니다. 하나만 더 질문드려도 괜찮을까요?
이런 상황에서는 프로그램 실행시간을 대략적으로 어떻게 계산하면 좋을까요?
저는 단순히 for문이 1억 번 돌아가면 1초가 소요된다고 생각을 했고, 제 코드는 최대 320002번 돌아갈 수 있으니 시간 초과가 날 것이라고 생각을 했었습니다.
그냥 이런 상황이 예외적인 것이라고 생각하고 넘어가는 것이 좋을지, 아니면 다른 n<10만 인 상황에서도 O(n^2)이 돌 것이라고 생각하고 코드를 짜는 것이 좋을지 잘 모르겠습니다.
시간 예측은 단순히 for문 횟수만 세서 할 수 있는 일은 아니고, 많이 반복하고 있는 연산이 무거운지 가벼운지도 살펴봐야 합니다.
지금 코드에서는 O(n^2)번 하게 되는 일이 indegree 배열 읽기와 if 조건 검사로 이들은 매우 가벼운 연산입니다. 정확히는 32000^2가 아닌 1+2+...+32000 ~= 5e8 정도로, 시간제한 1초면 웬만하면 가능하다고 보는 수치입니다. 하지만 std::set에 삽입/삭제를 10^9번 하는 코드가 1초에 돌아가기는 더 어렵다고 예상할 수 있습니다. 어떤 작업이 1초에 몇 번까지 가능한지는 주로 경험을 통해 감이 쌓이게 되고 CS 지식이 있으면 다소 도움이 됩니다.
이 문제 데이터가 부족한것도 있는 것 같습니다. https://www.acmicpc.net/board/... 여기에 데이터 추가 요청을 올렸습니다.
@aiden3233 말씀하신 데이터도 위의 코드로 제 로컬에서 128ms만에 돌아갑니다. 채점 서버 기준으로도 1초가 걸리지 않을 거라 생각합니다.
댓글을 작성하려면 로그인해야 합니다.
yjkim997 8달 전
안녕하세요.
제가 계산하기로 시간복잡도가 O(n2)인 코드를 작성했는데, n<=32000인 범위에서도 왜 시간초과가 나지 않는지 궁금합니다. 채점 데이터의 부족인지, 제가 시간복잡도를 잘못 계산한 건지 잘 모르겠습니다..
혹시 아시는 분들은 알려주시면 감사하겠습니다.
제출 번호는 103194174입니다. 아래에서도 확인해보실 수 있습니다.