4. N과 M(2) (15650)
문제
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
- 고른 수열은 오름차순이어야 한다.
입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
작성한 코드
let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
let [n, m] = input[0].split(" ").map(Number); // 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 조합
let arr = []; // 조합을 계산하고자 하는 원소가 담긴 배열
for (let i = 1; i <= n; i++) arr.push(i);
let visited = new Array(n).fill(false); // 각 원소 인덱스별 방문 여부
let selected = []; // 현재 조합에 포함된 원소
let answer = "";
function dfs(arr, depth, start) {
// 모든 조합을 확인하는 부분
if (depth == m) {
let result = []; // 조합 결과 저장 테이블
for (let i of selected) result.push(arr[i]);
for (let x of result) answer += x + " "; // 계산된 조합을 실질적으로 처리하는 부분
answer += "\n";
return;
}
// start 지점부터 하나씩 원소 인덱스를 확인하며
for (let i = start; i < arr.length; i++) {
if (visited[i]) continue; // 중복을 허용하지 않으므로 이미 처리 된 원소라면 무시
visited[i] = true; // 현재 원소 방문 처리
selected.push(i); // 현재 원소 선택
dfs(arr, depth + 1, i + 1); // 조합이므로, 재귀 함수 호출 시 다음 인덱스 넣기
selected.pop(0); // 현재 원소 선택 취소
visited[i] = false; // 현재 원소 방문 처리 취소
}
}
dfs(arr, 0, 0);
console.log(answer);풀이
- 1 부터 N까지 자연수 중에서 중복 없이 M개를 고른 모든 조합 계산 → 오름차순!
- 재귀함수를 호출할 때마다 선택되는 값이 커지도록 하는 것이 핵심! → 순열 소스 코드와 다른 점은 start 변수가 사용됨
5. N과 M(3) (15652)
문제
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터 N까지 자연수 중에서 M개를 고른 수열
- 같은 수를 여러 번 골라도 된다.
입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
작성한 코드
let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
let [n, m] = input[0].split(" ").map(Number); // 1부터 N까지 자연수 중에서 M개를 고른 중복 순열
let arr = []; // 중복 순열을 계산하고자 하는 원소가 담긴 배열
for (let i = 1; i <= n; i++) arr.push(i);
let selected = []; // 현재 중복 순열에 포함된 원소
let answer = "";
function dfs(arr, depth) {
// 모든 중복 순열을 확인하는 부분
if (depth == m) {
let result = []; // 중복 순열 결과 저장 테이블
for (let i of selected) result.push(arr[i]);
for (let x of result) answer += x + " "; // 계산된 중복 순열을 실질적으로 처리하는 부분
answer += "\n";
return;
}
// 하나씩 원소 인덱스 확인하며
for (let i = 0; i < n; i++) {
selected.push(i); // 현재 원소 선택
dfs(arr, depth + 1); // 재귀 함수 호출
selected.pop(i); // 현재 원소 선택 취소
}
}
dfs(arr, 0);
console.log(answer);풀이
- 중복 순열 → 같은 수 여러 번 골라도 됨 → visited 변수 제거
6. N과 M(4) (15653)
문제
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터 N까지 자연수 중에서 M개를 고른 수열
- 같은 수를 여러 번 골라도 된다.
- 고른 수열은 비내림차순이어야 한다.
- 길이가 K인 수열 A가 A ≤ A ≤ ... ≤ A ≤ A를 만족하면, 비내림차순이라고 한다.
입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
작성한 코드
let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
let [n, m] = input[0].split(" ").map(Number); // 1부터 N까지 자연수 중에서 M개를 고른 중복 순열
let arr = []; // 중복 순열을 계산하고자 하는 원소가 담긴 배열
for (let i = 1; i <= n; i++) arr.push(i);
let selected = []; // 현재 중복 순열에 포함된 원소
let answer = "";
function dfs(arr, depth, start) {
// 모든 중복 조합을 확인하는 부분
if (depth == m) {
let result = []; // 중복 조합 결과 저장 테이블
for (let i of selected) result.push(arr[i]); // 계산된 중복 조합을 실질적으로 처리하는 부분
for (let x of result) answer += x + " ";
answer += "\n";
return;
}
// start 지점부터 하나씩 원소 인덱스 확인하며
for (let i = start; i < n; i++) {
selected.push(i); // 현재 원소 선택
dfs(arr, depth + 1, i); // 조합이므로, 재귀 함수 호출 시 다음 인덱스 넣기
selected.pop(); // 현재 원소 선택 취소
}
}
dfs(arr, 0, 0);
console.log(answer);풀이
- 오름차순이라는 점에서 조합 이해 → 중복 순열!
- 재귀 함수를 호출할 때마다 선택되는 값이 커지도록! ⇒ start 변수 사용
- 중복 방문 가능하므로 ⇒ visited 변수 제거
