순열 - 재귀함수로 만드는 순열

#include <stdio.h>
#include <vector>
#include <algorithm>

int main()
{
    vector<int> v;

    for (int i = 1; i <= 3; i++) 
    	v.push_back(i);
        
    do
    {
        for (int i : v)
            cout << i << " ";
        cout << '\n';
    }while(next_permutation(v.begin(), v.end()));
}

 

원래 순열은 next_permutation을 사용해 첫번째 주소와 마지막주소의 다음주소를 넣어 순열을 만드는 것을 했다.

 

혹시 알고리즘 코딩 테스트를 볼 때 next_permutation이 생각이 안날수도 있다.

그렇기 때문에 재귀함수로 만드는 연습도 해볼 것인데

사실 재귀함수가 그렇게 코스트가 좋지는 않지만

그래도 알아가면 좋은 것이다.

 

아냐 할 수 있음......진짜..

 

 

일단 순열을 쌩으로 만들기 위해서 Swap을 해야한다는것은 당연한 것이다.

[1, 2, 3]에서 [1, 3, 2]의 다음 순열을 만드려면 1번째와 2번째 (처음은 무조건 0번째)를 Swap해야 한다는 것이다.

#include <stdio.h>
#include <algorithm>
#include <vector>

vector<int> v;

void PrintV(vector<int>& vec)
{
    for (int i = 0; i < vec.size(); ++i)
    {
        cout << vec[i] << " ";
    }

    cout << '\n';
}


void MakePermutation(int n, int r, int depth)
{
    cout << n << " : " << r << " : " << depth << '\n';

    // 기저사례
    if (r == depth)
    {
        PrintV(v);
        return;
    }

    // 실제 Swap 및 Recursion
    for (int i = depth; i < n; ++i)
    {
        swap(v[i], v[depth]);
        MakePermutation(n, r, depth + 1);
        swap(v[i], v[depth]);
    }

}

int main()
{
    for (int i = 1; i <= 3; ++i)
        v.push_back(i);

    MakePermutation(3, 3, 0);
}

 

 

내가 도식화해서 이해함

어우 그림봐바 증말..

 

근데 한 번 도식화 해보는 것을 추천

이해 잘됨

 

이거는 외워두자

 

// n개중에서 r개를 뽑아오겠다
// depth를 기반으로
void f(int n, int r, int depth)
{
    // 재귀함수는 기저사례를 무조건
    if (r == depth)
    {
        //logic
        return;
    }

    // 시작지점은 depth부터 n까지
    for (int i = depth; i < n; ++i)
    {
        swap(arr[i], arr[depth]);
        f (n, r, depth + 1);		// 다시 함수
        swap(arr[i], arr[depth]);	// 끝날 때 swap!
    }
}

 

이걸 외워두는게 좋긴 하지만

c++에서는 

do
{
    for (auto i : vector)
    {
        cout << i << " ";
    }
    
    cout << '\n';
}while(next_permutation(vector.begin(), vector.end()));

이게 제일 간단하긴하다 오늘 끝 이제 잘꺼야

 

내일출근이야................................................................................................................................

하지만