완전탐색 — 순열 / 조합

관련 문제

문제	난이도	핵심
소수 찾기	Lv.2	순열로 숫자 조합
후보키	Lv.2	조합으로 컬럼 선택
메뉴 리뉴얼	Lv.2	조합 빈도 계산

---

1. 개념

순열과 조합은 여러 원소 중 일부를 선택하는 방식이다.

	정의	순서	예시 (1,2,3 중 2개)
순열 (Permutation)	순서 있게 나열	O	12, 13, 21, 23, 31, 32
조합 (Combination)	순서 없이 선택	X	12, 13, 23

순열은 n!/(n-r)!가지, 조합은 n!/(r!*(n-r)!)가지다.

---

2. 동작 과정

[1, 2, 3] 중 2개를 선택하는 조합

pick(0, [])
├── pick(1, [1])
│   ├── pick(2, [1,2]) ✅
│   └── pick(3, [1,3]) ✅
├── pick(2, [2])
│   └── pick(3, [2,3]) ✅
└── pick(3, [3]) → 1개뿐이라 스킵

재귀로 하나씩 선택해나가면서 r개가 채워지면 결과에 추가한다.

---

3. 핵심 사용 패턴

visited 배열로 순열 구현

boolean[] visited = new boolean[n];
List<Integer> result = new ArrayList<>();

void permutation(int[] arr, int depth, int r) {
    if (depth == r) {
        // result 처리
        return;
    }
    for (int i = 0; i < arr.length; i++) {
        if (!visited[i]) {
            visited[i] = true;
            result.add(arr[i]);
            permutation(arr, depth + 1, r);
            result.remove(result.size() - 1);
            visited[i] = false;
        }
    }
}

start 인덱스로 조합 구현

List<Integer> result = new ArrayList<>();

void combination(int[] arr, int start, int r) {
    if (r == 0) {
        // result 처리
        return;
    }
    for (int i = start; i < arr.length; i++) {
        result.add(arr[i]);
        combination(arr, i + 1, r - 1);
        result.remove(result.size() - 1);
    }
}

---

4. 핵심 포인트 2가지

순열 vs 조합 구분

순서가 중요하면 순열, 아니면 조합이다.

"1,2,3 중 2명을 뽑아 줄 세우기" → 순열 (12 ≠ 21)
"1,2,3 중 2명을 뽑아 팀 구성"   → 조합 (12 == 21)

순열은 visited, 조합은 start

순열은 이미 사용한 원소를 다시 쓰면 안 되니까 visited로 체크한다. 조합은 앞에서 선택한 원소를 다시 선택하면 안 되니까 start 인덱스를 올려가며 탐색한다.

---

5. 시간복잡도

유형	시간복잡도	N=10일 때 경우의 수
순열 nPr	O(n!/(n-r)!)	10P3 = 720
조합 nCr	O(n!/(r!(n-r)!))	10C3 = 120

N이 커지면 경우의 수가 폭발적으로 늘어나기 때문에 N ≤ 10~15 정도일 때 주로 사용한다.

---

6. 주의사항

• 순열은 visited, 조합은 start. 이 두 가지만 기억하면 템플릿은 외운 거다.
• 재귀 깊이를 r로 제어해라. depth == r일 때 결과를 저장하고 return하는 구조가 기본이다.
• result 배열에서 원소를 제거할 때 인덱스 주의. ArrayList에서 remove(int index)와 remove(Object o)는 다르게 동작한다. Integer로 명시적 캐스팅해야 할 때가 있다.
• N이 크면 다른 방법을 고민해라. N이 20을 넘어가면 순열/조합만으론 시간초과가 날 수 있다.