프론트엔드 개발자의 기록 공간

[재귀함수, 완전탐색] 중복순열 구하기 본문

알고리즘_JS/인프런 JS알고리즘

[재귀함수, 완전탐색] 중복순열 구하기

[리우] 2022. 4. 2. 21:29

🚩 중복 순열 구하기

 

📖 문제 설명 : 1부터 N까지 번호중 M번을 뽑는 경우의 수를 모두 출력

중복도 가능하므로 [1,1] , [2,2] 등의 중복 숫자도 가능하다.

 

💡 재귀를 이용한다.

 

// 중복순열 구하기 (다중 for문과 재귀의 차이점)

function DFS(n, m, i, arr) {
  // 모든 n 탐색 완료
  if (i >= n || arr.length > m) {
    return
  }

  // n 만큼 조합
  for (let j = 1; j <= n; j++) {
    DFS(n, m, i + 1, [...arr, j])
  }

  // m 조합 개수일 때만 출력
  if (arr.length >= m) console.log(...arr)
}

// 다중 for문의 한계 : m값에 따라 이중for, 삼중for...조건이 바뀜
function forFn(n) {
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= n; j++) {
      console.log(i, j)
    }
  }
}

function solution(n, m) {
  let answer = n ** m

  forFn(n)
  console.log('----------------')
  DFS(n, m, 0, [])

  return answer
}

console.log(solution(3, 2))

위의 코드를 보면 다중 for 문을 활용한 예시도 있다. 하지만 다중 for 문을 이용할 경우 M의 수에 따라 for 문의 수가 달라진다. 예를 들어 2번 뽑는 경우 이중 for, 3번 뽑는 경우 삼중 for 문이 필요하다.

👨‍💻 코드 설

1. 재귀 함수 안에서 반복문을 통해 M 번을 뽑는 수만큼 반복문을 돌려준다.
그러면 M이 어떤 수의 경우에도 M 번 만큼 뽑을 수 있기 때문이다.

2. N과 M의 길이에 따라 적절한 baseCase를 설정하여 종료 조건 및 출력 조건을 제시한다.

 

잘못된 설명, 코드, 예외 케이스가 있다면 댓글 남겨주시면 수정하겠습니다.

728x90
Comments