[LG U+ 유레카 4기] WEEK 03 - 알고리즘 (5)

Swap 순열, 조합(Combination)

---

1. 오늘의 학습 흐름

• Swap 순열 (visited 없이 배열 자리교환으로 구현)
• SWEA 1247 최적 경로 풀이 3가지 비교
• 조합(Combination) 구현
• BOJ 1759 암호 만들기

---

2. Swap 순열

어제 배운 visited 방식 말고, 배열 원소를 직접 swap해서 순열을 구하는 방법이다.

[A B C]
└─ swap(A,A) → [A B C] → swap(B,B) → [ABC] ✓
                        → swap(B,C) → [ACB] ✓
└─ swap(A,B) → [B A C] → swap(A,A) → [BAC] ✓
                        → swap(A,C) → [BCA] ✓
└─ swap(A,C) → [C B A] → swap(B,B) → [CBA] ✓
                        → swap(B,A) → [CAB] ✓

depth 위치의 원소를 depth~N-1 사이의 각 원소와 swap → 재귀 → 다시 swap(복원)하는 구조다.

private static void permutation(int cnt, int dist, int prevX, int prevY) {
    if (dist >= min) return;  // 가지치기

    if (cnt == N - 1) {
        dist += Math.abs(prevX - homex) + Math.abs(prevY - homey);
        min = Math.min(min, dist);
        return;
    }

    for (int i = cnt; i < N; i++) {
        swap(cnt, i);                        // ① swap

        int nextX = customer[cnt][0];
        int nextY = customer[cnt][1];
        int move = Math.abs(prevX - nextX) + Math.abs(prevY - nextY);

        permutation(cnt + 1, dist + move, nextX, nextY);

        swap(cnt, i);                        // ③ swap 복원 (선택 해제)
    }
}

private static void swap(int i, int j) {
    int tempX = customer[i][0]; int tempY = customer[i][1];
    customer[i][0] = customer[j][0]; customer[i][1] = customer[j][1];
    customer[j][0] = tempX; customer[j][1] = tempY;
}

visited 방식과 비교하면 별도 배열이 필요 없다. swap 자체가 "선택"이고 복원 swap이 "선택 해제"다.

순열 구현 방식별 성능 비교

방식	시간복잡도	10P10 반복횟수	10P10 수행시간
중복순열	O(N^R)	-	-
순열 - 재귀(visited)	O(N^R - 중복)	6,235만	0.1초
넥퍼(Next Permutation)	O(N!)	986만	0.02초
순열 - swap	O(N!)	623만	0.02초

swap 방식이 반복 횟수가 가장 적다. visited 방식은 O(N^R - 중복)이라 실제 탐색 횟수가 N!보다 많지만, swap은 처음부터 O(N!)로 움직인다. 11P11에서 visited는 1.3초 컷이지만 swap은 0.2초 컷이다.

---

3. SWEA 1247 - 최적 경로

회사(출발) → 고객 N명 방문 → 집(도착)의 최단 거리를 구하는 문제다. 고객 방문 순서의 모든 순열을 시도하면서 최솟값을 찾는다. 맨해튼 거리(|x1-x2| + |y1-y2|)를 사용한다.

가지치기(Pruning)가 핵심

if (dist >= min) return;  // 현재까지 거리가 이미 최솟값 이상이면 더 볼 필요 없음

이 한 줄이 없으면 TLE. 있으면 통과. BackTracking에서 가지치기는 필수다.

세 가지 풀이 비교

재귀(visited) 버전 - 212ms

private static void permutation(int cnt, int dist, int startx, int starty) {
    if (cnt == N) {
        dist += Math.abs(startx - homex) + Math.abs(starty - homey);
        min = Math.min(min, dist);
        return;
    }
    if (dist >= min) return;  // 가지치기

    for (int i = 0; i < N; i++) {
        if (!visit[i]) {
            visit[i] = true;
            int ndist = Math.abs(startx - map[i][0]) + Math.abs(starty - map[i][1]);
            permutation(cnt + 1, dist + ndist, map[i][0], map[i][1]);
            visit[i] = false;
        }
    }
}

swap 버전 - 163ms

