조합과 순열//combination vs permutation

 

1️⃣ 조합(Combination)의 재귀 동작

💡 조합이란?

조합은 순서에 상관없이 n개의 원소 중 r개를 선택하는 경우의 수를 찾는 것

📌 핵심 로직

1. 현재 위치 start에서 원소를 선택하고(selected[i] = true), 남은 r-1개를 찾음
2. r == 0이 되면 출력
3. 원소를 선택하지 않는 경우도 고려하면서 진행

---

📌 예제 코드 (n=4, r=2)

void Combination_recur(vector<int>& vec, vector<int>& selected, int start, int r)
{
    if (r == 0) // 조합이 완성되었을 때 출력
    {
        PrintCombi(vec, selected);
        return;
    }
    for (size_t i = start; i < vec.size(); i++)
    {
        selected[i] = 1;
        Combination_recur(vec, selected, i + 1, r - 1); // ✅ r을 감소시킴
        selected[i] = 0; // 백트래킹 (원상 복구)
    }
}

---

📌 재귀 호출 트리 (n = {1, 2, 3, 4}, r = 2)

Combination_recur(0, 2)   // 시작점 0, r=2
 ├── 선택: {1}  → Combination_recur(1, 1)
 │   ├── 선택: {1, 2}  → Combination_recur(2, 0)  ✅ 출력: (1,2)
 │   ├── 선택: {1, 3}  → Combination_recur(3, 0)  ✅ 출력: (1,3)
 │   ├── 선택: {1, 4}  → Combination_recur(4, 0)  ✅ 출력: (1,4)
 │
 ├── 선택: {2}  → Combination_recur(2, 1)
 │   ├── 선택: {2, 3}  → Combination_recur(3, 0)  ✅ 출력: (2,3)
 │   ├── 선택: {2, 4}  → Combination_recur(4, 0)  ✅ 출력: (2,4)
 │
 ├── 선택: {3}  → Combination_recur(3, 1)
 │   ├── 선택: {3, 4}  → Combination_recur(4, 0)  ✅ 출력: (3,4)

📌 조합의 특징:

• i + 1을 넘기면서, 이전에 선택한 값보다 뒤에 있는 원소만 선택
• 중복이 없고, 선택한 원소들의 순서가 바뀌지 않음
• r == 0이 되면 조합이 완성됨

---

2️⃣ 순열(Permutation)의 재귀 동작

💡 순열이란?

순열은 순서를 고려하여 n개의 원소 중 r개를 선택하는 경우의 수를 찾는 것

📌 핵심 로직

1. 각 위치에서 모든 원소를 스왑하며 순서를 바꿈
2. depth == r이 되면 출력
3. 백트래킹(swap을 되돌림)하여 원래 상태로 복원

---

📌 예제 코드 (n=3, r=3)

void Permutation_recur(vector<int>& vec, int depth, int n)
{
    if (depth == n)
    {
        PrintVector(vec);
        return;
    }
    for (int i = depth; i < n; i++)
    {
        swap(vec[depth], vec[i]);  // ✅ 순서를 변경
        Permutation_recur(vec, depth + 1, n);
        swap(vec[depth], vec[i]);  // ✅ 백트래킹 (원래대로 복구)
    }
}

---

📌 재귀 호출 트리 (n = {1, 2, 3})

---

🚀 순열 재귀가 실행되는 순서

💡 핵심 개념:

1. depth는 현재까지 결정된 숫자의 개수.
2. depth == n이면 완성된 순열이므로 출력.
3. swap을 통해 현재 자리(depth)에 가능한 모든 숫자를 배치.
4. 백트래킹을 사용해 원래 상태로 복구.

---

🔍 예제 코드 (순열 재귀)

#include <iostream>
#include <vector>

using namespace std;

void PrintVector(const vector<int>& vec)
{
    for (int num : vec)
    {
        cout << num << " ";
    }
    cout << endl;
}

void Permutation_recur(vector<int>& vec, int depth, int n)
{
    if (depth == n) // ✅ depth가 n이 되면 출력
    {
        PrintVector(vec);
        return;
    }

    for (int i = depth; i < n; i++)
    {
        swap(vec[depth], vec[i]);  // ✅ 현재 위치(depth)와 i를 교환
        Permutation_recur(vec, depth + 1, n); // ✅ 다음 단계 진행
        swap(vec[depth], vec[i]);  // ✅ 백트래킹 (원상 복구)
    }
}

int main()
{
    vector<int> arr = {1, 2, 3};

    Permutation_recur(arr, 0, arr.size());

    return 0;
}

---

📌 실행 순서 (depth=0에서 시작)

1️⃣ 초기 상태

vec = [1, 2, 3]

• depth = 0, n = 3
• i = 0, 1, 2에 대해 루프를 돌면서 swap(0, i) 실행

---

2️⃣ depth=0에서 i=0 선택 (swap(0,0))

swap(0,0) → [1, 2, 3]
Permutation_recur(1, 3) 호출

