안녕하세요
백트레킹을 사용할때 일반적으로 항상 모든경우를 전부 따저서 사용했었는데요. n의 범위가 엄청나게 커져버리는경우라면
동적계획법을 사용하여 시간복잡도를 Memoization으로 줄이는걸로 알고있습니다. 그런데 백트레킹을 고수하면서
(top-Down)으로 n!을 2n으로 줄일수 있다고 들었는데 이 방법에 대한 구체적인 방법이 궁금합니다. 어떻게 하면 n!이나 되는
시간복잡도를 2n으로 줄일수 있는건지.... 아니면 2*((n/2)!)으로 줄일수 있다는 걸 제가 잘못이해한건지...
혹시 그렇다면 n! 에서 2*((n/2)!)로 줄일수 있는 방법은 어떤건지도 궁금합니다... 고수님들!
사람한명 살리는셈치고 도와주시면 감사하겠습니다 ㅠㅠㅠ 너무 신경쓰이네요...
백트래킹은 한정문제에서 문제를 풀기 위한 전략으로 dfs를 바탕으로 필요없는 가지는 잘라버리는 가지치기로 시간을 줄일텐데요. 혹시 어떤 문제인가요?
백트래킹이라는 건 하나의 기법일 뿐이지 특정한 시간 복잡도를 가진 구체적인 알고리즘을 말하는 게 아니므로 어떤 문제인지를 알지 못하면 그에 대한 답도 명확히 해드릴 수가 없습니다.
댓글을 작성하려면 로그인해야 합니다.
pda_pro12 6년 전
안녕하세요
백트레킹을 사용할때 일반적으로 항상 모든경우를 전부 따저서 사용했었는데요. n의 범위가 엄청나게 커져버리는경우라면
동적계획법을 사용하여 시간복잡도를 Memoization으로 줄이는걸로 알고있습니다. 그런데 백트레킹을 고수하면서
(top-Down)으로 n!을 2n으로 줄일수 있다고 들었는데 이 방법에 대한 구체적인 방법이 궁금합니다. 어떻게 하면 n!이나 되는
시간복잡도를 2n으로 줄일수 있는건지.... 아니면 2*((n/2)!)으로 줄일수 있다는 걸 제가 잘못이해한건지...
혹시 그렇다면 n! 에서 2*((n/2)!)로 줄일수 있는 방법은 어떤건지도 궁금합니다... 고수님들!
사람한명 살리는셈치고 도와주시면 감사하겠습니다 ㅠㅠㅠ 너무 신경쓰이네요...