wlsgur1843   1년 전

인터넷에서 답을 보고 왔는데 이진트리 전위 순회로 푸는 방법도 시간복잡도가 N^2 이고 

제가 만든 코드도 같은 시간복잡도라고 알고있는데 제가 푼 빽트래킹 방법은 왜 시간초과인지 모르겠습니다 

알려주시면 감사하겠습니다 ㅠ

luckyandykang   1년 전

해당 풀이는 44번 줄의 for 문에서 at이 1 증가할 때마다 모든 재귀 호출에서 n - at 만큼의 dfs를 시행하고 있으므로, 시간 복잡도는 근사적으로 O(N!) 입니다. N <= 20임을 고려해도 시간 초과가 발생할 수밖에 없습니다.

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