1. N과 M (1)
https://www.acmicpc.net/problem/15649
강의에서 제시한 문제 해결 아이디어
- 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 모든 수열을 계산
- 모든 순열의 수를 고려하기 위해 재귀 함수(백트래킹)를 사용할 수 있다.
- 하나의 순열을 트리(tree)에서 리프 노드까지의 경로로 생각할 수 있다.
-> 이때, M개의 원소를 뽑는 순열을 고려하는 것이므로, 깊이(depth)는 M과 같다. - 원소를 중복하여 선택하지 않으므로, 방문처리(visited) 배열을 사용한다.
-> 한 번 선택된 원소는 다음 재귀 함수에서 다시 선택되지 않는다.
제출 답안
let fs = require("fs");
let input = fs.readFileSync("dev/stdin").toString().split("\n");
let [n, m] = input[0].split(" ").map(Number);
let arr = [];
function possible(x, y) {
for (let [a, b] of arr) {
if (a == x || b == y) return false; // 행이나 열이 같다면 X
if (Math.abs(a - x) == Math.abs(b - y)) return false; // 대각선 위치한 경우 X
}
return true;
}
function dfs(row) {
for (let i = 1; i < n; i++) {
if (!possible(row, i)) continue;
arr.push([row, i]);
dfs(row + 1);
}
}
dfs(1);
console.log(arr);-오답 !
정답 예시
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); // [ 1, 2, 3, 4 ]
let visited = new Array(n).fill(false); // [ false, false, false, 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; //[중복X] 이미 처리된 원소라면 무시
selected.push(i); // 현재 원소 선택
visited[i] = true; // 현재 원소 방문 처리
dfs(arr, depth + 1); // 재귀 함수 호출
selected.pop(); // 현재원소 선택 취소
visited[i] = false; // 현재 원소 방문 처리 취소
}
}
dfc(arr, 0);
console.log(answer);2. 모든 순열
https://www.acmicpc.net/problem/10974
강의에서 제시한 문제 해결 아이디어
- N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전 순으로 출력
- N의 값은 최대 8이다.
-> 이때 모든 순열을 출력하므로 최대 경우의 수는 8!개이다.
제출 답안
let fs = require("fs");
let input = fs.readFileSync("dev/stdin").toString().split("\n");
let n = Number(input[0]);
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 x of result) answer += x + " "; // 계산된 순열을 실질적으로 처리하는 부분
answer += "\n";
return;
}
for (let i = 0; i < arr.length; i++) {
// 하나씩 원소 인덱스를 확인하며
if (visited[i]) continue; //[중복X] 이미 처리된 원소라면 무시
selected.push(i); // 현재 원소 선택
visited[i] = true; // 현재 원소 방문 처리
dfs(arr, depth + 1); // 재귀 함수 호출
selected.pop(); // 현재원소 선택 취소
visited[i] = false; // 현재 원소 방문 처리 취소
}
}
dfc(arr, 0);
console.log(answer);정답 예시
제출답안과 동일
3. 0 만들기
https://www.acmicpc.net/problem/7490
강의에서 제시한 문제 해결 아이디어
- 1부터 N까지의 수를 오름차순으로 쓴 수열 [1,2,3, ...N]이 있다고 할때
- 이때 각 수 사이에 사용할 수 있는 연산으로는 다음의 세가지 연산이 있다.
- (-)
- (+)
- 숫자 이어붙이기 (공백)
- 결과적으로 N이 주어졌을때, 수식의 결과가 0이 되는 모든 수식을 찾아야 한다.
- 테스트 케이스 및 자연수 N의 최댓값은 9이다.
- 3개의 연산 중에서 연속적으로 N번 선택하는 중복 순열 문제로 이해할 수 있다.
- 따라서 가능한 전체 경우의 수는 3의 8제곱이다.
정답 예시
let fs = require("fs");
let input = fs.readFileSync("dev/stdin").toString().split("\n");
let testCase = Number(input[0]);
let n = 0;
let arr = [];
for (let tc =1; tc <= testCase; tc++) { // 각 테스트 케이스 처리
n = Number(input[tc]); // 자연수(N) 입력 받기
arr = [];
for (let i = 1; i <= n; i++) arr.push(i) // 1부터 N까지의 수 삽입
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.(str); // 수식의 결과가 0이 되는 경우 출력
return;
}
for (let x of [' ', '+', '-']) { // +,-,혹은 이어붙이기( )
result.push(x);
dfs(result, depth + 1); // 재귀 함수 호출
result.pop();
}
}
