hajongil   1년 전

최빈값을 계산하기 위해 input이 들어오면 바로 입력된 수의 개수를 배열에 더해주도록 코드를 짰습니다.

이전에는 input을 모두 받고 for문을 따로 한 번 더 돌림으로써 배열에 개수를 더해주었는데, 시간초과가 되었습니다.

제 생각에 두 방법의 계산 횟수는 같을 것 같은데 두 번째 방법처럼 for문을 한 번 더 쓰면 시간차이가 많이 나게 되나요?

logicdrive   1년 전

작성자님이 이전에 제출하셔서 시간초과를 받으신 코드를 기준으로 설명하겠습니다. (https://www.acmicpc.net/source...)

9번째 ~ 11번째줄을 보시면 얻어진 숫자배열을 순환하면서 .count() 함수를 이용해서 개수를 구해주고 있습니다.

.count()함수가 특정 숫자의 개수를 구하기 위해서는 배열 전체를 순환해야하므로, 시간 복잡도는 O(n)입니다.

만약, [1, 2, 3, 4, 5]와 같은 배열이 주어졌다고 생각하면, 1을 찾기 위해서 5번 순환하고, 2를 찾기 위해서 5번 순환하고, .... 을 반복하기 때문에 5*5 = 25가 될 것 입니다.

문제를 보시면 배열의 최대 크기는 500000이 될 수 있고, 숫자는 -4000 ~ 4000까지 될 수 있으므로, 10번째 줄이 이미 구해진 값을 제거한다고 해도, 8000번은 반복될 가능성이 있습니다.

이는 500000 * 8000 = 4000000000 = 40억 정도의 반복횟수가 나올 수 있음을 의미합니다.

CPU의 연산량을 보수적으로 추정하면, 1초당 1억번정도의 연산을 수행한다고 볼 수 있고, 해당 문제의 시간제한은 2초이고 백준의 Python 시간제한 보너스를 고려하면 2*3+2 = 8초의 시간제한이 됩니다.

즉, 40억은 1억*8초=8억과 비교해서 5배나 크므로, Pypy3의 빠른 실행속도를 고려해도 시간제한이 난다는 결론이 됩니다.

hajongil   1년 전

count를 사용할 경우 연산 수가 급격하게 증가할 수 있다는 점을 이해할 수 있었습니다. count 뿐만 아니라 다른 함수들을 사용할 때에도 연산 수가 크게 늘어날 지 고민해볼 필요가 있을 것 같습니다.

친절한 답변 감사드립니다.

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