안녕하세요 선생님

21.03.18 12:26 작성 조회수 176

dp로도 풀어보았고 DFS로도 풀어봤습니다. DFS는 경우의 수가 너무 많아 타임아웃이 나더라구요!

이런 경우의 수 문제를 풀 때 dp와 DFS 중 어떤 것을 적절히 적용해야하는 지 팁이 있을까요??

감사합니다.

파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)

7. 알리바바와 40인의 도둑(Bottom-Up)

강의실 바로가기

답변 2

좋아요순

최신순

답변을 작성해보세요.

김태원

2021.03.19

안녕하세요^^

dfs는 트리형태의 깊이 탐색을 하는데 그 깊이 즉 레벨값이 보통 20~25를 넘지 않아야 1초 타임 리밋을 피한다고 보통 생각합니다. 뭐 적절히 컷에지를 하면 30정도까지도 해 볼 수 있구요. 하지만 50, 100 이런 깊이면 다이나믹이라 생각하면 됩니다.

박진호

2021.03.19

감사합니다 선생님!!