Permutation 및 Combination

순열과 조합은 주어진 집합에서 원소들을 선택하는 방법론으로, 다양한 알고리즘 문제에서 빈번히 사용된다. 순열은 원소의 순서를 고려하여 선택하는 방식이고, 조합은 순서와 상관없이 원소를 선택하는 방식이다. 각각 중복을 허용하는 경우와 허용하지 않는 경우로 나뉘어 구현할 수 있다.

순열(Permutation)

개념

순열은 n개의 원소 중에서 r개의 원소를 순서를 고려하여 선택하는 방식이다. 예를 들어, n = 3, r = 2인 경우 [1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]와 같은 모든 가능한 순열을 생성한다.

로직

1. 주어진 배열에서 첫 번째 원소를 선택한다.
2. 첫 번째 원소를 제외한 나머지 원소들로 재귀적으로 순열을 생성한다.
3. 선택된 원소와 나머지 원소들을 합쳐서 최종 순열을 생성한다.

예제 코드 (중복을 허용하지 않는 순열)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;

public class PermutationWithLinkedList {
    private static LinkedList<Integer> list;
    private static boolean[] check;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] in = br.readLine().split(" ");
        int n = Integer.parseInt(in[0]);
        int r = Integer.parseInt(in[1]);

        list = new LinkedList<>();
        check = new boolean[n + 1];
        permutation(n, r);
    }

    private static void permutation(int n, int r) {
        if (list.size() == r) {
            print();
            return;
        }

        for (int i = 1; i <= n; i++) {
            if (!check[i]) {
                list.add(i);
                check[i] = true;
                permutation(n, r);
                check[i] = false;
                list.removeLast();
            }
        }
    }

    private static void print() {
        for (int value : list) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}

예제 코드 (중복을 허용하는 순열)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;

public class PermutationWithRepetition {
    private static LinkedList<Integer> list;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] in = br.readLine().split(" ");
        int n = Integer.parseInt(in[0]);
        int r = Integer.parseInt(in[1]);

        list = new LinkedList<>();
        rePermutation(n, r);
    }

    private static void rePermutation(int n, int r) {
        if (list.size() == r) {
            print();
            return;
        }

        for (int i = 1; i <= n; i++) {
            list.add(i);
            rePermutation(n, r);
            list.removeLast();
        }
    }

    private static void print() {
        for (int value : list) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}

조합(Combination)

조합은 n개의 원소 중에서 r개의 원소를 순서와 상관없이 선택하는 방식이다. 예를 들어, n = 3, r = 2인 경우 [1, 2], [1, 3], [2, 3]과 같은 모든 가능한 조합을 생성한다. [1, 2]와 [2, 1]은 동일한 조합으로 간주한다.

로직

1. 주어진 배열에서 첫 번째 원소를 선택하거나 선택하지 않는다.
2. 첫 번째 원소를 선택한 경우, 나머지 원소들로 재귀적으로 조합을 생성한다.
3. 첫 번째 원소를 선택하지 않은 경우, 나머지 원소들로 재귀적으로 조합을 생성한다.

예제 코드 (중복을 허용하지 않는 조합)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;

public class Combination {
    private static int[] comArr;
    private static LinkedList<Integer> list = new LinkedList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] in = br.readLine().split(" ");
        int n = Integer.parseInt(in[0]);
        int r = Integer.parseInt(in[1]);

        comArr = new int[r];
        combination(n, r, 0, 1);
    }

    private static void combination(int n, int r, int index, int target) {
        if (r == 0) {
            print();
            return;
        }

        if (target > n) return;

        comArr[index] = target;
        combination(n, r - 1, index + 1, target + 1); // 선택한 경우
        combination(n, r, index, target + 1); // 선택하지 않은 경우
    }

    private static void print() {
        for (int value : comArr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}

예제 코드 (중복을 허용하는 조합)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;

public class CombinationWithRepetition {
    private static int[] comArr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] in = br.readLine().split(" ");
        int n = Integer.parseInt(in[0]);
        int r = Integer.parseInt(in[1]);

        comArr = new int[r];
        reCombination(n, r, 0, 1);
    }

    private static void reCombination(int n, int r, int index, int target) {
        if (r == 0) {
            print();
            return;
        }

        if (target > n) return;

        comArr[index] = target;
        reCombination(n, r - 1, index + 1, target); // 선택한 경우
        reCombination(n, r, index, target + 1); // 선택하지 않은 경우
    }

    private static void print() {
        for (int value : comArr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}

결과 예제

중복을 허용하지 않는 순열 (n=3, r=2)

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

중복을 허용하는 순열 (n=3, r=2)
1 1 
1 2 
1 3 
2 1 
2 2 
2 3 
3 1 
3 2 
3 3 

중복을 허용하지 않는 조합 (n=3, r=2)
1 2 
1 3 
2 3 

중복을 허용하는 조합 (n=3, r=2)
1 1 
1 2 
1 3 
2 2 
2 3 
3 3 

So...

순열과 조합은 다양한 알고리즘 문제에서 중요한 역할을 한다. 순열은 원소의 순서를 고려하여 선택하는 반면, 조합은 순서를 고려하지 않고 원소를 선택한다. 이를 통해 다양한 문제를 효율적으로 해결할 수 있으며, 중복을 허용하는 경우와 허용하지 않는 경우로 나누어 구현할 수 있다. 오늘 학습을 통해 순열과 조합의 개념과 구현 방법을 이해하고, 이를 실제 코드로 작성해보며 그 중요성을 체험할 수 있었다.