[공부] 순열과 조합 (C)

백준 문제를 풀다가, 내가 순열과 조합에 대해서 준비가 하나도 되어있지 않다는 것을 알았다.

 

개념은 잡혀있으나, 이를 코드로 구현하는 연습이 미비한 것 같았다.

 

그래서, 일단 기본적인 순열 코드를 긁어서 가져왔다.

https://wonsjung.tistory.com/11

위 블로그에서 몰래 긁어왔다.. ㅎ

순열 (중복 가능)

#include <stdio.h>

int dep[20];
int n;

void rec(int x)
{
    if (x == n)
    {
        for (int i = 0; i < n; i++)
            printf("%d ", dep[i]);
        printf("\n");
        return;
    }

    for (int i = 0; i < n; i++)
    {
        dep[x] = i + 1;
        rec(x + 1);
    }
}

int main()
{
    scanf("%d", &n);
    rec(0);

    return 0;
}

결과

3
1 1 1 
1 1 2
1 1 3
1 2 1
1 2 2
1 2 3
1 3 1
1 3 2
1 3 3
2 1 1
2 1 2
2 1 3
2 2 1
2 2 2
2 2 3
2 3 1
2 3 2
2 3 3
3 1 1
3 1 2
3 1 3
3 2 1
3 2 2
3 2 3
3 3 1
3 3 2
3 3 3

 

순열 (중복 불가)

#include <stdio.h>
#include <stdbool.h>

int dep[20];
bool visited[20];
int n;

void rec(int x)
{
    if (x == n)
    {
        for (int i = 0; i < n; i++)
        {
            printf("%d ", dep[i]);
        }
        printf("\n");
        return;
    }

    for (int i = 0; i < n; i++)
    {
        if (!visited[i + 1])
        {
            dep[x] = i + 1;
            visited[i + 1] = true;
            rec(x + 1);
            visited[i + 1] = false;
        }
    }
}

int main()
{
    scanf("%d", &n);
    rec(0);
    return 0;
}

결과

3
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

조합

#include <stdio.h>

int N, M;
int arr[20];

void depth(int index, int start)
{
    if (index == M)
    {
        for (int i = 0; i < M; i++)
        {
            printf("%d ", arr[i]);
        }
        printf("\n");
        return;
    }

    for (int i = start; i <= N; i++)
    {
        arr[index] = i;
        depth(index + 1, i + 1);
    }
}

int main()
{
    scanf("%d %d", &N, &M);
    depth(0, 1);
    return 0;
}

결과

5 3
1 2 3 
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5

---

이 기본적인 순열 및 조합을 통해, 간단하게 순열과 조합에 대해서 공부하고 이 원리를 이해하면 분명 다른 곳에서도 쉽게 응용할 수 있을 것이다.

이후 백준 1062에서 돌아오겠다!!