인프런 영문 브랜드 로고
인프런 영문 브랜드 로고

인프런 커뮤니티 질문&답변

이준호님의 프로필 이미지
이준호

작성한 질문수

자바스크립트 알고리즘 문제풀이 입문(코딩테스트 대비)

섹션 8의 13번 수열의 추측 시간복잡도 질문 있습니다.

작성

·

158

0

선생님 조합수를 사용해도 시간복잡도는 O(n!)인거 같은데 제가 잘못 생각한걸까요?

조합수를 사용하지 않아도 메모이제이션을 사용하면 O(n!)인거 같아서 질문 드립니다. 

혹시 맞으면 시간복잡도를 O(n^k)정도로 바꿀 수 있는 방법이 있을까요?

조합수를 사용하지 않은 풀이입니다.  비효율적인 부분이나 잘못된점도 알고 싶습니다. 

 function solution(nf){
                const arrayMaker = (lengenerator=> 
                    Array.from({ length: len}, (_i=> generator(i));
                const base = arrayMaker(nidx => idx + 1);
                const checker = arrayMaker(n, () => 0);
                const temp = arrayMaker(n, () => 0);
                const change = i => array => array[i] === 0 ? array[i] = 1 : array[i] = 0;

                function *permutation (position){
                    if(position === n){
                        yield temp;
                    }
                    else{
                        for(let i = 0i < checker.lengthi++){
                            if(checker[i] === 0){
                                temp[position] = base[i];
                                change(i)(checker);
                                yield *permutation(position + 1);
                                change(i)(checker);
                            }
                        }
                    }
                }         
                                
                function combination (nrseq){
                    if(bin[n - 1][r - 1] !== 0return bin[n - 1][r - 1];
                    if(n === 1return seq[r-1];
                    return bin[n - 1][r - 1] = combination(n - 1rseq) + combination(n - 1r + 1seq);
                }
                let bin;
                for(let order of permutation(0)){
                    bin = arrayMaker(n, () => arrayMaker(n, () => 0));
                    ifcombination(n1order) === freturn order;
                }
            }
            console.log(solution(416));

답변 1

0

김태원님의 프로필 이미지
김태원
지식공유자

안녕하세요^^

순열을 돌아야 해서 n! 은 해야 하지 않나 생각됩니다. 더 줄일 수 있는 방법은 모르겠네요.

이준호님의 프로필 이미지
이준호

작성한 질문수

질문하기