링크
https://www.youtube.com/watch?v=Enz2csssTCs&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=13
문제
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
순열
자바 코드
import java.io.*;
import java.util.StringTokenizer;
public class Main_15649 {
private static int N;
private static int M;
private static boolean[] vis;
private static int[] arr;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M=Integer.parseInt(st.nextToken());
vis = new boolean[N+1];
arr = new int[M];
perm(0);
}
private static void perm(int cnt) {
if(cnt == M) {
for(int i = 0; i < M; i++) {
System.out.print(arr[i]+ " ");
}
System.out.println();
}
else {
for(int i = 1; i <= N; i++) {
if(!vis[i]) {
vis[i]=true;
arr[cnt] = i;
perm(cnt+1);
vis[i]= false;
}
}
}
}
}C++ 코드
👨🏻💻 백트래킹
#include <iostream>
using namespace std;
int n, m;
int arr[10];
bool isused[10];
void func(int k) { //현재 k개까지 수를 택했음.
if (k == m) { // m개를 모두 택했으면
for (int i = 0; i < m; i++)
cout << arr[i] << ' '; // arr에 기록해둔 수를 출력
cout << '\n';
return;
}
for (int i = 1; i <= n; i++) { //1부터 n까지의 수에 대해
if (!isused[i]) { // 아직 i가 사용되지 않았으면
arr[k] = i; //k번째 수를 i로 정함
isused[i] = 1; // i를 사용되었다고 표시
func(k + 1); //다음 수를 정하러 한 단계 더 들어감
isused[i] = 0; //k번째 수를 i로 정한 모든 경우에 대해 다 확인했으니 i를 이제 사용되지않았다고 명시함.
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
func(0);
}👨🏻💻 next_permutation STL함수를 사용한 풀이
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<int> v(n), w(n);
//iota(v.begin(), v.end(), 1); //1 2 3... 차례로 벡터를 채운다.
for (int i = 0; i < n; i++) {
v[i] = i + 1;
}
fill(w.end() - m, w.end(), 1);// nCr을 위해 0과 1을 채울때 next_per을 쓸려면
// 가장 작은 값으로 만들어놔야한다. -> 1의 갯수는 m(=r)과 같아야하고 가장 작은 값
//-> 뒷부분을 1로 채운다.
vector<vector<int>> res;
//1. n개의 수에서 "중복 없이" m개의 수를 선택하는 과정
//2. m개의 수로 만들 수 있는 모든 순열을 나열하는 과정으로 쪼갠다. (nPr = nCr * r!)
//수열에 대해 next_permutation == nPn = n!
// nPr == n * (n-1) *(n-1)* ... *(n-r+1)
do {
vector<int> t;
for (int i = 0; i < n; i++) if(w[i]) t.push_back(v[i]);
do {
res.push_back(t);
} while (next_permutation(t.begin(), t.end()));
} while (next_permutation(w.begin(), w.end()));
sort(res.begin(), res.end());
for (auto i : res) {
for (auto j : i) {
cout << j << ' ';
}
cout << '\n';
}
}설명
백트래킹
🧷 수열의 한 경우를 넣는 int arr[10]배열과 해당 수가 이미 쓰였는지 확인할 수 있는 bool타입의 bool isused[10]배열이 필요하다.
📌 k개 수를 선택한 상태에서 func(k)를 호출한다.
맨 처음에는 func(0)을 호출하고 arr[0]을 정한 후에 func(1)을 호출한다. arr배열이 0-indexed인걸 잘 기억해두자.
📌 base condition : k==m일때 m개를 모두 택했으니 수열을 출력한 후 함수를 종료한다.
📌 재귀 : 1부터 n까지 수를 차례로 확인하며 아직 쓰이지 않은 수를 찾아낸다. 쓰이지 않은 수를 arr[k]=i에 넣고 isused[i] = 1을 통해 해당 값은 쓰여졌다고 표시한다.
그리고 func(k+1)을 호출한다.
📌 그 다음 줄로 왔다는 것은 arr[k]=i를 둔 상태에서 func(k+1)에 들어갔다가 모든 과정을 끝냈다는 얘기니 isused[i] = false로 되돌려 i가 사용되지 않고 있음을 명시해야한다. 그리고 반복문을 따라 다음 i+1값으로 넘어간다. 단, 현재 값이 i인 arr[k]는 어차피 다른 값으로 덮힐 예정이라 굳이 0과 같은 값으로 변경할 필요가 없다.
⭐ i는 각 상태들이 각자 가지고 있고 arr와 isused는 공통으로 쓰는 조금 헷갈릴 수 있지만 해당 문제가 백트래킹의 전형적인 구조이니 잘 알아두자
next_permutation 함수를 사용한 풀이
n개의 수에서 중복 없이 m개의 수를 뽑아서 만들 수 있는 순열(=nPm)을 사전순으로 출력하는 문제입니다.
이는 1)n개의 수에서 중복 없이 m개의 수를 선택하는 과정과 2)m개의 수로 만들 수 있는 모든 순열을 나열하는 과정으로 쪼갤 수 있습니다. (nPr = nCr * r!) -> r!는 next_permutation를 do while했을때다. (nPn == r!)
1번 과정은 위의 "iterating combination"에서 살펴본 대로 0과 1로 이루어진 vector에서 next_permutation을 돌려주면 처리할 수 있습니다. 2번 과정은 1번 과정에서 구한 m개의 수로 단순히 next_permutation을 돌려주면 됩니다.
주의할 점은 1, 2번 과정으로는 순열을 사전순으로 구할 수 없기 때문에 구한 순열들을 한 번 정렬해주고 출력해야 합니다.
+)
사실 N과 M 시리즈는 next_permutation을 이용하거나, 재귀함수를 이용해 백트래킹으로 구현하는 두 가지 풀이가 존재합니다. next_permutation은 재귀함수를 이용하지 않아서 구현이 편리하고, 백트래킹은 직접 다음 순열을 생성하지 않아서 더 빠르다는 장점이 있습니다.
앞으로 가능한 모든 순열, 조합을 탐색하는 문제가 자주 등장할 텐데, 상황에 맞게 두 방법 중 하나를 사용할 수 있도록 숙지해두시면 좋을 거 같습니다. 저는 보통 단순 순열, 조합을 필요로 하면서 효율성을 고려하지 않아도 되는 문제라면 next_permutation을 사용하고, 중복 순열, 중복 조합 등을 필요로 하거나 시간 최적화가 필요한 문제는 백트래킹으로 처리합니다.
