순열, 조합 알고리즘 문제 푼 거 기록

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)이 된다.

---

참고한 글: https://hongchan.tistory.com/5