기록
순열, 조합 알고리즘 문제 푼 거 기록
als982001
2024. 11. 30. 17:18
1. 개요
오랜만에 알고리즘 문제를 풀려고 했는데 너무 많이 쉰 탓인지 예전에 풀었던 문제들도 너무 어렵게 느껴졌다. 그래서 쉬운 순열, 조합 문제부터 차근차근 문제를 다시 풀어 나가려고 한다. 우선, 순열과 조합을 간단히 말하자면 다음과 같다.
- 순열 (Permutation): 순서를 고려해 n개의 원소 중 r개를 고르는 경우의 수. => 순서 O, 중복 X
- 같은 원소더라도 순서가 다르면 다른 경우로 취급
- 중복 순열 (Repetition Permutation): n개의 원소 중 r개를 중복을 허용하여 순서를 고려해 고르는 경우의 수. => 순서 O, 중복 O
- 같은 원소를 여러 번 선택 가능하며, 순서를 다르게 하면 다른 경우로 취급
- 조합 (Combination): 순서를 고려하지 않고 n개의 원소 중에서 r개를 고르는 경우의 수. => 순서 X, 중복 X
- 중복 조합 (Repetition Combination): n개의 원소 중 r개를 중복을 허용하여 순서를 고려하지 않고 고르는 경우의 수. => 순서 X, 중복 O
2. 순열 예시 문제
https://www.acmicpc.net/problem/15654
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
int n, m;
vector<int> nums;
vector<int> arr;
map<int, bool> check;
void PrintArray()
{
for (int i = 0; i < arr.size(); ++i)
printf("%d ", arr[i]);
printf("\n");
return;
}
void Solve(int idx)
{
if (idx == m)
{
PrintArray();
return;
}
for (int i = 0; i < nums.size(); ++i)
{
int num = nums[i];
if (check[num] == false)
{
check[num] = true;
arr.push_back(num);
Solve(idx + 1);
arr.pop_back();
check[num] = false;
}
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; ++i)
{
int num;
scanf("%d", &num);
check[num] = false;
nums.push_back(num);
}
sort(nums.begin(), nums.end());
Solve(0);
return 0;
}
- 중복을 검사하기 위한 check 배열이 필요
- depth(위 코드에서는 idx)를 늘려가며 배열에 하나씩 채워나감
3. 조합 예시 문제
https://www.acmicpc.net/problem/15655
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, m;
vector<int> arr;
vector<int> nums;
void PrintArray()
{
for (int i = 0; i < arr.size(); ++i)
printf("%d ", arr[i]);
printf("\n");
return;
}
void Solve(int idx, int cnt)
{
if (cnt == m)
{
PrintArray();
return;
}
for (int i = idx; i < nums.size(); ++i)
{
arr.push_back(nums[i]);
Solve(i + 1, cnt + 1);
arr.pop_back();
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; ++i)
{
int num;
scanf("%d", &num);
nums.push_back(num);
}
sort(nums.begin(), nums.end());
Solve(0, 0);
return 0;
}
- 이전에 선택한 index + 1부터 반복문을 시작한다. 이 덕에 중복을 검사하는 배열이 별도로 필요하지는 않다.
4. 중복 순열 예시 문제
https://www.acmicpc.net/problem/15656
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, m;
vector<int> arr;
vector<int> nums;
void PrintArray()
{
for (int i = 0; i < arr.size(); ++i)
printf("%d ", arr[i]);
printf("\n");
return;
}
void Solve(int idx, int cnt)
{
if (cnt == m)
{
PrintArray();
return;
}
for (int i = 0; i < nums.size(); ++i)
{
arr.push_back(nums[i]);
Solve(i + 1, cnt + 1);
arr.pop_back();
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; ++i)
{
int num;
scanf("%d", &num);
nums.push_back(num);
}
sort(nums.begin(), nums.end());
Solve(0, 0);
return 0;
}
- 순열 문제 코드에서 중복 검사를 제외하면 거의 동일하다.
5. 중복 조합 예시 문제
https://www.acmicpc.net/problem/15657
#include <iostream>
#include <vector>
#include <map>
using namespace std;
int n, m;
vector<int> arr;
vector<int> nums;
void PrintArray()
{
for (int i = 0; i < arr.size(); ++i)
printf("%d ", arr[i]);
printf("\n");
return;
}
void Solve(int idx)
{
if (arr.size() == m)
{
PrintArray();
return;
}
for (int i = idx; i < n; ++i)
{
arr.push_back(nums[i]);
Solve(i);
arr.pop_back();
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; ++i)
{
int num;
scanf("%d", &num);
nums.push_back(num);
}
sort(nums.begin(), nums.end());
Solve(0);
return 0;
}
- 조합과 비슷하지만 반복문의 시작값이 이전에 선택한 값(위 코드에서는 idx)이 된다.