1. 중복 가능, 순서 상관없는 경우
1) 문제 - https://www.acmicpc.net/problem/15651
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터 N까지 자연수 중에서 M개를 고른 수열
- 같은 수를 여러 번 골라도 된다.
- 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)
2) 접근 방식
(1) 완전 탐색 효율성 여부
- M개의 자리에 N개의 중복된 수가 올 수 있으므로 O(N^M)이다.
- 문제의 경우의 수는 7^7이므로 82만 즉, 1초에 1억번의 연산을 한다고 가정했을 때 1초안에 연산 가능
(2) 구현 전략
- 각 경우의 수를 output 배열에 담고 M의 자리수와 일치하면 재귀를 종료한다.
- 재귀를 돌며 맨 마지막 자리에 N의 숫자를 변경하면서 output 배열에 담고, N의 숫자를 모두 사용시 그 이전자리 숫자에 N숫자를 적용한다.
- 재귀가 끝난 후 output에 초기값 0을 할당한다.
- 첫째자리까지 다시 오면 위 과정을 반복하여 마지막 N의 숫자까지 반복한다.
3) 구현
const solution = (n: number, m: number) => {
let result = "";
const output: number[] = [];
const rec_fuc = (k: number) => {
// 같아지는 순간이 재귀 종료 시점
if (k === m) {
result += `${output.join(" ")}\n`;
return;
}
// k번째 자리에 n숫자를 번갈아가면서 넣어주기
for (let i = 0; i < n; i++) {
output[k] = i + 1;
// 재귀를 돌며 k + 1 자리에 n번 또 반복 한다.
rec_fuc(k + 1);
// 재귀 끝부터 빠져나오면서 해당 k자리를 초기화 해준다.
output[k] = 0;
}
};
rec_fuc(0);
return result;
};
solution(3,3);2. 중복 불가, 순서 상관없는 경우
1) 문제 - https://www.acmicpc.net/problem/15649
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
2) 접근 방식
(1) 완전 탐색 효율성 여부
- M개의 자리에 N개의 중복된 수가 없으므로, N:4,M:3인 경우 4!이다.
- 조건이 (1 ≤ M ≤ N ≤ 8)이므로 완전 탐색 가능
(2) 구현 전략
- 각 경우의 수를 output 배열에 담고 M의 자리수와 일치하면 재귀를 종료한다.
- 재귀를 돌며 맨 마지막 자리에 N의 숫자를 변경하면서 output 배열에 담고, N의 숫자를 모두 사용시 그 이전자리 숫자에 N숫자를 적용한다.
- 위 과정 중 이전에 N의 숫자를 사용했다면 해당 숫자 재귀는 생략한다.
- 재귀가 끝난 후 output에 초기값 0을 할당한다.
- 첫째자리까지 다시 오면 위 과정을 반복하여 마지막 N의 숫자까지 반복한다.
3) 구현
const solution = (n: number, m: number) => {
let result = "";
const output: number[] = [];
const used: number[] = [];
const rec_fuc = (k: number) => {
// 같아지는 순간이 재귀 종료 시점
if (k === m) {
result += `${output.join(" ")}\n`;
return;
}
// k번째 자리에 n숫자를 번갈아가면서 넣어주기
for (let i = 0; i < n; i++) {
if (!used[i]) {
// k번째 자리에 i + 1값을 기입
output[k] = i + 1;
// i번째 자리 숫자를 사용했으므로 기입
used[i] = 1;
// 재귀를 돌며 k + 1 자리에 n번 또 반복 한다.
rec_fuc(k + 1);
// 재귀 끝부터 빠져나오면서 해당 k자리를 초기화 해준다.
output[k] = 0;
// 재귀 끝부터 빠져나오면서 해당 i번자리 초기화
used[i] = 0;
}
}
};
rec_fuc(0);
return result;
};
solution(3,3);3. 중복 가능, 순서 오름차순
1) 문제 - https://www.acmicpc.net/problem/15652
2) 접근 방식
(1) 완전 탐색 효율성 여부
- M개의 자리에 N개의 중복된 경우의 수보다는 내림차순이므로 작다.
- 조건이 (1 ≤ M ≤ N ≤ 8)이므로 완전 탐색 가능
(2) 구현 전략
- 각 경우의 수를 output 배열에 담고 M의 자리수와 일치하면 재귀를 종료한다.
- 재귀를 돌며 맨 마지막 자리에 N의 숫자를 변경하면서 output 배열에 담고, N의 숫자를 모두 사용시 그 이전자리 숫자에 N숫자를 적용한다.
- 위 과정 중 오름차순 && 중복 가능이므로 시작점을 이전값으로 설정한다.
- 재귀가 끝난 후 output에 초기값 0을 할당한다.
- 첫째자리까지 다시 오면 위 과정을 반복하여 마지막 N의 숫자까지 반복한다.
3) 구현
const solution = (n: number, m: number) => {
let result = "";
const output: number[] = [];
const rec_fuc = (k: number) => {
// 같아지는 순간이 재귀 종료 시점
if (k === m) {
result += `${output.join(" ")}\n`;
return;
}
let start = output[k - 1];
// 초기설정
if (!start) start = 1;
// k번째 자리에 i숫자를 넣어주는데 시작점은 중복 허용하므로 전 값이다.
// for문 횟수가 전보다 한번 줄어드므로 i <= n 진행
for (let i = start; i <= n; i++) {
// k번째 자리에 i값을 기입
output[k] = i;
// 재귀를 돌며 k + 1 자리에 n번 또 반복 한다.
rec_fuc(k + 1);
// 재귀 끝부터 빠져나오면서 해당 k자리를 초기화 해준다.
output[k] = 0;
}
};
rec_fuc(0);
return result;
};
solution(3,3);4. 중복 불가, 순서 오름차순
1) 문제 - https://www.acmicpc.net/problem/15650
2) 접근 방식
(1) 완전 탐색 효율성 여부
- 조건이 (1 ≤ M ≤ N ≤ 8)이므로 완전 탐색 가능
(2) 구현 전략
- 각 경우의 수를 output 배열에 담고 M의 자리수와 일치하면 재귀를 종료한다.
- 재귀를 돌며 맨 마지막 자리에 N의 숫자를 변경하면서 output 배열에 담고, N의 숫자를 모두 사용시 그 이전자리 숫자에 N숫자를 적용한다.
- 위 과정 중 오름차순 && 중복 불가이므로 시작점을 이전값 + 1로 설정한다.
- 재귀가 끝난 후 output에 초기값 0을 할당한다.
- 첫째자리까지 다시 오면 위 과정을 반복하여 마지막 N의 숫자까지 반복한다.
3) 구현
const solution = (n: number, m: number) => {
let result = "";
const output: number[] = [];
const used: number[] = [];
const rec_fuc = (k: number) => {
// 같아지는 순간이 재귀 종료 시점
if (k === m) {
result += `${output.join(" ")}\n`;
return;
}
// 초기설정
let start = (output[k - 1] ? output[k - 1] : 0) + 1;
// k번째 자리에 i숫자를 넣어주는데 시작점은 중복 허용 안하므로 전 값에 + 1이다.
// for문 횟수가 전보다 한번 줄어드므로 i <= n 진행
for (let i = start; i <= n; i++) {
// k번째 자리에 i값을 기입
output[k] = i;
// 재귀를 돌며 k + 1 자리에 n번 또 반복 한다.
rec_fuc(k + 1);
// 재귀 끝부터 빠져나오면서 해당 k자리를 초기화 해준다.
output[k] = 0;
}
};
rec_fuc(0);
return result;
};
solution(3,3);
Pay it forward