2022/04/06) 8. 중복순열 [재귀함수와 완전탐색(DFS:깊이우선탐색)]
1. 문제
<중복순열>
: 1부터 N까지 번호가 적힌 구슬이 있다. 이 중 중복을 허락하여 M번을 뽑아 일렬로 나열하는 방법을 모두 출력한다.
2. 해결방법
- 우선 중복순열이므로, 중복도 가능하고(=같은 구슬 뽑을 수 있음) 1-2랑 2-1도 가능하다는 걸 알고 있자. 그러므로 경우의 수는 n^2이다.
3개의 구슬을 2개씩 뽑아야 한다면,
구슬1을 뽑았을 때(인덱스 0에 1) : 1,2,3 가능(인덱스 1에 1,2,3)
구슬2를 뽑았을 때(인덱스 0에 2) : 1,2,3 가능(인덱스 2에 1,2,3)
... 어 어디서 많이 본 듯한 for문이죠? i를 기준으로 j for문 돌리기!!!
- 왜 다중for문이 아닌 재귀for문으로 코드를 짰을까?
- 만약 다중for문으로 코드를 짜게 된다면 m의 개수에 따라 코드가 바뀐다. 만약 3개를 뽑아야 한다고 하면, 3개의 for문을 생성해야 한다. 즉, m개의 for문을 생성해야 한다는 말!
그러나 재귀함수는 L===m의 조건으로 뻗어나가므로, m의 개수가 코드에 영향을 미치지 않는다.
- tmp를 깊은 복사해야 하는 거 까먹지 않기!! 아직 이해안가는데 나중에 이해되겠지 뭐ㅜ 일단 패스한다.
- 구슬의 번호로 for문을 돌려서 tmp[L]=i해주고, DFS(L+1);해주기!! tmp!!!
이 코드는 인덱스 0에 1을 넣고, 1에 1,2,3을 넣는거다!
3. 정답
<script> function solution(n, m){ let answer=[]; let tmp=Array.from({length:m}, ()=>0); function DFS(L){ if(L===m){ answer.push(tmp.slice()); } else{ for(let i = 1; i <= n; i++){ tmp[L]=i; DFS(L+1); } } } DFS(0); return answer; } console.log(solution(3, 2)); </script>
Author And Source
이 문제에 관하여(2022/04/06) 8. 중복순열 [재귀함수와 완전탐색(DFS:깊이우선탐색)]), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@7lo9ve3/20220406-8.-중복순열-재귀함수와-완전탐색DFS깊이우선탐색저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)