N과 M (1)

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

입출력 예

입력	출력
4 2	1 2 1 3 1 4 2 1 2 3 2 4 3 1 3 2 3 4 4 1 4 2 4 3

풀이

N과 M 문제 시리즈는 모두 특정 조건을 만족하는 수열을 출력하면 되는 문제이다.
모두 완전 탐색 (brute force)으로 풀 수 있고, 나는 dfs와 재귀 함수 이용해서 풀었다.

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const input = fs.readFileSync(filePath).toString().trim().split(' ').map(Number);

const [N, M] = input;
let answer = [];

const dfs = (arr, visited) => {
	if (arr.length === M) { // 2️⃣ 배열의 길이가 M개라면 answer에 추가한다.
		return answer.push([...arr]);
	}

	for (let i = 1; i <= N; i++) {
		if (!visited[i]) {     // 3️⃣ i를 방문한 적 없다면,
			arr.push(i);       //    배열에 추가하고,
			visited[i] = true; //    방문 처리한다.
			dfs(arr, visited); // 4️⃣ i를 넣은 배열과, i를 방문 처리한 visited를 전달해 dfs 함수를 다시 호출한다.
			visited[i] = false; // 5️⃣ 재귀적으로 호출한 dfs가 종료되면, 이전에 방문 처리해준 i를 다시 false로 돌려놓고,
			arr.pop();          // 배열에서도 제거한다. (이후 다음 i로 반복...)
		}
	}
};

const visited = Array(N + 1).fill(false); // [false, false, false ...]
dfs([], visited); // 1️⃣ 빈 배열과 방문 여부를 담는 visited 배열 전달

answer = answer.map((arr) => arr.join(' ')).join('\n');

console.log(answer);

---

N과 M (2)

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
고른 수열은 오름차순이어야 한다.

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

입출력 예

입력	출력
4 2	1 2 1 3 1 4 2 3 2 4 3 4

풀이

1번 문제와 비슷해보이지만, 이번에는 수열의 순서도 고려해서 중복이 있으면 안된다.

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const input = fs.readFileSync(filePath).toString().trim().split(' ').map(Number);

const [N, M] = input;
let answer = [];

const dfs = (num, arr, used) => {
	if (arr.length === M) { // 2️⃣ 배열의 길이가 M개라면 answer에 추가한다.
		return answer.push([...arr]);
	}

	for (let i = num; i <= N; i++) { // 3️⃣ i를 num부터 시작하게 해서, 중복 수열이 생기는 것을 막는다. 
      							     //    e.g. [1, 2]는 되지만 [2, 1]은 만들어지지 않는다.
		if (!used[i]) { // 나머지 로직은 1번 문제와 동일
			arr.push(i);   
			used[i] = true; 
			dfs(i, arr, used); // 4️⃣ dfs 함수를 호출할 때 num 자리에 i를 전달해준다.
			used[i] = false;
			arr.pop();
		}
	}
};

for (let i = 1; i <= N; i++) {
	const used = new Array(N + 1).fill(false);
	used[i] = true;
	dfs(i, [i], used); // 1️⃣ i와 i를 담은 배열, 사용(방문)했음을 뜻하는 used 배열 전달
}

answer = answer.map((arr) => arr.join(' ')).join('\n');

console.log(answer);

---

N과 M (3)

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

1부터 N까지 자연수 중에서 M개를 고른 수열
같은 수를 여러 번 골라도 된다.

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

입출력 예

입력	출력
4 2	1 1 1 2 1 3 1 4 2 1 2 2 2 3 2 4 3 1 3 2 3 3 3 4 4 1 4 2 4 3 4 4

풀이

2개를 뽑지만 중복이 가능하다. -> 조합 문제
1번 문제와 거의 똑같고, visited 배열만 삭제하면 된다.

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const input = fs.readFileSync(filePath).toString().trim().split(' ').map(Number);

const [N, M] = input;
let answer = [];

const dfs = (arr) => {
	if (arr.length === M) {
		return answer.push([...arr]);
	}

	if (arr.length > M) return;

	for (let i = 1; i <= N; i++) {
		arr.push(i);
		dfs(arr);
		arr.pop();
	}
};


dfs([]);


answer = answer.map((arr) => arr.join(' ')).join('\n');

console.log(answer);