[알고리즘] JavaScript로 조합, 중복조합, 순열, 중복순열 구현하기

✅ 들어가며 

최근에 알고리즘 문제풀이 언어를 Python에서 JavaScript로 변경했다. 

JS 대신에 Py를 코테 언어로 사용해본 결과 느낀 장점은 다음과 같다.

- 문제 해결을 위한 방법론에만 집중하고, 세세한 구현은 내장 모듈을 활용하고 간결한 문법구조로 구현할 수 있었기 때문에 더 빠르게 다양한 문제를 풀고, 알고리즘 문제풀이 전체에 대한 감을 빠르게 쌓을 수 있었다. 

 

하지만 알고리즘 스터디를 통해서 다른 언어를 사용하는 팀원들과 답안을 교환해본 결과, 답안의 길이나 문제 풀이 소요시간에서 분명한 차이가 있음을 확인할 수 있었다. 

 

따라서 JS를 주요 언어로 사용하는 입장에서 Python을 활용한 문제풀이가 진짜 내 실력이 아니라고 느꼈고, JS로 동일한 수준의 실력을 쌓아야겠다고 마음먹었으며 JavaScript로 알고리즘 문제 풀이를 다시 하고 있다. 

 

이번 글에서는 Python에서 유용하게 사용했던 라이브러리를 JavaScript로 직접 구현해 보고자 한다. 

---

 

Python에서 가장 유용하게 사용했던 라이브러리는 itertools이다. 

 

itertools는 아래 링크를 참고하길 바란다.

 

[Python] 순열, 조합 , 중복순열, 중복조합

 

itertools 내부에는 순열, 조합, 중복순열 등의 경우의 수를 확인할 수 있는 매우 강력한 모듈이 제공되고 있으며, 이 모듈을 활용하면 '완전탐색' 문제의 대부분을 매우 손쉽게 풀 수 있다. 

 

이에 반해 JavaScript는 해당 라이브러리가 존재하지 않기 때문에 매 문제에 직접 구현해야 하고, 문제의 난이도가 급격하게 올라간다. 

 

따라서 이번에는 JavaScript로 경우의 수를 구하는 함수들을 미리 구현하며 익숙해질 필요가 있다.

 

✅ 구현

기본적으로 전체 경우의 수를 방문해야 하기 때문에 익숙한 구조인 깊이우선 탐색 dfs를 활용해서 일관성있게 구현하고자 한다. 

 

🔸 중복순열 Permutation with repetition 

dfs를 활용해서 전체 경우의 수를 순회하고, 원하는 조건이 되면 탈출하는 형식으로 구현한다. 

//! 중복순열(permutation with repetition)
function permutationWithRep(arr,n){		//array와 원하는 길이 n을 파라미터로 전달
    let result=[]
    
    function dfs(current){	//dfs 활용해서 탐색한다.
    	// 현재 전달된 current가 우리가 원하는 배열의 길이와 동일하다면 탈출
        if (current.length ===n){
            result.push([...current])
            return 
        }
        
        // 원하는 조건이 아니라면 current에 원소를 돌아가며 하나씩 추가해주며 순회한다.
        for (let i=0; i<arr.length;i++){
            current.push(arr[i]);   //current에 원소를 넣어준다. 
            dfs(current)
            current.pop()   //반복 없애기 위해 방금 넣었던 원소를 빼주고 다음 반복문으로 넘어간다. 
        }
    }
    dfs([])

    return result
}

console.log(permutationWithRep([1,2,3],3))

 

🔸 순열 Permutation

중복순열과 다르게 요소가 중복되면 안된다. 

따라서 처음에는 아래와 같이 간단한 코드가 나왔다.

>>> 방법1

//! 순열(permutation)
function permutation(arr,n){   
    let result =[]
    
    function dfs(current){
        if(current.length===n){
            result.push([...current])
            return 
        }
        for(let i=0; i<arr.length;i++){
            if(!current.includes(arr[i])){	//current에 해당 요소 포함여부 확인 후 push해준다.
                current.push(arr[i])
                dfs(current)
                current.pop()
            }
        }
    }
    dfs([])
    
    return result
}

 

하지만 위 코드에서는 current.includes() 메서드를 사용하고 있는데 이는 시간복잡도가 O(n)으로 보이기에 효율성 측면에서 불리하다.

 

따라서 아래와 같이 수정한다.

>>> 방법2

//! 순열(permutation)
function permutation(arr,n){   
    let result =[]
    const visited = Array(arr.length).fill(false); // 방문 여부를 체크할 배열
    
    function dfs(current){
        if(current.length===n){
            result.push([...current])
            return 
        }
        for(let i=0; i<arr.length;i++){
            if(!visited[i]){    //방문 여부 체크 후
                visited[i]=true     //방문처리
                current.push(arr[i])
                dfs(current)
                current.pop()
                visited[i]=false    //다음 반복을 위해 미방문 처리
            }
        }
    }
    dfs([])
    
    return result
}

방문 여부를 체크할 배열 visited를 먼저 선언하고 dfs의 for문 안에서 방문 여부를 체크한다.

이렇게 하면 방문 여부를 조회하는 것이 O(1)이므로 효율성 측면에서 이전 코드보다 이점이 있다.

 

 

 

---

🔸 중복조합 Combination with repetition

위의 순열을 이해했다면 아래 코드는 이해하기 용이할 것이다. 

아래 주석과 같이 순열과 조합의 차이를 이해하고 코드를 살짝 바꾸면 된다.

  //! 중복조합(combination with repetition)
function combinationWithRep(arr, n){
    let result=[]

    function dfs(current,idx){
        if (current.length===n){
            result.push([...current])
            return
        }
        //조합과 순열의 차이점을 반영해야 한다. 조합에서는 [1,2,3]과 [3,2,1]은 동일한 경우의 수로 판단한다.
        for(let i=idx; i<arr.length;i++){   //i=idx로 놓음으로써 조합으로 구현되도록 함.
            current.push(arr[i])
            dfs(current,i)
            current.pop()
        }
    }
    dfs([],0)
    return result
}

 

 

🔸 조합 Combination

조합은 중복조합과 달리 요소의 중복을 허용하지 않는다. 

이를 유념해서 작성하면 된다.

//! 조합(combination)
function combination(arr,n){
    let result=[]
    function dfs(current,idx){
        if(current.length===n){
            result.push([...current])
            return
        }
        for(let i=idx;i<arr.length;i++){
            // 조합은 요소의 중복을 허락하지 않는다. 따라서 현 인덱스를 넣었다면 다시 반복되지 않도록 다음 dfs에는 i+1을 넘겨주어야 함
            current.push(arr[i])
            dfs(current,i+1)
            current.pop()
        }
    }
    dfs([],0)
    return result
}