n & m series
각 문제의 핵심 차이점은 중복 허용 여부와 오름차순 또는 비내림차순 요구에 있음
| 문제 번호 | 풀이 방식 | 설명 |
|---|---|---|
| N과 M (1) | 순서 | 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 모두 구하는 문제. 순서가 중요함. |
| N과 M (2) | 선택 | 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 모두 구하는 문제(오름차순). 순서는 고려되지만, 조합적 접근. |
| N과 M (3) | 순서 | 1부터 N까지 자연수 중에서 M개를 고른 수열을 모두 구하는 문제(중복 선택 가능). 순열의 변형. |
| N과 M (4) | 선택 | 1부터 N까지 자연수 중에서 M개를 고른 수열을 모두 구하는 문제(중복 선택 가능, 비내림차순). 조합적 접근. |
| N과 M (5) | 순서 | N개의 서로 다른 자연수 중에서 M개를 고른 수열을 모두 구하는 문제. 순서가 중요함. |
| N과 M (6) | 선택 | N개의 서로 다른 자연수 중에서 M개를 고른 수열을 모두 구하는 문제(오름차순). 조합적 접근. |
| N과 M (7) | 순서 | N개의 서로 다른 자연수 중에서 M개를 고른 수열을 모두 구하는 문제(중복 가능). 순열의 변형. |
| N과 M (8) | 선택 | N개의 서로 다른 자연수 중에서 M개를 고른 수열을 모두 구하는 문제(중복 가능, 비내림차순). 조합적 접근. |
| N과 M (9) | 순서 | N개의 자연수 중에서 M개를 고른 수열을 모두 구하는 문제. 순서가 중요함. |
| N과 M (10) | 선택 | N개의 자연수 중에서 M개를 고른 수열을 모두 구하는 문제(비내림차순). 조합적 접근. |
| N과 M (11) | 순서 | N개의 자연수 중에서 M개를 고른 수열을 모두 구하는 문제(중복 선택 가능). 순열의 변형. |
| N과 M (12) | 선택 | N개의 자연수 중에서 M개를 고른 수열을 모두 구하는 문제(중복 선택 가능, 비내림차순). 조합적 접근. |
순서를 고려한 풀이 vs 선택을 고려한 풀이
[#순서] 풀이1.
숫자의 위치, 어떤 숫자 -> 순열적
bool c[10] : 중복이 없어야 하므로 숫자의 사용여부를 표현하는 배열
int a[10] : 구한 수열을 저장할 배열
go함수의 동작 원리
- Base Case
- index가 m에 도달했는지를 확인 ⟺ 재귀 호출이 M개의 수를 모두 선택했는지 확인
- 도달시, 수열 출력
- Recursive
index= 현재 수열에서 선택된 숫자의 위치
start= 수열에서 다음에 선택할 수 있는 숫자의 시작점(숫자 후보군)
- start부터 시작한 순회 : 숫자 사용여부(
c)에 따라 수열에 포함시킬지를 결정 - (true; 이미 선택된 숫자라면) : 다음 순회로 넘어감
- (false; 선택된적 없다면) : 수열에 포함시킴
2-1) Recursive 호출 : go(index+1, i+1, n, m)
- index를 1증가 <=> 다음 순서의 숫자 선택
- i+1 <=> 오름차순의 유지
2-2) 역추적 : 재귀 호출이 반환되면(수열이 모두 결정되어 출력이 되면), 다시 c를 false로 설정하여(현재 숫자를 다시 사용할 수 있게하여) 모든 가능한 수열을 탐색 가능
#include <iostream>
using namespace std;
bool c[10];
int a[10];
void go(int index, int start, int n, int m) {
if (index == m) {
for (int i=0; i<m; i++) {
cout << a[i];
if (i != m-1) cout << ' ';
}
cout << '\n';
return;
}
for (int i=start; i<=n; i++) {
if (c[i]) continue;
c[i] = true;
a[index] = i;
go(index+1, i+1, n, m);
c[i] = false;
}
}
int main() {
int n, m;
cin >> n >> m;
go(0,1,n,m);
return 0;
}[#선택] 풀이2. (중요!!)
go함수의 동작원리 : index를 넣을 것인가 말 것인가.
어떤 숫자, 사용된 숫자의 개수로 -> 조합
index: 현재 고려하고 있는 숫자
selected: 현재까지 선택된 숫자의 개수
-
Base Case
1-1) 선택된 숫자의 개수가 M에 도달하면 현재까지 선택된 수열을 출력하고 재귀 호출을 종료
1-2) 현재 고려하고 있는 숫자 index가 N을 초과하면 더 이상 선택할 수 있는 숫자가 없으므로 함수를 종료 -
Recursive
i) 숫자를 선택하여 수열에 추가
go(index+1, selected+1, n, m);
ii) 숫자를 선택하지 않고 넘어가기
go(index+1, selected, n, m);
#include <iostream>
using namespace std;
int a[10];
void go(int index, int selected, int n, int m) {
if (selected == m) {
for (int i=0; i<m; i++) {
cout << a[i] << ' ';
}
cout << '\n';
return;
}
if (index > n) return;
a[selected] = index;
go(index+1, selected+1, n, m);
a[selected] = 0;
go(index+1, selected, n, m);
}
int main() {
int n, m;
cin >> n >> m;
go(1, 0, n, m);
return 0;
}1번
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 모두 구하는 문제. 순서가 중요함.
bool c[10]; int a[10];
void go(int index, int n, int m) {
if (index == m) { // 수열을 출력
return; }
for (int i=1; i<=n; i++) {
if (c[i]) continue;
c[i] = true; a[index] = i;
go(index+1, n, m);
c[i] = false;
}
}
// go(0, n, m);2번
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 모두 구하는 문제(오름차순). 순서는 고려되지만, 조합적 접근.
int a[10];
void go(int index, int selected, int n, int m) {
if (selected == m) { // 수열 출력
return; }
if (index > n) return;
a[selected] = index;
go(index+1, selected+1, n, m);
a[selected] = 0;
go(index+1, selected, n, m);
}
// go(1, 0, n, m);3번
1부터 N까지 자연수 중에서 M개를 고른 수열을 모두 구하는 문제(중복 선택 가능). 순열의 변형.
bool c[10]; int a[10];
void go(int index, int n, int m) {
if (index == m) { // 수열을 출력
return; }
for (int i=1; i<=n; i++) {
//if (c[i]) continue;
c[i] = true; a[index] = i;
go(index+1, n, m);
c[i] = false;
}
}
// go(0, n, m);4번
1부터 N까지 자연수 중에서 M개를 고른 수열을 모두 구하는 문제(중복 선택 가능, 비내림차순). 조합적 접근.
bool c[10]; int a[10];
void go(int index, int start, int n, int m) {
if (index == m) { // 수열을 출력
return; }
for (int i=start; i<=n; i++) {
//if (c[i]) continue;
c[i] = true; a[index] = i;
go(index+1, i, n, m);
c[i] = false;
}
}
// go(0, 1, n, m);5번
N개의 서로 다른 자연수 중에서 M개를 고른 수열을 모두 구하는 문제. 순서가 중요함
int a[10]; int num[10]; int c[10];
void go(int index, int n, int m) {
if (index == m) { // 수열을 출력
return; }
for (int i=0; i<n; i++) {
if (c[i]) continue;
c[i] = true; a[index] = i;
go(index+1, n, m);
c[i] = false;
} }
// sort(num, num+n); go(0, n, m);6번
N개의 서로 다른 자연수 중에서 M개를 고른 수열을 모두 구하는 문제(오름차순). 조합적 접근.
int a[10]; int num[10]; int c[10];
void go(int index, int start, int n, int m) {
if (index == m) { // 수열 출력
return; }
for (int i=start; i<n; i++) {
a[index] = i;
go(index+1, i + 1, n, m);
}
}
// sort(num, num+n); go(0, 0, n, m);int a[10];
int num[10];
void go(int index, int selected, int n, int m) {
if (selected == m) { // 수열 출력
return; }
if (index >= n) return;
a[selected] = index;
go(index+1, selected+1, n, m);
a[selected] = 0;
go(index+1, selected, n, m);
}
// sort(num, num+n); go(0, 0, n, m);7번
N개의 서로 다른 자연수 중에서 M개를 고른 수열을 모두 구하는 문제(중복 가능, 비내림차순). 조합적 접근.
int a[10]; int num[10]; int c[10];
void go(int index, int n, int m) {
if (index == m) { // 수열 출력
return; }
for (int i=0; i<n; i++) {
a[index] = i;
go(index+1, n, m);
}
}
// sort(num, num+n); go(0, n, m);
8번
N개의 서로 다른 자연수 중에서 M개를 고른 수열을 모두 구하는 문제(중복 가능, 비내림차순). 조합적 접근
int a[10]; int num[10]; int c[10];
void go(int index, int start, int n, int m) {
if (index == m) { // 수열 출력
return; }
for (int i=start; i<n; i++) {
a[index] = i;
go(index+1, i, n, m);
}
}
// sort(num, num+n); go(0, 0, n, m);(순서) 중복 허용
for (int i=0; i<n; i++) {
a[index] = i;
go(index+1, n, m);
}(순서) 중복 허용 + 오름차순
for (int i=start; i<n; i++) {
a[index] = i;
go(index+1, i + 1, n, m);
}(순서) 중복 허용 + 비내림차순
for (int i=start; i<n; i++) {
a[index] = i;
go(index+1, i, n, m);
}참고 : 재귀함수의 구조
재귀 함수는 다음과 같은 기본 구조를 가진다.
Base Case: 재귀 호출을 종료하는 조건.
Recursive Case: 문제를 더 작은 문제로 분할하여 재귀적으로 해결하는 과정.
@Hanyang univ(seoul). CSE