• 자기 자신을 swap했으므로 그대로 진행.

---

3️⃣ depth=1에서 i=1 선택 (swap(1,1))

swap(1,1) → [1, 2, 3]
Permutation_recur(2, 3) 호출

• 자기 자신을 swap했으므로 그대로 진행.

---

4️⃣ depth=2에서 i=2 선택 (swap(2,2))

swap(2,2) → [1, 2, 3]
Permutation_recur(3, 3) 호출

✅ depth == n이므로 출력

출력: 1 2 3

🚀 순열 하나 완성!

---

5️⃣ 백트래킹 수행 (swap(2,2) 복구)

• swap(2,2)을 다시 실행해서 원래 상태 [1, 2, 3] 유지.

---

6️⃣ depth=2에서 i=2 대신 다른 값 없으므로 종료

• i = 2까지만 실행했으므로 depth=1로 돌아감.

---

7️⃣ depth=1에서 i=2 선택 (swap(1,2))

swap(1,2) → [1, 3, 2]
Permutation_recur(2, 3) 호출

---

8️⃣ depth=2에서 i=2 선택 (swap(2,2))

swap(2,2) → [1, 3, 2]
Permutation_recur(3, 3) 호출

✅ depth == n이므로 출력

출력: 1 3 2

---

9️⃣ 백트래킹 수행

• swap(2,2)을 다시 실행해서 원래 상태 [1, 3, 2] 유지.
• swap(1,2)을 다시 실행해서 원래 상태 [1, 2, 3] 복구.

---

🔄 같은 과정이 반복됨

• depth=0로 돌아와서 i=1 선택 (swap(0,1))
• depth=1에서 i=1, i=2 탐색
• depth=0로 돌아와서 i=2 선택 (swap(0,2))
• 모든 경우를 탐색할 때까지 반복!

---

🔍 전체 실행 순서 (트리 구조)

Permutation_recur(0, 3)   // depth=0
 ├── swap(0,0): [1,2,3] → Permutation_recur(1, 3)
 │   ├── swap(1,1): [1,2,3] → Permutation_recur(2, 3)
 │   │   ├── swap(2,2): [1,2,3] ✅ 출력 (1,2,3)
 │   │   ├── (백트래킹)
 │   ├── swap(1,2): [1,3,2] → Permutation_recur(2, 3)
 │   │   ├── swap(2,2): [1,3,2] ✅ 출력 (1,3,2)
 │   │   ├── (백트래킹)
 │   ├── (백트래킹)
 │
 ├── swap(0,1): [2,1,3] → Permutation_recur(1, 3)
 │   ├── swap(1,1): [2,1,3] → Permutation_recur(2, 3)
 │   │   ├── swap(2,2): [2,1,3] ✅ 출력 (2,1,3)
 │   │   ├── (백트래킹)
 │   ├── swap(1,2): [2,3,1] → Permutation_recur(2, 3)
 │   │   ├── swap(2,2): [2,3,1] ✅ 출력 (2,3,1)
 │   │   ├── (백트래킹)
 │   ├── (백트래킹)
 │
 ├── swap(0,2): [3,2,1] → Permutation_recur(1, 3)
 │   ├── swap(1,1): [3,2,1] → Permutation_recur(2, 3)
 │   │   ├── swap(2,2): [3,2,1] ✅ 출력 (3,2,1)
 │   │   ├── (백트래킹)
 │   ├── swap(1,2): [3,1,2] → Permutation_recur(2, 3)
 │   │   ├── swap(2,2): [3,1,2] ✅ 출력 (3,1,2)
 │   │   ├── (백트래킹)
 │   ├── (백트래킹)

---

📌 정리

1. swap(0,0) → swap(1,1) → swap(2,2) 이렇게 진행되면서 각 자리별로 가능한 숫자를 넣는다.
2. depth == n이 되면 출력.
3. 백트래킹(swap으로 원래 상태 복구)을 통해 모든 조합을 탐색.

👉 결국 swap을 이용해 "현재 자리(depth)에 올 수 있는 모든 값"을 넣으면서 순열을 찾는 것!
👉 이제 swap(0,0), swap(1,1), swap(2,2)가 왜 필요한지 이해되셨나요? 😃

혹시 추가로 이해가 안 되는 부분 있으면 더 설명해드릴게요! 🚀

---

🚀 조합 vs 순열 차이 정리

개념 조합(Combination) 순열(Permutation)

순서	❌ 무관 (ex: {1,2} == {2,1})	✅ 중요 (ex: {1,2} ≠ {2,1})
방법	r-1을 감소시키며 선택	swap을 활용하여 순서 바꿈
중복 여부	중복 없이 선택	중복 허용
백트래킹	선택 후 해제	swap() 후 원상 복구

---

🛠 결론

1. 조합은 "현재 선택한 원소를 유지하며 다음 원소를 선택"하는 방식.
2. 순열은 "현재 위치에서 가능한 모든 원소를 swap"하며 순서를 바꾸는 방식.