[Algorithm] 순열(Permutation) 경우의 수 구하는 알고리즘 문제(feat. 재귀(Recursion) 함수 사용)

 

 

 

문제

입력값으로 임의의 수 N(1<=N)을 전달받는다. 1부터 N 까지의 숫자들로 구성된 임의의 배열을 생성하고, N개의 배열에서 N개의 요소를 출력할 때 가능한 경우의 수를 순열(Permutation)으로 출력하라.

 

입력값

1<=N

 

예제

예를 들어 N=3 인 경우 임의의 배열은 [1,2,3]이 된다. 이 배열에서 3개의 요소를 출력하는 경우의 수는 3! = 6가지가 나온다. [ '1 2 3' , '1 3 2', '2 1 3', '2 3 1', '3 1 2', '3 2 1' ]을 최종적으로 출력해야 한다.

 

 

풀이

 

① 임의의 배열 startArr을 생성한다.

② 내부 재귀 함수를 생성한다. 재귀 함수 탈출 조건은 시작 시점 start와 배열 전체 길이 len이 같아지는 시점이다. 시작점 start 부터 시작해서 배열의 길이만큼 반복하고 시작지점 start와 현재 요소 i의 위치를 변경해 재귀 함수를 호출한다. 재귀 함수 호출 후 배열의 위치는 원위치 시킨다.

③ 결과값을 담은 resultArr를 반환한다.

 

function permutationCase (N) {

    /*

       작성자 : About-Tech
       일자 : 2022-05-20
       알고리즘 : 재귀 알고리즘
        
    */

    const startArr = [];
    const resultArr = [];

    for(let i=0; i<N; i++){
        startArr[i] = i+1;
    }

	// 재귀함수
    // 클로져 함수
    const recurFunc = (arr, start, len) =>{
    	// 재귀 탈출 조건
        if(start === len){
            resultArr.push(arr.join("-"));
            return;
        }

		// 재귀 로직
        for(let i=start; i<arr.length; i++){
            [arr[start], arr[i]] = [arr[i], arr[start]];
            recurFunc(arr, start+1, len);
            [arr[start], arr[i]] = [arr[i], arr[start]];
        }
    }

    recurFunc(startArr, 0, N);

    return resultArr;

}


// 테스트 케이스
const output = permutationCase(3);
console.log(output);

 

 

함수의 진행과정을 한번 살펴보자.

 

- 1번째 재귀 함수가 call stack에 올라갔다. start = 0 , len=3 으로 탈출 불가능이다.

- for 반복문 내에서 두번째 재귀 함수가 호출된다. start=1, i=1에서 부터 시작한다. 탈출 불가능이다.

- for 반복문 내에서 세번째 재귀 함수가 호출된다. start=2, i=2 탈출 가능하다. 이 때 arr = [1,2,3]이다. 첫번째 출력값이 완성되었다.

- 이제 start=1인 상태로 call stack이 다시 내려오게 된다. i=2가 된다. 탈출 불가능이다. 여기서 arr[1]과 arr[2]의 위치가 변경된다. 즉 arr=[1,3,2]로 변경된다. 네번째 재귀 함수가 호출된다.

- 다섯번째 재귀함수가 호출 될 때 start=2, i=2인 상태로 탈출이 가능하다. 두번째 출력값이 완성되었다. 출력값은 "1-3-2"다.

- 여기까지가 1-X-X 지점이다. 이제 call stack은 start=0인 반복문이 있던 곳까지 내려간다. i는 1이 증가하고 배열의 위치가 변경된다. arr=[1,2,3] -> arr=[2,1,3]

- 이 과정이 "3-2-1"을 출력할 때 까지 반복된다. N이 3인 경우 총 15번의 재귀함수 호출이 발생한다. 

 

                1 번째 call stack
                현재 start = 0
                현재 i = 0
                resultArr = ;
            

                2 번째 call stack
                현재 start = 1
                현재 i = 1
                resultArr = ;
            

                3 번째 call stack
                현재 start = 2
                현재 i = 2
                resultArr = ;
            

                4 번째 call stack
                현재 start = 1
                현재 i = 2
                resultArr = 1-2-3;
            

                5 번째 call stack
                현재 start = 2
                현재 i = 2
                resultArr = 1-2-3;
            

                6 번째 call stack
                현재 start = 0
                현재 i = 1
                resultArr = 1-2-3,1-3-2;
            

                7 번째 call stack
                현재 start = 1
                현재 i = 1
                resultArr = 1-2-3,1-3-2;
            

                8 번째 call stack
                현재 start = 2
                현재 i = 2
                resultArr = 1-2-3,1-3-2;
            

                9 번째 call stack
                현재 start = 1
                현재 i = 2
                resultArr = 1-2-3,1-3-2,2-1-3;
            

                10 번째 call stack
                현재 start = 2
                현재 i = 2
                resultArr = 1-2-3,1-3-2,2-1-3;
            

                11 번째 call stack
                현재 start = 0
                현재 i = 2
                resultArr = 1-2-3,1-3-2,2-1-3,2-3-1;
            

                12 번째 call stack
                현재 start = 1
                현재 i = 1
                resultArr = 1-2-3,1-3-2,2-1-3,2-3-1;
            

                13 번째 call stack
                현재 start = 2
                현재 i = 2
                resultArr = 1-2-3,1-3-2,2-1-3,2-3-1;
            

                14 번째 call stack
                현재 start = 1
                현재 i = 2
                resultArr = 1-2-3,1-3-2,2-1-3,2-3-1,3-2-1;
            

                15 번째 call stack
                현재 start = 2
                현재 i = 2
                resultArr = 1-2-3,1-3-2,2-1-3,2-3-1,3-2-1;

 

 

정리

 

순열은 순서를 고려한 경우의 수를 출력한다. 위 문제에서는 모든 경우의 수를 출력하는 문제인데, 재귀 알고리즘을 사용했다. 핵심은 현재의 위치를 임의로 변경하면서 재귀 탈출 조건을 찾아나가는 과정이다. 이 간단해 보이는 문제를 푸는데 5시간이 넘게 걸렸다.

 

재귀 함수는 클로져 함수로 생성했다. 재귀 함수를 생성할 때 가장 중요한 건, 탈출 조건이다. 이번 문제에서는 시작지점이 함수의 총 길이와 같아지는 시점, 즉 모든 배열의 요소 순회를 마쳤을 때로 지정했다.

 

재귀 함수에 익숙해지는 방법은 다양한 케이스를 풀어보는 수 밖에 없다. Call Stack에 어떤 함수가 쌓이고 있고, 현재 어떤 로직인지 해결이 안되면 Chrome Debuging Tool을 사용하는 방법도 있다.

 

 

Reference

• 재귀 함수란?

 

 

 

 

[Javascript] AJAX란? (feat. Fetch, XHR, 장점 단점)