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

부분집합(Subset), 탐욕 알고리즘(Greedy)

---

1. 오늘의 학습 흐름

• 부분집합(Subset) 구현 3가지: for문 → BitMask → 재귀
• SWEA 5215 햄버거 다이어트, SWEA 4012 요리사
• 탐욕 알고리즘(Greedy) 개념 + 동전 바꾸기
• 정올 1370 회의실 배정, 정올 2247 도서관

---

2. 부분집합(Subset)

N개의 원소에서 0개~N개를 선택하는 모든 경우다. 부분집합의 수는 항상 2^N개다. 각 원소를 "선택(1)" 또는 "비선택(0)"으로 표현하면 0부터 2^N-1까지의 이진수와 1:1 대응된다.

0000 → [] (공집합)
0001 → [d]
0010 → [c]
0011 → [c, d]
...
1111 → [a, b, c, d] (전체 집합)

방법 1 - for문 중첩 (SubsetTest1)

원소마다 0/1을 반복하는 for문을 N개 중첩한다. N이 고정일 때만 쓸 수 있다.

String[] input = "abcd".split("");
int[] subset = new int[4];

for (int i = 0; i < 2; i++) { subset[0] = i;
  for (int j = 0; j < 2; j++) { subset[1] = j;
    for (int k = 0; k < 2; k++) { subset[2] = k;
      for (int l = 0; l < 2; l++) { subset[3] = l;
        print(subset);
      }
    }
  }
}

N이 달라지면 코드 구조 자체를 바꿔야 한다. 순열에서 for문 → 재귀로 발전한 것처럼, 부분집합도 재귀나 BitMask로 일반화한다.

방법 2 - BitMask (SubsetTest2)

0부터 2^N-1까지 정수의 각 bit를 원소 선택 여부로 쓴다. N이 달라져도 코드 구조가 변하지 않는다.

int N = 24;
int[] subset = new int[N];

for (int i = 0, end = 1 << N; i < end; i++) {  // 0 ~ 2^N-1
    for (int j = 0; j < N; j++) {
        subset[j] = (i >> j) & 1;  // j번째 bit가 1이면 선택
    }
    // 부분집합 완성 후 처리
}
// 시간복잡도: O(2^N * N)

(i >> j) & 1이 핵심이다. i를 j칸 오른쪽으로 밀어서 j번째 bit를 맨 끝으로 가져온 다음, & 1로 0 또는 1만 추출한다.

N=24 기준으로 2^24 = 16,777,216개인데 속도가 빠른 이유가 bit 연산이 O(1)이기 때문이다.

방법 3 - 재귀 (SubsetTest3)

각 원소를 "선택" 또는 "비선택"으로 재귀를 두 갈래로 분기한다. 조합과 비슷하지만, 조합은 선택만 있고 부분집합은 선택과 비선택 두 갈래가 있다.

static int[] numbers = new int[N];  // 선택된 원소 저장

private static void subset(int depth, int len) {
    if (depth == N) {       // 모든 원소에 대해 결정 완료
        totalCnt++;
        // System.out.println(Arrays.copyOfRange(numbers, 0, len));
        return;
    }
    numbers[len] = input[depth];
    subset(depth + 1, len + 1);  // 선택
    subset(depth + 1, len);      // 비선택
}
// 호출: subset(0, 0)
// 시간복잡도: O(2^N)

순열/조합과 비교:

• 순열: for문 + visited
• 조합: for문 + start 파라미터
• 부분집합: 두 갈래 재귀 (선택 / 비선택)

---

3. SWEA 5215 - 햄버거 다이어트

칼로리 제한 내에서 맛 점수 합이 최대인 재료 조합을 찾는 문제다. 부분집합으로 모든 조합을 시도하면서 조건을 만족하면 최댓값을 갱신한다.

public static void subset(int cnt, int s, int total) {
    if (total > limitCal) return;   // 가지치기: 칼로리 초과면 더 볼 필요 없음
    if (cnt == N) {
        Answer = Math.max(s, Answer);
        return;
    }
    subset(cnt + 1, s + score[cnt], total + calorie[cnt]);  // 선택
    subset(cnt + 1, s, total);                               // 비선택
}

가지치기 위치가 중요하다. if (total > limitCal) return을 함수 진입부에 두면 칼로리가 초과된 순간 그 하위 탐색을 전부 건너뛴다.

---

4. SWEA 4012 - 요리사

