N과 M 시리즈 ( 순열, 조합, 중복순열, 중복조합 )

15649, 15650, ..등등 N과 M을 받았을때 

순열과 조합을 만드는 코딩 문제를 해결하면서, dfs에 대해서 깊게 생각해볼 수 있는 계기가 되었다.

 

1. 정의

2. 코딩

3. 예제

순으로 글을 쓸 것이다.

 

 

나름의 정의를 내린다.

 

순열 : 순서에 따라 결과가 달라지는 수의 모임 {1,2,3} != {2,1,3}

조합 : 순서가 상관없는 수의 모임 {1,2,3} == {2,1,3}

 

순열과 조합의 코딩스타일을 이해하기 위해서 https://yabmoons.tistory.com/99

[ 순열과 조합 구현 ] - 재귀를 통한 구현(1 - 조합) (C++)

이분의 블로그를 참고했다. 도움이 많이 되었다.

 

 

먼저, 조합이다. 조합의 경우, 순서가 상관없기 때문에 요소들의 중복을 허용하지 않는다.

그러므로 코드는 다음과 같다.

#include <iostream>
#define MAX 9
using namespace std;

int n,m;
int arr[MAX] = {0,};
bool visited[MAX] = {0,};

void dfs(int num, int cnt)
{
    if(cnt == m)
    {
        for(int i = 0; i < m; i++)
            cout << arr[i] << ' ';
        cout << '\n';
        return;
    }
    for(int i = num; i <= n; i++)
    {
        if(!visited[i])
        {
            visited[i] = true;
            arr[cnt] = i;
            dfs(i+1,cnt+1);
            visited[i] = false;
        }
    }
}

int main() {
    cin >> n >> m;
    dfs(1,0);
}

 

다음은 순열이다.

조합과 다른점은 dfs의 반복문이 고정적으로 1부터 순회한다는 것

#include <iostream>
#define MAX 9
using namespace std;

int n, m;
int arr[MAX] = { 0, };
bool visited[MAX] = { 0, };

void dfs(int cnt)
{
    if (cnt == m)
    {
        for (int i = 0; i < m; i++)
            cout << arr[i] << ' ';
        cout << '\n';
        return;
    }
    for (int i = 1; i <= n; i++)
    {
        if (visited[i])continue;
        
           visited[i] = true;
           arr[cnt] = i;
           dfs(cnt + 1);
           visited[i] = false;
        }
    }
}

int main() {
    cin >> n >> m;
    dfs(0);
}

 

다음은 중복 순열이다.

#include <iostream>
#define MAX 9
using namespace std;

int n, m;
int arr[MAX] = { 0, };
bool visited[MAX] = { 0, };

void dfs(int cnt)
{
    if (cnt == m)
    {
        for (int i = 0; i < m; i++)
            cout << arr[i] << ' ';
        cout << '\n';
        return;
    }
    for (int i = 1; i <= n; i++)
    {
        //if (visited[i])continue;
        
           visited[i] = true;
           arr[cnt] = i;
           dfs(cnt + 1);
           visited[i] = false;
        
    }
}

int main() {
    cin >> n >> m;
    dfs(0);
}

 

다음은 중복 조합이다.

#include <iostream>
#define MAX 9
using namespace std;

int n,m;
int arr[MAX] = {0,};
bool visited[MAX] = {0,};

void dfs(int num, int cnt)
{
    if(cnt == m)
    {
        for(int i = 0; i < m; i++)
            cout << arr[i] << ' ';
        cout << '\n';
        return;
    }
    for(int i = num; i <= n; i++)
    {
            visited[i] = true;
            arr[cnt] = i;
            dfs(i,cnt+1);
            visited[i] = false;
    }
}

int main() {
    cin >> n >> m;
    dfs(1,0);
}

 

코드를 비교하면서 공부하는게 도움이 된다.

 

코드 출처 : https://cryptosalamander.tistory.com/54

[백준 / BOJ] - 15649번 N과 M(1) C++ 풀이