[STL] 부분조합 구하기 (prev_permutation과 bool 배열을 응용)

• 설명
• 구현

   

   설명

 

STL의 prev_permutation과 bool 배열을 사용합니다. 

우선 prev_permuation은 algorithm 라이브러리에 있는 함수로써 내림차순되어있는 컨테이너, 자료들을

순열로 정렬해줍니다. 이 때의 반환형은 순열로 정렬이 가능하다면 true, 불가능하다면 false를 반합니다.

 

다음과 같은 크기 5정도의 bool배열에서 5C3을 구할 때 일어날 과정에 대하여 나타내겠습니다.

bool b_arr = {1, 1, 1, 0, 0}; 

1, 1, 1, 0, 0
1, 1, 0, 1, 0
1, 1, 0, 0, 1
1, 0, 1, 1, 0
1, 0, 0, 1, 1
0, 1, 1, 1, 0
0, 1, 1, 0, 1
0, 1, 0, 1, 1
0, 0, 1, 1, 1

 

0, 1의 크기와 이 크기를 이용한 prev_permutation의 내림차순을 정렬하는 특성으로 

우리는 원하는 배열에서 가능한 모든 경우의 부분조합을 얻을 수 있습니다.

 

한 마디로  bool 배열의 움직이는 1들이 인덱스가 되어 조합을 찾고자하는 배열의 값들을 선택하는 것 입니다.

구현할 땐  bool 배열을 순회하며 현재 인덱스의 bool 배열의 값이 1일 때 조합을 찾고자하는 배열에도

같은 인덱스를 적용하여 반환합니다.

 

bool b_arr = {1, 1, 1, 0, 0};                   int arr[5] = {1, 2, 3, 4, 5}; 
												
1, 1, 1, 0, 0						1, 2, 3, X, X
1, 1, 0, 1, 0						1, 2, X, 4, X
1, 1, 0, 0, 1						1, 2, X, X, 5
1, 0, 1, 1, 0						1, X, 3, 4, X
1, 0, 1, 0, 1					    	1, X, 3, X, 5
1, 0, 0, 1, 1						1, X, X, 4, 5
0, 1, 1, 1, 0						X, 2, 3, 4, X
0, 1, 1, 0, 1						X, 2, 3, X, 5
0, 1, 0, 1, 1						X, 2, X, 4, 5
0, 0, 1, 1, 1						X, X, 3, 4, 5

 

 

   구현

 

9개의 수 중  7개의 수만을 구해 합이 100이 될 경우 그 7개의 수를 오름차순으로 출력하는 문제입니다.

https://www.acmicpc.net/problem/2309

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

int main() {
    int arr[9];
    bool b_arr[9] = { 1,1,1,1,1,1,1,0,0 }; // 이미 내림차순으로 정렬된 bool 배열
    vector<int> vec;
    // 9개의 숫자 입력
    for (int i = 0; i < 9; i++)
        cin >> arr[i];
	
    // 부분집합 시작
    do
    {
        vector<int> temp_v;
        for (int i = 0; i < 9; i++)
            if (b_arr[i]) // bool이 1일 경우
                temp_v.emplace_back(arr[i]);
        vec = temp_v;
        if (accumulate(vec.begin(), vec.end(), 0) == 100)
        {
            sort(vec.begin(), vec.end());
            for (auto num : vec)
                cout << num << '\n';
            break;
        }
    } while (prev_permutation(b_arr, b_arr + 9));

    return 0;
}

 

 

   느낀 점, 배운 점

 

최근 PS를 하다보면 순열이나, 조합 등을 요구하는 문제가 많아 한 번 공부한 다음 정리해야겠다 생각이 들어

작성하였습니다.

 

 

 

다음 글을 참고하였습니다.

 

https://ansohxxn.github.io/algorithm/combination/#stl-prev_permutation%EC%9C%BC%EB%A1%9C-%EC%A1%B0%ED%95%A9-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0

 

 

 

읽어주셔서 감사합니다. 부족한 부분이나 틀린 부분이 있다면 부디 알려주시면 감사하겠습니다.