인프런 커뮤니티 질문&답변
작성한 질문수
그래프와 탐색- 4. 미로탐색 시간복잡도 관련
작성
·
239
0
안녕하세요 항상 좋은 강의 잘 듣고 있습니다!
선생님께서 가르쳐주신 풀이 방식이 생각한대로 나름 직관적(?)이여서 다른 문제에서도 잘 사용하고 있는데 아무래도 재귀방식이다보니 시간복잡도에서 시간초과가 발생합니다.
이러한 DFS 방식에서 시간복잡도를 낮추는 방법이 있을까요?
또한 선생님께서는 이러한 문제 풀때 시간복잡도 관련해서 어떻게 해결하시나요?(예를들어 다른 풀이방식을 선호한다던지.. 등등)
답변 1
0
김태원
지식공유자
안녕하세요^^
보통 코딩테스트에서 시간제한은 출제자가 작성한 정답코드의 3배 정도로 설정합니다.
그 문제를 출제할 때 DFS를 정답코드로 했다면 DFS짜서 시간초과될 일이 거의 없습니다.
만약 시간 초과가 났다면 정답코드가 DFS가 아닌 다른 해법일 수 있다는 생각을 해야 합니다.
또는 이 문제는 정답코드가 DFS인게 확실한데 내가 짠 DFS코드가 시간초과가 난다면 그건 수학적 사고를 동원해 불필요한 재귀호출을 cut해서 작성해야 통과되는 문제입니다.
답변 감사합니다!