인프런 커뮤니티 질문&답변
작성한 질문수
1-I문제 / 시간 빡세다의 정의 궁금증
해결된 질문
작성
·
316
·
수정됨
0
우선 강의를 보고 밑의 코드를 넣어서 문제는 해결한 상태입니다. 아마 시간초과 난 부분도 I/O 부분에서 많이 잡아먹어서 그런 것 같습니다.
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
강의 내용 중에 시간초과가 빡세서 위의 코드를 넣어야 한다고 했는데, 코드를 넣는 것과는 별개로 어떻게 시간초과가 빡센지 문제를 풀면서 생각할 수 있을까요?? 제 논리구조는 아래와 같습니다.
첫 번째 반복문 O(NlogN)
코드 상 첫번째 반복문에서는 입력을 N번 받고, map에 넣는 경우는 O(logN)
두 번째 반복문 O(M * (logN + T))
우선 M번 반복하고, 반복할 때마다 문제를 받는데, 해당 문제의 input을 int로 변환하는 과정 O(T) (문자열 길이 T가정)
map에서 탐색하는 과정 O(logN)
=> 총 시간복잡도 = O(N *( log(N) + T )(M과 N의 최대 범위 같으니 동치해 봤습니다)
사실상 T의 길이도 최대 20이어서 미미해서 O(NlogN)이라고 판단했습니다.
저는 1초 = c++에서 1억번이라고 들어서 그것을 기준으로 잡고 해봤습니다.(혹시 이렇게 정의해도 되는건지요?) 단순히 입력값으로 계산만 해봐서는 100000 * log(100000) = 약 160~170만
최대 20자인 문자열을 고려해도 => 약 3000만회
널널하다고 생각
이렇게 해서 저는 시간초과가 생각보다 빡세지 않다고 생각했는데, 제가 한 논리중에 잘못된 부분이 있는지도 궁금하고, 어떻게 하면 이 문제에서 1초라는 시간초과가 빡세다는 점을 캐치할 수 있는지 궁금합니다.
감사합니다
답변 1
1
안녕하세요 ㅎㅎ
생각의 흐름 자체가 좋습니다.
사실상 T의 길이도 최대 20이어서 미미해서 O(NlogN)이라고 판단했습니다.
>> 네 맞습니다.
우선 M번 반복하고, 반복할 때마다 문제를 받는데, 해당 문제의 input을 int로 변환하는 과정 O(T) (문자열 길이 T가정)
>> 네 맞습니다.
저는 1초 = c++에서 1억번이라고 들어서 그것을 기준으로 잡고 해봤습니다.
>> 아닙니다. 그럴 수도 있고 아닐 수도 있습니다.
어떻게 하면 이 문제에서 1초라는 시간초과가 빡세다는 점을 캐치할 수 있는지
>> 먼저 1초라고 해서 빡세다는 것이 아닙니다. 빡세다라는 것의 근거는.
어떠한 맞는 로직을 제출했을 때의 private TC가 통과되었지만 시간초과가 났다는 근거하에 빡세다라는 것을 알 수 있습니다.
예를 들어 처음에 짠 로직 자체가 O(N)인데 알고보니 이 문제의 시간초과가 타이트해서 시간초과가 뜬 경우 조금 더 효율적인 로직을 생각해야 합니다.
즉, 제출을 하면서 빡세다라는 것을 유추해야 합니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
럼 해당 문제는 최대 20만개의 input이 들어올 수 있으니 I/O가 빡세다는 점을 유추해서 저 코드를 넣어야겠다 이렇게 하는 것이 좋나요??
>> 아니요 cin을 썼는데 시간초과가 난다 -> ios 등을 넣는게 좋습니다. 애초에 코테 볼 때 저걸 넣고 시작하는게 좋습니다.
혹시 그러면 문제에서 시간 제한이 있을 경우에는 이것을 어떻게 활용해야 하는지요?? 예를 들면 N의 범위가 10만이이고 시간이 2초니 O(Nlogn)까지는 고려해볼스 있겠다 이렇게 정형화된 방법은 없나요??
>> 초를 기반으로 시간초과 유추하는 것은 불가능합니다. N의 범위가 10만이면 N^2은 1억이 넘어가게 됩니다. 보통의 문제는 1억 또는 10억이면 시간초과가 납니다.
N의 범위가 10만 -> N^2의 알고리즘이 생각남 -> 1억이 넘네? -> 이거 말고는 없을까?
-> 없는 거 같은데 -> 제출 -> 시간초과 -> 조금 더 효율적인거 없을까.. 이분탐색이나 정렬 등을 이용한다면? map을 사용한다면? -> 알고리즘 개선 및 제출
이런식의 플로우를 빠르게 하는 것을 연습하시면 됩니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
아 답변 감사합니다! 그럼 해당 문제는 최대 20만개의 input이 들어올 수 있으니 I/O가 빡세다는 점을 유추해서 저 코드를 넣어야겠다 이렇게 하는 것이 좋나요??
혹시 그러면 문제에서 시간 제한이 있을 경우에는 이것을 어떻게 활용해야 하는지요?? 예를 들면 N의 범위가 10만이이고 시간이 2초니 O(Nlogn)까지는 고려해볼스 있겠다 이렇게 정형화된 방법은 없나요??
제가 놓친건지 공간복잡도 관련해서는 교안에 한번 정리해주신것같은데 문제의 시간 제한을 실전에서는 값의 범위, 입력 개수 등과 어떻게 활용해야 할지 감이 아직 잘 안옵니다