순열과 조합 알아보기

알고리즘 공부하게 되면 순열과 조합은 마주할 수 밖에 없는 개념이다. 분명 중고교 시절 배웠던 내용이지만, 막상 코드로 구현해보고자 하면 쉽지 않다.

---

✅  순열

순열은 순서가 영향있는 경우의 수 집합 개념이다. 음식을 주문하는 순서가 좋은 예시이다.

예를 들어, 아메리카노와 스무디를 주문하는 경우, (아메리카노 - 스무디), (스무디 - 아메리카노)로 경우의 수는 두 가지이다.

🔍 코드로 알아보기

/*
* @Param numbers 뽑기 대상
* @Param output 뽑힌 숫자들
* @Param visited 뽑힌 숫자를 기록
* @param depth 뽑고있는 깊이
* @Param picks 뽑는 개수
*/
public static void perm(int[] numbers, int[] output, boolean[] visited, int depth, int picks) {
    if (depth == picks) {
        System.out.println(Arrays.toString(output));
        return;
    }

    for (int i = 0; i < numbers.length; i++) {
        if (!visited[i]) {
            visited[i] = true;
            output[depth] = numbers[i];
            perm(numbers, output, visited, depth + 1, picks);
            visited[i] = false;
        }
    }
}

1. _!numbers!_에 담긴 각 숫자들을 돌면서 _!visited!_의 동일한 인덱스를 _!true!_로 지정하고 _!perm!_ 함수를 재 실행한다.

2. 함수를 실행시킨 다음에는 아까 변경한 _!visited!_의 값을 되돌린다. 현 _!depth!_의 다음 함수들도 실행시켜야 하기 때문이다.

• (i = 0) _!output!_에 1을 담았고, 다음 함수를 실행했다.
• (i = 1) _!output!_에 2를 담았고, 다음 함수를 실행한다. _!visited!_의 0, 1 각각의 인덱스의 값은 _!true!_이다. 직접에 뽑은 값도 뽑힌 것으로 간주 된 것이다. (실제로는 2만 뽑혀있다!) -> _!visited!_의 값을 되돌리는 이유

3. _!visited!_가 _!false!_ 일 때만 _!output!_에 값을 넣도록 해서, 배열 내 중복된 값이 입력되지 않도록 한다.

4. 함수의 첫 시작은 _!picks!_(뽑기 개수)와 _!depth!_(뽑힌 개수)를 비교해 동일하면 콘솔에 _!output!_을 출력한다.

 

1 ~ 4까지의 숫자 중 네 개의 숫자를 뽑았다.

✅  조합

반면, 조합은 순서와 무관하게 뽑는 것이다. (아메리카노 - 스무디) 세트 하나로 묶인다.

순서 의미가 없기 때문에 순회하는 요소를 뽑았거나 뽑지 않은 경우만 고려하면 된다. (지나친 요소는 다시 보지 않는다.)

🔍 코드로 알아보기

public static void comb(int[] numbers, int[] output, int start, int endNum, int picks) {
    if (picks == 0) {
        System.out.println(Arrays.toString(output));
        return;
    }

    for (int i = start; i < endNum; i++) {
        output[picks - 1] = numbers[i];
        comb(numbers, output, i + 1, endNum, picks - 1);
    }
}

1. 조합은 한 번 방문한 수는 다시 방문할 필요가 없다. 그렇기에 _!start!_을 인수로 사용해, 다음 함수 실행에서 순회 할 범위를 한 칸 줄인다.

• 순열에서는 대상 숫자들을 모두 순회하되, _!visited!_ 배열을 통해 방문 여부를 통제했다. 앞에서는 뽑히지 않았어도 뒷 순서에서 언젠가 뽑힐 수 있기 때문이다.
• 반면, 조합에서는 그저 자기 차례에서 뽑혔나 안뽑혔나에서 결정된다. 뒤에서는 뽑힐 수가 없다. 그러므로 순회 범위를 좁혀 다시 순회되지 않게끔 하는 것이다.

2. 범위를 줄이며 탐색하며, 뽑기 개수인 _!picks!_가 0일 때 결과를 콘솔에 표시한다.

 

1 ~ 4 중에 네 개를 뽑는 조합은 하나 밖에 없다.

 

 

✔️ 소스코드 및 온라인 실행환경 : https://replit.com/@peaks26/Combination-And-permutation?v=1