알고리듬#3 경우의 수 : 순열과 조합

경우의 수란?

모든 가능한 방법의 수

문제 해결에서 모든 조합이나 배치를 탐색해야 하는 상황에서 경우의 수를 계산하는 것이 중요하다.

✅ 1. 경우의 수 – 동전 앞뒤 모든 경우 출력 (2^n)

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int n = 3; // 동전 3개
    int total = pow(2, n);

    for (int i = 0; i < total; ++i) {
        for (int j = n - 1; j >= 0; --j) {
            cout << (((i >> j) & 1) ? "뒤 " : "앞 ");
        }
        cout << '\n';
    }
    return 0;
}

순열(Permutation)이란?

n개의 대상 중에서 r개의 대상을 선택하여 나열할 때, 그 순서가 있는 경우로, 기호로는 nPr이라고 사용하고, 팩토리얼 연산을 이용해 다음과 같이 표현한다.

✅ 2. 순열 – nPr 구현 (백트래킹) 

보통 트리 탐색으로 구현되며, DFS와 BFS와 같은 것이 있다. 

#include <iostream>
using namespace std;

int n = 3, r = 2;
int arr[3] = {1, 2, 3};
bool visited[3];

void Permutation(int depth) {
    static int result[3];

    if (depth == r) {
        for (int i = 0; i < r; ++i)
            cout << result[i] << ' ';
        cout << '\n';
        return;
    }

    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            visited[i] = true;
            result[depth] = arr[i];
            Permutation(depth + 1);
            visited[i] = false;
        }
    }
}

int main() {
    Permutation(0);
    return 0;
}​

조합(Combination)이란?

n개의 대상 중에서 r개의 대상을 선택할 때, 그 순서가 없는 경우로, 기호로는 nCr이라고 사용하고, 팩토리얼 연산을 이용해 다음과 같이 표현한다.

✅ 3. 조합 – nCr 구현 (백트래킹)

조합은 순서를 고려하지 않기 때문에, 같은 숫자의 다른 순열은 모두 하나의 조합으로 취급된다.

#include <iostream>
using namespace std;

int n = 4, r = 2;
int arr[4] = {1, 2, 3, 4};
int result[4];

void Combination(int depth, int start) {
    if (depth == r) {
        for (int i = 0; i < r; ++i)
            cout << result[i] << ' ';
        cout << '\n';
        return;
    }

    for (int i = start; i < n; ++i) {
        result[depth] = arr[i];
        Combination(depth + 1, i + 1);
    }
}

int main() {
    Combination(0, 0);
    return 0;
}​

 

이번 글은 GPT가 많이 도와줬어요