[다중 for문과 재귀의 차이]중복순열 구하기

문제

1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 중복을 허락하여 M번을 뽑아 일렬로 나열하는 방법을 모두 출력합니다.

 

문제풀이

트리 DFS 

 

다중 for문과 재귀의 차이

트리 구조를 통해 DFS 탐색을 하는 것은 다중 for문을 하는 것과 전체적인 동작 방식이 똑같다.하지만 왜 해당 문제에서 중복순열을 구할 때 다중 for문이 아닌 재귀 함수를 사용하는 것인지는 다음 코드를 통해 확인할 수 있다.

function solution(n , m) {
  let answer = [];
  
  for(let i = 1; i <= n; i++) {
    for(let j = 1; j <= n; j++) {
      console.log(i , j);
    }
  }
  return answer;
}

console.log(solution(3, 2));

2개의 조합으로 이루어진 중복순열을 구하기 2중 for문을 작성하였다.현재 m은 2이기 때문에 2중 for문 만으로도 모든 중복순열 값을 구할 수 있다.

 

그러나 만약에 뽑아야 될 조합이 3일 경우에는 2중 for문 만으로는 모든 중복순열 값을 구할 수 없다. 이 경우에는 for문을 하나 더추가하여 3중 for문을 해야 된다.

 

이렇듯 다중 for문을 사용한 경우, 주어진 m의 값이 어떤지에 따라 수행해야 되는 for문이 가변적이기 때문에 프로그래밍적으로 매우 비합리적일 뿐만 아니라 수행해야 되는 반복문의 수가 많아지기 때문에 시간 복잡도 상으로도 비효율적이기 때문에 재귀 함수를 이용한 것이다.

 

코드

function solution(n , m) {
  let answer = [];
  let arr = Array.from({length: m}, () => 0);
  
  function DFS(L) {
    if(L === m) {
      answer.push([...arr]); //배열은 주소값을 참조하기 때문에 얕은 복사를 방지하기 위해 스프레드 문법 사용, arr.slice()도 사용 가능
    } 
    else {
        for(let i = 1; i <= n; i++) {
            arr[L] = i;
            DFS(L + 1);
        }
    }
  }

  DFS(0);
  return answer;
}

console.log(solution(3, 2));