N명을 두 팀으로 나눠 각 팀의 시너지 합 차이가 최소인 경우를 찾는 문제다. N/2명을 뽑는 조합(부분집합)으로 풀었다.

static boolean[] teamSplit = new boolean[N];
teamSplit[0] = true;  // 0번은 무조건 A팀으로 고정 → 대칭 경우 제거

static void dfs(int index, int count) {
    if (count == N / 2) {    // A팀 N/2명 확정
        result = calculate();
        min = Math.min(min, result);
        return;
    }
    if (index >= N) return;

    teamSplit[index] = true;
    dfs(index + 1, count + 1);  // A팀 선택
    teamSplit[index] = false;
    dfs(index + 1, count);      // B팀 선택
}

teamSplit[0] = true로 0번을 미리 A팀에 고정한 게 포인트다. 0번이 A팀/B팀 두 경우를 다 탐색하면 (A팀=0,1,2 / B팀=3,4,5)와 (A팀=3,4,5 / B팀=0,1,2)가 중복으로 나온다. 0번을 고정하면 이 대칭 경우를 절반으로 줄인다.

---

5. 탐욕 알고리즘(Greedy)

현재 단계에서 선택할 수 있는 것 중 가장 좋은 것을 선택하는 알고리즘이다.

주의할 점: 매 순간 최선의 선택이 전체 최선을 보장하지 않는다.

// 동전 {500, 100, 50, 10} → 항상 최적
// 동전 {500, 400, 100, 50, 10} → 800원을 바꿀 때
//   Greedy: 500 + 100 + 100 + 100 = 4개
//   최적:   400 + 400 = 2개  ← Greedy가 틀림

Greedy가 통하는 조건: 탐욕적 선택이 최적 부분 구조를 만족할 때. 문제의 구조를 파악하고 "Greedy가 맞는가"를 먼저 증명해야 한다.

static int[] coin = {500, 100, 50, 10};

public static void coinChange(int money) {
    for (int i = 0; i < coin.length; i++) {
        result[i] = money / coin[i];   // 해당 동전으로 최대한
        money %= coin[i];              // 나머지
    }
}

---

6. 정올 1370 - 회의실 배정

가장 많은 회의를 배정하는 문제다. 종료 시간이 빠른 회의를 먼저 선택하면 다음 회의가 들어올 공간이 최대로 생긴다.

Greedy 전략: 종료 시간 기준 오름차순 정렬 → 앞에서부터 시작 시간이 이전 회의 종료 시간 이후인 것만 선택

static class Room implements Comparable<Room> {
    int stime, etime, rnum;

    public int compareTo(Room o) {
        int ia = this.etime - o.etime;  // 종료 시간 오름차순
        if (ia == 0) ia = this.stime - o.stime;  // 같으면 시작 시간 오름차순
        return ia;
    }
}

// PriorityQueue로 자동 정렬
PriorityQueue<Room> list = new PriorityQueue<>();

Room room = list.poll();
int end = room.etime;
while (!list.isEmpty()) {
    room = list.poll();
    if (end <= room.stime) {   // 이전 회의 끝난 후 시작 가능
        cnt++;
        end = room.etime;
    }
}

Room이 Comparable을 구현했으므로 PriorityQueue가 알아서 종료 시간 기준으로 정렬한다. 어제 배운 PriorityQueue + Comparable이 여기서 바로 나왔다.

---

7. Greedy주의점

오늘 Greedy를 배우면서 언제 Greedy를 쓰고 언제 완전탐색을 쓰냐가 중요하다고 하셨다.

동전 바꾸기 예시에서 {500, 400, 100, 50, 10}처럼 동전 종류가 달라지면 Greedy가 틀린다. 반면 회의실 배정은 종료 시간 기준 Greedy가 항상 최적이다.

결국 Greedy는 증명이 먼저다. "이 문제에서 탐욕적 선택이 최적 부분 구조를 만족한다"는 게 보장될 때 써야 한다. 코테에서 Greedy로 보이는 문제도 틀린 경우가 많으니, 반례를 먼저 떠올려보는 습관이 필요하다. (저번 코테에 Greedy인줄 알고 풀었다가 틀렸다)

완전탐색(Brute-Force) → Greedy/DP 순으로 접근하는 게 안전하다. 완전탐색이 시간 초과라면 최적화 방법을 찾는 것이다.

---

8. 키워드 정리

부분집합 Subset Greedy

---

9. 내일의 목표

• 코테 연습 및 GSAT준비