N과 M 시리즈 부수기
개요
요즘들어 구현력이 많이 부족하다고 생각했다. 기초부터 다시 해보자는 생각으로 한 N과 M 시리즈.
혼자 힘으로 하기 어려워서 대부분 백준님의 힘을 빌렸다.
next_permutation을 사용하지 않고 재귀적으로 구현했다.
문제들을 해결할 수 있었던 몇가지 방법을 정리하고자 한다.
먼저 재귀적으로 구현하는 방법은 N과 M (1), N과 M (2), N과 M (3)에 자세히 소개했으므로 위 글을 먼저 보고 오자.
N과 M (5)
N개의 자연수 중에서 M개를 고른 수열이며 중복되는 수열을 여러 번 출력하면 안된다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
예제 입력 2
4 2
9 8 7 1
예제 출력 2
1 7
1 8
1 9
7 1
7 8
7 9
8 1
8 7
8 9
9 1
9 7
9 8
여기서 생각해야 하는 아이디어는 세가지다.
- 중복이 없다.
- 처음값을 다시 사용할 수 있다(1 7이 나왔지만 7 1도 가능하다)
- 사전 순으로 증가하는 순서로 출력한다.
사전 순으로 증가하는 순서
- 처음 받은 값을 정렬해준다.
중복이 없다.
- for문 안에서 재귀 전에 이미 사용한 수는 check배열에 넣어주고, 재귀가 끝난 후 check배열에서 제외시킨다.
처음값을 다시 사용할 수 있다.
- 재귀적으로 구현할 때, 각 재귀에서 for문의 시작점을 0으로 초기화해주면 된다.
재귀함수라서 약간 이해하기 어려울 수 있지만 코드를 자세히 들여다 보자.
#include <iostream>
#include <algorithm>
using namespace std;
int a[10];
int num[10];
int c[10];
void go(int index, int n, int m) {
if (index == m) {
for (int i = 0; i < m; i++) {
cout << num[a[i]];
if (i != m - 1) cout << ' ';
}
cout << '\n';
return;
}
for (int i = 0; i < n; i++) { /// 처음값을 다시 사용할 수 있으므로 매 단계에서 0에서 시작한다.
if (c[i]) continue; /// 이 부분은 중복체크1
c[i] = true; /// 이 부분은 중복체크2
/***************************************************************************************/
a[index] = i; /// 몇번째 번호를 사용했는가?
/// a[index] = num[i]를 하고 마지막에 a[i]를 출력해줘도 된다.
/***************************************************************************************/
go(index + 1, n, m);
c[i] = false; /// 이 부분은 중복체크3
}
}
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> num[i];
}
sort(num, num + n); /// 정렬
go(0, n, m);
return 0;
}
N과 M (6)
위 문제에서 수열이 오름차순이여야 한다고 바뀌었다.
예제 입력 2
4 2
9 8 7 1
예제 출력 2
1 7
1 8
1 9
7 8
7 9
8 9
위의 아이디어에서 2번만 다르게 생각하면 해결되는 문제다.
오름차순이어야 한다.
- 시작점을 재귀함수 인자에 추가해주고, 다음 함수를 호출할 때 현재 사용한 위치+1을 주면 값이 오름차순으로 된다. (처음 시작에 정렬했으므로)
위의 코드와 달라진 점만 보자.
void go(int index, int start,int n, int m) { /// 인자가 추가되었다.
if (index == m) {
for (int i = 0; i < m; i++) {
cout << a[i] << ' ';
}
cout << '\n';
return;
}
for (int i = start; i < n; i++) { /// for문의 시작점이 start로 바뀌었다.
if (c[i])
continue;
c[i] = true;
a[index] = num[i];
go(index + 1, i + 1, n, m); /// 함수를 호출할 때 내가 사용한 값의 위치+1번째를 준다.
c[i] = false;
}
}
N과 M (7)
N과 M (5)와 비슷하지만 중복이 가능하다는 점이 다르다.
예제 입력 2
4 2
9 8 7 1
예제 출력 2
1 1
1 7
1 8
1 9
7 1
7 7
7 8
7 9
8 1
8 7
8 8
8 9
9 1
9 7
9 8
9 9
이 또한 간단히 해결 가능하다.
N과 M (5) 코드에서 중복 처리해주었던 곳을 주석처리해주면 된다.
for (int i = 0; i < n; i++) {
//if (c[i])
// continue;
//c[i] = true;
a[index] = num[i];
go(index + 1, n, m);
//c[i] = false;
}
N과 M (8)
N과 M (6)+ N과 M(7) 문제이다.
비내림차순은 내림차순이 아닌(?) 차순이다. 즉, 1 1이 내림차순이 아니므로 가능하다.
중복이 가능하다.
예제 입력 2
4 2
9 8 7 1
예제 출력2
1 1
1 7
1 8
1 9
7 7
7 8
7 9
8 8
8 9
9 9
이 문제 또한 간단한 코드 변경으로 해결 가능하다.
N과 M (6)에서 바뀐 부분만 살펴보자.
for (int i = start; i < n; i++) {
//if (c[i])
// continue; 중복 가능
//c[i] = true;
a[index] = num[i];
go(index + 1, i, n, m); ///i+1 -> i
//c[i] = false; 중복 가능
}
N과 M (9) ~ (12)
위의 5~8 문제와 거의 동일하지만 중복 값이 존재한다는 것이 다르다.
위의 코드들을 그대로 이용하고, 마지막에 답을 답 vector에 추가한 뒤에, 정답이 중복되는 것들을 지워주는 방식을 이용했다.
N과 M (9)번 코드이며, 이후의 값들은 직접 해보면 된다.
다만 unique가 생소하실 분들을 위해 간단히 설명하면,
주어진 반복자 구간에서 연속되면서 중복되는 값들을 한 값만 제외하고 뒤로 밀어버리는 함수이다.
예를들어 [1 3 3 4 4 4 3]이면, [1 3 4 3 * 3 4 4 ], 그리고 * 3 위치를 반환한다.
그러므로 *3부터 벡터의 마지막까지 지워버리는 원리이다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int a[10];
int num[10];
int c[10];
vector< vector<int> > d;
void go(int index,int n, int m) {
if (index == m) {
vector<int> tmp;
for (int i = 0; i < m; i++) {
tmp.push_back(a[i]);
}
d.push_back(tmp);
return;
}
for (int i = 0; i < n; i++) {
if (c[i])
continue;
c[i] = true;
a[index] = num[i];
go(index + 1,n, m);
c[i] = false;
}
}
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> num[i];
}
sort(num, num + n);
go(0,n, m);
sort(d.begin(), d.end());
d.erase(unique(d.begin(), d.end()), d.end());
for (auto dd : d) {
for (auto ddd : dd) {
cout << ddd << ' ';
}
cout << '\n';
}
return 0;
}
마무리
알고리즘 공부하는 사람들 화이팅이다.. 너무 어렵다 으악
댓글남기기