dkwkekzz   1년 전

이 문제 뿐만 아니라 수많은 문제에서 항상 시간초과가 나옵니다.

더 이상 반복루프를 줄일 수 없을 것 같은데 계속 시간초과가 나오니 뭔가 제가 모르는 원리가 있는 것이라고 생각하는 것이죠.

그게 뭔지좀 알려주세요.

하필 이문제는 왜 또 다른사람 코드를 볼수가 없나요 좀 배울려고 하는데 ㅋㅋ당황스럽고

도대체 뭘해야 시간을 줄일 수있 는지좀 알려주세요. 시간초과라는게 뭔소리인지좀 알려주세요. 필요한 개요를 알려주셔도 되고 뭐든 괜찮습니다.

포인터로접근하는건가요?

포인터로 접근하면 뭐가 달라지는게 없을 것 같은데 그것이라면 역시 이해가 안됩니다.

간절히 부탁합니다 알려주세요^^

dotorya   1년 전

시간 복잡도라는 개념을 정확히 이해하셔야 합니다.

위 알고리즘의 경우는 M개 각각의 숫자를 최대 N번 비교하게 되므로, 최대 NM = 10^5 * 10^5 = 10^10번의 비교 연산을 수행하게 됩니다.

이것을 위 알고리즘이 O(NM)의 시간복잡도를 가지고 있다고 이야기합니다.

일반적으로 채점 서버에서 프로그램이 1초 동안 수행할 수 있는 연산의 횟수는 10^8~9 정도입니다. 따라서 위 알고리즘을 실행하는 데 약 10~100초 정도의 시간이 걸리게 됩니다.

이것은 문제에서 요구한 프로그램의 수행 시간보다 길므로 시간 초과가 발생할 것입니다.


위 문제는 O(NM)보다 더 짧은, O((M+N) logN)의 시간 복잡도로 해결할 수 있습니다.

비교 연산을 NM번보다 적게 수행하는 알고리즘을 생각해야 하겠죠?

baekjoon   1년 전

소스 보기는 문제를 풀어야 볼 수 있습니다.

뭘 풀어도 시간 초과가 나는 것은 문제 풀이를 처음 시작할 때 흔히 겪는 상황인데, 효율적인 알고리즘을 이용해서 문제를 풀지 않았기 때문입니다.

예를 들어, 이 문제의 경우에는 이분 탐색을 사용해서 풀어야 합니다. 아마도 시간 초과가 나는 이유는 각각의 숫자를 찾을 때마다 전체 숫자에서 숫자를 하나씩 찾아서일텐데, 이 방법은 어떤 방법을 사용해도 시간 초과를 받게 됩니다.

창의적인 방법을 새로 생각해낼 필요는 없고, 이미 존재하는 알고리즘을 공부해서 문제를 풀면 됩니다.

알고리즘 문제해결전략 책 추천합니다.

http://book.algospot.com/

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