15649번
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
사실 DFS랑 푸는 방법이 무슨 차이가 있는지 잘 모르겠었다.
챗지피티에게 문의한 결과는 이렇다.
DFS는 그래프, 트리 자료구조에서 모든 노드를 탐색하거나 특정 노드를 찾는 데 사용되는 탐색 알고리즘이고,
백트래킹은 주어진 문제에서 가능한 모든 해를 찾거나 최적해를 찾는 데 사용되는 기술로 주로 제약 조건을 충족하는 모든 가능해를 찾는 데 사용된다. 순열, 조합, 집합 분할 등의 문제 해결에 적합하다.
백트래킹은 일반적인 패턴은 이렇다.
- 시작 지점에서 출발하여 가능한 다음 단계로 이동
- 가능한 모든 다음 단계로 진행하며, 현재 상태에서 조건을 충족하지 못하면 이전 단계로 되돌아감 (백트래킹)
- 조건을 충족하거나 해를 찾을 때까지 1과 2를 반복
백트래킹은 대표적으로 조합, 순열, 집합 분할, 스도쿠, N-퀸 문제와 같은 다양한 조합 최적화 문제를 해결하는 데 사용된다. 이러한 문제는 일반적으로 DFS와 백트래킹을 결합하여 해결된다. 따라서 백트래킹은 DFS와 밀접하게 관련되어 있으며, 특히 DFS의 재귀적 특성을 이용하여 문제의 가능한 모든 해를 찾는 과정에 적용된다.
정리하자면, 백트래킹은 꼭 DFS만을 뜻하거나 같은 의미는 아니지만 밀접한 관련을 갖는다.
DFS는 모든 노드의 탐색을 목표로 하지만, 백트래킹은 모든 가능해를 찾는 것을 목표로 한다.
풀이는 이렇다.
#include <iostream>
#include <vector>
using namespace std;
int n, m;
vector<int> nums(10);
vector<int> ch(10);
vector<int> res(10);
void BT(int L)
{
if (L == m)
{
for (int i = 0; i< m; i++)
{
cout << res[i] << " ";
}
cout << "\n";
return;
}
else
{
for (int i = 1; i <= n; i++)
{
if (ch[i] == 0)
{
ch[i] = 1;
res[L] = i;
BT(L + 1);
ch[i] = 0;
}
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
nums[i] = i;
}
BT(0);
return 0;
}15650번
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
고른 수열은 오름차순이어야 한다.
이제는 중복된 수열은 출력하면 안되고 오름차순으로 선택해야한다.
-> 선택된 숫자가 있으면 이후로는 그 값보다 큰 값에만 접근하도록 제한하자
-> 매개변수로 자기 자신의 값을 전달해 어디서부터 탐색해야하는지 알려주는 방식으로 해결
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, m;
vector<int> nums(10);
vector<int> ch(10);
vector<int> res(10);
void BT(int L, int num)
{
if (L == m)
{
for (int i = 0; i< m; i++)
{
cout << res[i] << " ";
}
cout << "\n";
return;
}
else
{
for (int i = num + 1; i <= n; i++)
{
if (ch[i] == 0)
{
ch[i] = 1;
res[L] = i;
BT(L + 1, i);
ch[i] = 0;
}
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
nums[i] = i;
}
BT(0, nums[1]);
return 0;
}15651번
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
1부터 N까지 자연수 중에서 M개를 고른 수열
같은 수를 여러 번 골라도 된다.
중복 선택이 가능하니 체크 벡터를 사용하지 않고 작업해준다.
#include <iostream>
#include <vector>
using namespace std;
int n, m;
vector<int> nums(10);
vector<int> res(10);
void BT(int L)
{
if (L == m)
{
for (int i = 0; i< m; i++)
{
cout << res[i] << " ";
}
cout << "\n";
return;
}
else
{
for (int i = 1; i <= n; i++)
{
res[L] = i;
BT(L + 1);
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
nums[i] = i;
}
BT(0);
return 0;
}15652번
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
1부터 N까지 자연수 중에서 M개를 고른 수열
같은 수를 여러 번 골라도 된다.
고른 수열은 비내림차순이어야 한다.
길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.
위의 내용들을 조합해서 푼다.
#include <iostream>
#include <vector>
using namespace std;
int n, m;
vector<int> nums(10);
vector<int> res(10);
void BT(int L, int num)
{
if (L == m)
{
for (int i = 0; i< m; i++)
{
cout << res[i] << " ";
}
cout << "\n";
return;
}
else
{
for (int i = num; i <= n; i++)
{
res[L] = i;
BT(L + 1, i);
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
nums[i] = i;
}
BT(0, 1);
return 0;
}15654번
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, M;
vector<int> vInput;
vector<int> res(10);
vector<int> ch(10);
void DFS(int L)
{
if (L == M)
{
for (int i=0; i<M; i++)
{
cout << res[i] << " ";
}
cout << "\n";
return;
}
else
{
for (int i = 0; i < N; i++)
{
if (ch[i] == 0)
{
ch[i] = 1;
res[L] = vInput[i];
DFS(L + 1);
ch[i] = 0;
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> M;
for (int i = 1; i <= N; i++)
{
int a;
cin >> a;
vInput.push_back(a);
}
sort(vInput.begin(), vInput.end());
DFS(0);
return 0;
}15663번
문제
N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
N개의 자연수 중에서 M개를 고른 수열
입력
첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
.
.
풀이
이 경우에는 중복 수열을 제거해야해서, 정렬해서 작업한 뒤에 바로 출력하는 것이 아니라
set에 넣어서 중복 수열을 제거하고 출력해주는 방식을 택했다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
vector<int> v;
vector<int> ch(10);
int N, M;
vector<int> res(10);
set<vector<int>> ans;
void BT(int L)
{
if (L == M)
{
vector<int> tmpV;
for (int i = 0; i < M; i++)
{
tmpV.push_back(res[i]);
}
ans.insert(tmpV);
return;
}
else
{
for (int i = 0; i < N; i++)
{
if (ch[i] == 0)
{
ch[i] = 1;
res[L] = v[i];
BT(L + 1);
ch[i] = 0;
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> M;
for (int i = 0; i < N; i++)
{
int tmp;
cin >> tmp;
v.push_back(tmp);
}
sort(v.begin(), v.end());
BT(0);
for (const vector<int>& vec : ans)
{
for (const int& a : vec)
{
cout << a << " ";
}
cout << "\n";
}
return 0;
}