pda_pro12   6년 전

안녕하세요 

백트레킹을 사용할때 일반적으로 항상 모든경우를 전부 따저서 사용했었는데요. n의 범위가 엄청나게 커져버리는경우라면 

동적계획법을 사용하여 시간복잡도를 Memoization으로 줄이는걸로 알고있습니다.  그런데 백트레킹을 고수하면서 

(top-Down)으로 n!을 2n으로 줄일수 있다고 들었는데 이 방법에 대한 구체적인 방법이 궁금합니다. 어떻게 하면 n!이나 되는

시간복잡도를 2n으로 줄일수 있는건지.... 아니면 2*((n/2)!)으로 줄일수 있다는 걸 제가 잘못이해한건지...

혹시 그렇다면 n!  에서 2*((n/2)!)로 줄일수 있는 방법은 어떤건지도 궁금합니다... 고수님들! 

사람한명 살리는셈치고 도와주시면 감사하겠습니다 ㅠㅠㅠ 너무 신경쓰이네요...

donghy9508   6년 전

백트래킹은 한정문제에서 문제를 풀기 위한 전략으로 dfs를 바탕으로 필요없는 가지는 잘라버리는 가지치기로 시간을 줄일텐데요. 혹시 어떤 문제인가요?

djm03178   6년 전

백트래킹이라는 건 하나의 기법일 뿐이지 특정한 시간 복잡도를 가진 구체적인 알고리즘을 말하는 게 아니므로 어떤 문제인지를 알지 못하면 그에 대한 답도 명확히 해드릴 수가 없습니다.

pda_pro12   6년 전

이번 1월 21일이 치뤘던 모 기업 a형테스트였습니다만 

과자가 n개주어지고 과자 n개에 대한 이름이 각각 문자열로 주어져있는데요 각 과자의 가격도 주어지구요

그런데 여기서 어떤 만들고싶은 하나의 문자열이 주어질때 과자봉지에 있는 글자를 오려서 만들려는 문제입니다. 

과자의 글자를 한글자씩 오려서 만들려면 과자를 구입해야하는거구요 !

이때 최소의비용으로 글자를 만들기위해 구입하게 되는과자의 비용을 구하는 겁니다! ㅠㅠ

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