1. N과 M(1) (15649)
문제
자연수 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);
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) {
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 < arr.length; i++) {
if (visited[i]) continue; // [중복을 허용하지 않으므로] 이미 처리 된 원소라면 무시
selected.push(i); // 현재 원소 선택
visited[i] = true; // 현재 원소 방문 처리
dfs(arr, depth + 1); // 재귀 함수 호출
selected.pop(); // 현재 원소 선택 취소
visited[i] = false; // 현재 원소 방문 처리 취소
}
}
dfs(arr, 0);
console.log(answer);풀이
- 순열(permutation)을 이용하여 풀기
- 트리를 이용해서 풀기 → 경우의 수: n!
- 모든 순열의 수를 고려하기 위해 재귀 함수(백트래킹)를 사용
- 하나의 순열을 트리에서 리트 노드까지의 경로로 생각 → M개의 원소를 뽑는 순열을 고려하는 것이므로, 깊이(depth)는 M과 같음
- 원소를 중복하여 선택하지 않으므로, 방문 처리 배열 사용 → 한 번 선택된 원소는 다음 재귀 함수에서 다시 선택되지 않음
2. 모든 순열 (10974)
문제
N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다.
출력
첫째 줄부터 N!개의 줄에 걸쳐서 모든 순열을 사전순으로 출력한다.
작성한 코드
let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
let n = Number(input[0]); // 1부터 N까지 자연수 중에서 중복 없이 N개를 고른 수열
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) {
// 모든 순열을 확인하는 부분
if (depth == n) {
let result = []; // 순열 결과 저장 테이블
for (let i of selected) result.push(arr[i]);
for (let i of result) answer += i + " "; // 계산된 순열을 실질적으로 처리하는 부분
answer += "\n";
return;
}
// 하나씩 원소 인덱스를 확인하며
for (let i = 0; i < n; i++) {
if (visited[i]) continue; // 중복을 허용하지 않으므로 이미 처리 된 원소라면 무시
selected.push(i); // 현재 원소 선택
visited[i] = true; // 현재 원소 방문 처리
dfs(arr, depth + 1); // 재귀 함수 호출
selected.pop(); // 현재 원소 선택 취소
visited[i] = false; // 현재 원소 방문 처리 취소
}
}
dfs(arr, 0);
console.log(answer);풀이
- 모든 순열 출력
- 위의 코드와 동일
3. 0 만들기 (7490)
문제
1부터 N까지의 수를 오름차순으로 쓴 수열 1 2 3 ... N을 생각하자.
그리고 '+'나 '-', 또는 ' '(공백)을 숫자 사이에 삽입하자(+는 더하기, -는 빼기, 공백은 숫자를 이어 붙이는 것을 뜻한다). 이렇게 만든 수식의 값을 계산하고 그 결과가 0이 될 수 있는지를 살피자.
N이 주어졌을 때 수식의 결과가 0이 되는 모든 수식을 찾는 프로그램을 작성하라.
입력
첫 번째 줄에 테스트 케이스의 개수가 주어진다(<10).
각 테스트 케이스엔 자연수 N이 주어진다(3 <= N <= 9).
출력
각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다.
작성한 코드
let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
let tc = Number(input[0]); // 테스트 케이스 개수
let n = 0;
let arr = [];
for (let t = 1; t <= tc; t++) {
n = Number(input[t]); // 자연수 N
arr = [];
for (let i = 1; i <= n; i++) arr.push(i);
dfs([], 0);
console.log();
}
function dfs(result, depth) {
// 현재 순열 처리(중복 순열)
if (depth == n - 1) {
let str = ""; // 현재 수식 문자열
for (let i = 0; i < n - 1; i++) str += arr[i] + result[i];
str += arr[n - 1] + "";
current = eval(str.split(" ").join("")); // 공백 제거한 뒤에 수식 계산
if (current == 0) console.log(str); // 수식의 결과가 0이 되는 경우 출력
return;
}
// 더하기, 빼기, 혹은 이어 붙이기
for (let x of [" ", "+", "-"]) {
result.push(x);
dfs(result, depth + 1); // 재귀 함수 호출
result.pop();
}
}풀이
- 각 수 사이에 사용할 수 있는 연산 → 더하기, 빼기, 숫자 이어 붙이기
- 결과적으로 N이 주어졌을 때, 수식의 결과가 0이 되는 모든 수식을 찾아야 함
- 3개 연산 중에서 연속적으로 N번 선택하는 중복 순열 문제로 이해
