[ 완전탐색 알고리즘 ] BAEKJOON(백준) 10974번 모든순열 (C/C++)

JIYUL LEE (jiyul)·2022년 12월 23일
0

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

int main()
{
    int n;  //입력받을 숫자
    std::cin >> n;
    std::vector<int> vnNum;
    for (int i = 1; i <= n; i++)
        vnNum.push_back(i);
 
    do {
        for (int i : vnNum)
        {
            std::cout << i ;
        }
        std::cout<<std::endl;		//시간초과 시 puts("");로 대체
    } while (next_permutation(vnNum.begin(), vnNum.end()));
    //현재 수열에서  넘어간 범위 해당하는 다음 순열 ->true, 없다면 -> false
}

완전탐색의 가장 기본 문제인 순열 문제였어요!
nPn = n! 의 경우의 수를 찾는 문제네요. 알고리즘을 짜서 풀었다기보다는 기존의 함수를 써서 풀었다는 함정이 있지만..ㅎㅎ 위의 함수 앞으로 코테 (특히 카카오)문제 풀때 굉장히 유용할거예요!
기억해둬서 나쁠것 없는 함수!

여담으로 위에서 언급한 n! 팩토리얼도 구현해볼까해요:)

int factorial(int num)
{
    return factorial_tail(num);
}

int factorial_tail(int num)
{
    if (num == 1)
        return num;
    else
        return num* factorial(--num);
}

위와 같이 factorial은 재귀 함수로 구현가능하답니다!
next_permutation(vector.begin(), vector.end()) 함수는 반드시 vector값이 정렬되어있어야 모든 경우의 수를 구할 수 있답니다!
그러기에 만약 위에처럼 직접 vector에 넣는 경우가 아닌 중복되지않는 랜덤한 배열값이라면 반드시 정렬을 해주어야해요!
정렬하는 함수는 sort(vector.begin(), vector.end()) 랍니다!

이번 백준 문제에서는 사전표기대로 정렬(즉, 오름차순 정렬)을 하도록하였지만, 간혹 내림차순 정렬혹은 순열이 필요할때가 있어요 그럴때는 역정렬 후 뒤에 greater()를 붙여줘야 합니다!
예제 볼게요!

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

int main()
{
    int n;
    std::cin >> n;
    std::vector<int> v;
    for (int i = 1; i <= n; i++)
        v.push_back(i);
    std::reverse(v.begin(), v.end());	//반드시 역정렬해줘야합니다.                      
    do
    {
        for(int num :v)
            std::cout<<num;
        std::cout<<std::endl;
    }while(next_permutation(v.begin(),v.end(),std::greater<int>()));
}

다음에는 다른 조금 더 복잡한 유형의 완전탐색 문제를 가져와볼게요ㅎㅎ

profile
의료(헬스케어/(외/내)과/치과/수술 등) 프로그램 개발자

0개의 댓글