1. 개요
순열과 조합은 익히 아는 개념일 것이다.
순열은 N개 중 r개를 뽑아서 줄세우는 경우의 수 = nPr
조합은 N개 중 r개를 뽑는 경우의 수 = nCr
-> 즉 순열과 조합의 차이는 "줄세우기"의 유무이다.
nPr = nCr x r!
그렇다면 프로그래밍을 하다보면 이러한 순열과 조합을 활용해 어떻게 문제를 해결할 수 있을까?
1) 활용 예시
① 문제 개요
orders(손님별 주문한 요리의 종류를 담은 vector)와 course(코스 요리에 포함된 메뉴의 개수)가 주어질 때 최소 2명이상의 손님에게 주문받은 조합을 출력하는 문제이다.
② 풀이
위 예시 중 1번의 경우를 살펴보자.
i) 요리 2개 조합
- A,C : 1,2,4,6 번 손님으로부터 주문
ii) 요리 3개 조합 - C,D,E : 3,4,6번 손님으로부터 주문
iii) 요리 4개 조합 - B,C,F,G : 1,5번 손님으로부터 2번
- A,C,D,E : 4,8번 손님으로부터 2번
문제는 상당히 심플하다. 주의할 점은 요리 하나하나가 2명 이상에게 주문되어야 한다는 것이 아닌 "조합" 이 2명 이상에게 주문되어야 한다는 것이다.
2) Solution
위 문제의 풀이는 다음과 같다.
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <map>
using namespace std;
bool cmp(pair<string, int> a, pair<string, int>b)
{
if (a.second > b.second)
return true;
else
return false;
}
vector<string> solution(vector<string> orders, vector<int> course)
{
vector<string> answer;
// 코스 별 주문 횟수
map<string, int> coursecnt;
// STEP1 : 주문 별 가능한 조합의 수 탐색
for (int i = 0;i < orders.size();i++)
{
string od = orders[i];
// STEP 2: course 개수 별 조합 확인하기
for (int n = 0;n < course.size();n++)
{
if (course[n] > od.length())
break;
vector<bool> tmp(od.length(), true);
for (int k = 0;k < tmp.size() - course[n];k++)
tmp[k] = false;
do
{
string comb = "";
for (int x = 0;x < od.length();x++)
{
if (tmp[x])
comb += od[x];
}
// 알파벳순 정렬 후
sort(comb.begin(), comb.end());
coursecnt[comb]++;
} while (next_permutation(tmp.begin(), tmp.end()));
}
}
// STEP3 : 갯수별 최대 값을 가지는 문자열을 출력해야함
map<int, vector<pair<string, int>>> vp;
for (auto iter = coursecnt.begin();iter != coursecnt.end();iter++)
{
if (iter->second >= 2)
vp[iter->first.length()].push_back({iter->first, iter->second});
}
for (auto iter = vp.begin();iter != vp.end();iter++)
{
vector<pair<string, int>> v=iter->second;
sort(v.begin(), v.end(), cmp);
answer.push_back(v[0].first);
int mx = v[0].second;
for (int i = 1;i < v.size();i++)
{
if (v[i].second == mx)
answer.push_back(v[i].first);
else
break;
}
}
sort(answer.begin(), answer.end());
return answer;
}2. 조합
1) 조합 경우의 수 구하기 (nCr) - 재귀로 구현하기
nCr = n-1Cr-1 + n-1Cr
- n명 중 r명을 선택하는 경우의 수 = (특정 한명을 포함하거나, 안하거나)
= n-1Cr-1 (특정한명을 포함한 후 나머지 중에서 r-1을 고르는 경우) + n-1Cr (특정한명을 제외하고, 나머지 중에서 r명을 고르는 경우)
int comb(int n, int r)
{
if(n==r||r==0)
return 1;
else
return comb(n-1,r-1) + com(n-1,r);
}2) STL 활용하기 (prev_permutation)
stl에서 제공하는 함수(prev_permutation)를 활용해 조합을 구현해볼 수 있다.
- algorithm 헤더에 정의된 함수로, 현재 순열의 이전 순열을 생성
- 즉, 주어진 순열에서 이전에 오는 순열로 변경하는 역할을 수행
prev_permutation 함수의 순열 생성 과정은 다음과 같다.
① 오른쪽에서 왼쪽으로 이동하면서 순열에서 바꿀 수 있는 가장 작은 숫자를 찾는다.
② 해당 숫자를 기준으로 오른쪽부터 가장 큰 숫자를 찾아 교환
③ 교환된 위치 이후의 숫자들을 뒤집어 준다.
#include <iostream>
#include <vector>
#include <algorithm>
int main()
{
// 2개의 조합을 출력
const int r=2;
vector<char> arr{'a','b','c','d'};
vector<bool> tmp(arr.size(),false);
// r개만 true(출력)되도록
for(int i=0;i<r;i++)
tmp[i]=true;
do
{
for(int i=0;i<arr.size();i++)
{
if(tmp[i])
cout<<arr[i]<<' ';
}
}while(prev_permutation(tmp.begin(),tmp.end()));
}2) STL 활용하기 (next_permutation)
stl에서 제공하는 함수(next_permutation)를 활용해 조합을 구현해볼 수 있다.
- prev_permutation과 역순으로 조합을 출력한다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
cont int r=2;
vector<char> arr{'a','b','c','d'};
vector<bool> tmp(arr.size(),true);
// 뒤의 r개부터 true(출력)되도록
for(int i=0;i<arr.size()-r;i++)
tmp[i]=false;
do
{
for(int i=0;i<arr.size();i++)
{
if(tmp[i])
cout<<arr[i]<<' ';
}
}while(next_permutation(tmp.begin(),tmp.end()));
}
