[알고리즘] 세트(set)

필요 알고리즘

1. 순열
2. DFS

중복 순열

아래와 같이 각 자리수에 나오는 모든 경우를 만드는 알고리즘은

원하는 형태는 5개의 숫자가 4자리에서 나오므로 5_5_5*5이다.

0 0 0 0
0 0 0 1
0 0 0 2
0 0 0 3
0 0 0 4
0 0 1 0
0 0 1 1
0 0 1 2
0 0 1 3
0 0 1 4
0 0 2 0
0 0 2 1
0 0 2 2
0 0 2 3
0 0 2 4
0 0 3 0
0 0 3 1
...
0 0 4 2
0 0 4 3
0 0 4 4
0 1 0 0
0 1 0 1

....

4 4 3 3
4 4 3 4
4 4 4 0
4 4 4 1
4 4 4 2
4 4 4 3
4 4 4 4

for문으로 구현할 경우

#define MAXN    4
#define MAXI    5

int score[MAXN];

void showDisplay()
{
    for (int i = 0; i < MAXN; i++)
        printf("%d ", score[i]);

    printf("\n");
}

void 중복순열()
{

    for (int a = 0; a < MAXI; a++)
    {
        score[0] = a;

        for (int b = 0; b < MAXI; b++)
        {
            score[1] = b;

            for (int c = 0; c < MAXI; c++)
            {
                score[2] = c;

                for (int d = 0; d < MAXI; d++)
                {
                    score[3] = d;

                    showDisplay();
                }
            }
        }

    }
}

DFS로 변경

#define MAXN    4
#define MAXI    5

int score[MAXN];

void showDisplay()
{
    for (int i = 0; i < MAXN; i++)
        printf("%d ", score[i]);

    printf("\n");
}

void 중복순열_DFS(int idx)
{
    if (idx >= MAXN)
    {
        showDisplay();
        return;
    }

    for (int i = 0; i < MAXI; i++)
    {
        score[idx] = i;

        중복순열_DFS(idx+1);
    }


}

설명 자료

순열

아래와 같이 각 자리수에 나오는 모든 경우를 만드는 알고리즘은

원하는 형태는

1. 5개의 숫자가 4자리에 나와야 한다.
2. 각자리의 숫자들은 중복되지 않는다.

0 1 2 3
0 1 3 2
0 2 1 3
0 2 3 1
0 3 1 2
0 3 2 1
1 0 2 3
1 0 3 2
1 2 0 3
1 2 3 0
1 3 0 2
1 3 2 0
2 0 1 3
2 0 3 1
2 1 0 3
2 1 3 0
2 3 0 1
2 3 1 0
3 0 1 2
3 0 2 1
3 1 0 2
3 1 2 0
3 2 0 1
3 2 1 0

for문

int used[MAXN];

void 순열()
{
    for (int a = 0; a < MAXI; a++)
    {
        if (used[a] == 1) continue;
        used[a] = 1;

        score[0] = a;

        for (int b = 0; b < MAXI; b++)
        {
            if (used[b] == 1) continue;
            used[b] = 1;

            score[1] = b;

            for (int c = 0; c < MAXI; c++)
            {
                if (used[c] == 1) continue;
                used[c] = 1;

                score[2] = c;

                for (int d = 0; d < MAXI; d++)
                {
                    if (used[d] == 1) continue;
                    used[d] = 1;

                    score[3] = d;

                    showDisplay();

                    used[d] = 0;
                }


                used[c] = 0;
            }


            used[b] = 0;
        }

        used[a] = 0;
    }
}

DFS로 변경

int used[MAXN];

void 순열_DFS(int idx)
{
    if (idx >= MAXN)
    {
        showDisplay();
        return;
    }

    for (int i = 0; i < MAXI; i++)
    {
        if (used[i] == 1) continue;

        used[i] = 1;
        score[idx] = i;

        순열_DFS(idx + 1);

        used[i] = 0;
    }
}