Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
Tags
- Vue3
- KDT 프로그래머스 데브코스 프론트엔드
- 우테캠 회고록
- 리팩토링 회고
- 프로그래머스 K_Digital Training 프론트엔드
- KDT 프로그래머스
- react customHook 예시
- 모던 자바스크립트 TIL
- Vue3 Router
- frontend roadmap study
- K_Digital Training
- 프로그래머스 데브코스 프론트엔드 TIL
- 프로그래머스 데브코스
- 모던 자바스크립트 Deep Dive
- 모던 자바스크립트 Deep Dive TIL
- 프로그래머스 K_Digital Training
- 모던 javascript Deep Dive
- 머쓱이
- TypeScript 문법 소개
- useEffect return
- 인프런 자바스크립트 알고리즘 문제풀이
- 투포인터알고리즘 js
- 모던 자바스크립트 딥다이브
- react 프로젝트 리팩토링
- 개발자 특강
- 백준 node.js
- 프로그래머스 데브코스 프론트엔드
- Frontend Roadmap
- 백준 js
- useRef 지역 변수
Archives
- Today
- Total
프론트엔드 개발자의 기록 공간
[재귀함수, 완전탐색] 중복순열 구하기 본문
🚩 중복 순열 구하기
📖 문제 설명 : 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
'알고리즘_JS > 인프런 JS알고리즘' 카테고리의 다른 글
[재귀함수, 완전탐색] 조합 구하기 (0) | 2022.04.03 |
---|---|
[재귀함수, 완전탐색] 순열 구하기 (0) | 2022.04.02 |
[재귀함수, 완전탐색] 합이 같은 부분집합 (0) | 2022.04.02 |
[이분 탐색] 마구간 정하기 (0) | 2022.04.02 |
[이분 탐색] 뮤직비디오 (0) | 2022.04.01 |
Comments