DFS - 중복순열 구하기

2024. 3. 25. 10:50알고리즘

중복순열 구하기

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

 

▣ 입력설명

첫 번째 줄에 자연수 N(3<=N<=10)과 M(2<=M<=N) 이 주어집니다.

 

▣ 출력설명

첫 번째 줄에 결과를 출력합니다. 맨 마지막 총 경우의 수를 출력합니다. 출력순서는 사전순으로 오름차순으로 출력합니다.

 

▣ 입력예제 1

3 2

 

▣ 출력예제 1

1 1

1 2

1 3

2 1

2 2

2 3

3 1

3 2

3 3

9


중복 순열을 구하는 과정을 그림으로 표현하면 다음과 같다.

만일 1,2,3 중에서 중복을 허용하고 순서를 고려해서 2개를 뽑는다면,

2개의 자리마다 각각 3개씩 올 수 있기 때문에 3^2 = 9개의 경우의 수가 생긴다.

 

이 과정을 재귀로 표현했을 때 그림으로 그려보았다.

레벨별로 재귀함수가 호출이 되고 레벨이 뽑고자 하는 갯수 2와 같을 때는 2개를 모두 뽑은 상태가 된다.

이때 출력이든 뭐든 문제가 요구하는 대로 로직 처리를 해주고 다시 원복의 과정을 거쳐야한다.

let a = [];

function solve(n, r, depth) {
  if (depth === r) {
    console.log(a);
    return;
  } else {
    for (let i = 1; i <= n; i++) {
      a.push(i);
      solve(n, r, depth + 1);
      a.pop();
    }
  }
}

solve(3, 2, 0);

 

let a = [];

function solve(n) {
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= n; j++) {
      a.push([i, j]);
    }
  }
  a.forEach(([a, b]) => console.log(a, b));
}

solve(3);

반복문으로도 구현할 수 있다. 하지만 뽑아야하는 수가 많아진다면 그 갯수만큼 내부 for문을 생성해야하기 때문에 비효율적이다.

'알고리즘' 카테고리의 다른 글

DFS - 순열 구하기  (0) 2024.03.28
DFS - 동전 교환  (0) 2024.03.25
DFS - 최대점수 구하기  (0) 2024.03.25
DFS - 합이 같은 부분집합  (0) 2024.03.25
알고리즘 기초 - 골드바흐의 추측 (백준 6588)  (0) 2024.03.18