8-8) 중복순열 구하기
문제
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}와 {2, 1}을 다르게 생각한다.(조합은 같은것으로 침)
- DFS 사용의 효용성
- 얕은복사한 것(tmp)을 push하면, 이미 push한 것이라도 나중 tmp값을 변경한다면 push한 값도 변한다. 따라서, 반드시 slice()메소드를 통해 깊은 복사해준다.
코드
- 문제 풀이 원리는 다음과 같다.
<html>
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<script>
function solution(n, m){
let answer=[];
let tmp=Array.from({length:m}, ()=>0); //길이가 m인 배열 0으로 초기화해서 생성
function DFS(L){
if(L===m){
answer.push(tmp.slice()); //slice는 깊은복사(깊은복사 안하면 마지막갚으로 모두 push됨)
}
else{
for(let i=1; i<=n; i++){
tmp[L]=i; //넣고
DFS(L+1); //다음 레벨로 넘어감
}
}
}
DFS(0);
return answer;
}
console.log(solution(3, 2));
</script>
</body>
</html>Author And Source
이 문제에 관하여(8-8) 중복순열 구하기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@rladpwl0512/8-8-중복순열-구하기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