private static void permutation(int cnt, int dist, int prevX, int prevY) {
    if (dist >= min) return;
    if (cnt == N - 1) {
        dist += Math.abs(prevX - homex) + Math.abs(prevY - homey);
        min = Math.min(min, dist);
        return;
    }
    for (int i = cnt; i < N; i++) {
        swap(cnt, i);
        int move = Math.abs(prevX - customer[cnt][0]) + Math.abs(prevY - customer[cnt][1]);
        permutation(cnt + 1, dist + move, customer[cnt][0], customer[cnt][1]);
        swap(cnt, i);
    }
}

Node 클래스로 좌표 관리

public static void solve(int curr, int depth, int totalDist) {
    if (totalDist >= minDistance) return;  // 가지치기
    if (depth == N) {
        totalDist += distance(nodes[curr], nodes[1]);  // 집까지 거리 추가
        minDistance = Math.min(minDistance, totalDist);
        return;
    }
    for (int i = 2; i < N + 2; i++) {
        if (!visited[i]) {
            visited[i] = true;
            solve(i, depth + 1, totalDist + distance(nodes[curr], nodes[i]));
            visited[i] = false;
        }
    }
}

---

4. 조합(Combination)

순열은 순서가 중요하고, 조합은 순서가 없다. {1,2,3}에서 2개를 뽑으면 순열은 6가지, 조합은 3가지다.

구현에서 순열과의 차이는 단 하나다. for문의 시작점이 항상 i+1로 올라간다.

static int[] numbers;  // 뽑은 조합 저장
static int[] input;

private static void combi(int depth, int start) {
    if (depth == r) {         // r개 다 뽑으면 완성
        testcase++;
        // System.out.println(Arrays.toString(numbers));
        return;
    }
    for (int i = start; i < n; i++) {
        numbers[depth] = input[i];
        combi(depth + 1, i + 1);  // 다음은 i+1부터 → 이미 뽑은 건 다시 안 뽑음
    }
}
// 호출: combi(0, 0)

순열에서 combi(depth+1, 0)이었던 게 combi(depth+1, i+1)로 바뀐 것뿐이다. start를 올림으로써 이미 선택한 원소의 앞쪽은 다시 보지 않는다.

조합 시간복잡도 실측

25C12  → 조합 수 5,200,300    → 35ms  (안전)
26C13  → 조합 수 10,400,600   → 80ms  (안전)
30C9   → 조합 수 14,307,150   → 80ms  (안전)
27C14  → 조합 수 20,058,300   → 200ms (위험)
30C15  → 조합 수 1억 5천만    → 1.2초 (안됨)

30C15처럼 경우의 수가 1억을 넘어가면 TLE다. 백트래킹(가지치기)이 필요하다.

---

5. BOJ 1759 - 암호 만들기

조합 + 조건 필터링 문제다. C개의 알파벳 중 L개를 골라 암호를 만드는데, 최소 모음 1개, 최소 자음 2개가 있어야 한다.

포인트: 미리 정렬해두면 조합 결과가 자동으로 사전순이 된다.

HashSet으로 모음 체크

static Set<String> vowels = new HashSet<>(Arrays.asList("a","e","i","o","u"));

public static void combi(int depth, int start) {
    if (depth == L) {
        int vCount = 0, cCount = 0;
        for (String val : outputs) {
            if (vowels.contains(val)) vCount++;
            else cCount++;
        }
        if (vCount >= 1 && cCount >= 2) {
            System.out.println(String.join("", outputs));
        }
        return;
    }
    for (int i = start; i < C; i++) {
        outputs[depth] = inputs[i];
        combi(depth + 1, i + 1);
    }
}

BitMask로 모음 체크

// a,e,i,o,u 위치에 1을 세팅한 상수
static final int bitV = 0b100000100000100010001;

// 모음인지 확인: 알파벳 위치(alps[i]-'a')번째 bit가 1이면 모음
if ((bitV & (1 << alps[i] - 'a')) != 0)
    combi(depth+1, i+1, vowel+1, nonVowel);
else
    combi(depth+1, i+1, vowel, nonVowel+1);

HashSet.contains() 대신 bit 연산 하나로 모음 여부를 O(1)로 확인한다. 어제 배운 BitMask가 바로 여기서 쓰인다.

---

6. 키워드 정리

Swap 순열 가지치기 pruning 조합 Combination

---

7. 내일의 목표

• 코테 당일