전파 최대화 문제 3 (Greedy Algorithm)

탐욕 알고리즘(Greedy Algorithm)

1. 기본 개념

• 매 단계에서 현재 상황에서 가장 좋아 보이는 선택을 함
• 한 번 선택한 것은 번복하지 않음
• 전체 최적해를 보장하지는 않지만, 계산이 빠르고 실용적

2. 알고리즘 진행 과정 (예: SNS 인플루언서 3명 선택하기)

Step 1: 첫 번째 인플루언서 선택

집합 {1}, {2}, ..., {|V|} 중에서 선택
- 각각 시뮬레이션으로 영향력 측정
- 가장 영향력 큰 사람 'A' 선택
결과: {A}

Step 2: 두 번째 인플루언서 선택

집합 {A,1}, {A,2}, ..., {A,|V|} 중에서 선택
- A와 함께했을 때 시너지 고려
- 추가 영향력이 가장 큰 'B' 선택
결과: {A,B}

Step 3: 세 번째 인플루언서 선택

집합 {A,B,1}, {A,B,2}, ..., {A,B,|V|} 중에서 선택
- A,B와 함께했을 때 시너지 고려
- 추가 영향력이 가장 큰 'C' 선택
결과: {A,B,C}

3. 주요 특징

• 근시안적 선택: 현재 단계의 최선만 고려
• 이전 선택과의 조합 효과는 고려
• 목표 크기(k)에 도달할 때까지 반복

4. 실제 적용 예시: 학교 축제 홍보대사 선택

Step 1: 가장 영향력 있는 총학생회장 선택
Step 2: 총학생회장과 겹치지 않는 과학생회장 선택
Step 3: 앞선 둘과 겹치지 않는 동아리연합회장 선택

5. 장단점
   장점:

• 구현이 간단하고 빠름
• 실제로 꽤 좋은 결과 도출
• (1-1/e) ≈ 63% 이상의 성능 보장

단점:

• 전체 최적해를 찾지 못할 수 있음
• 이전 선택을 수정할 수 없음

이러한 탐욕 알고리즘은 완벽한 해결책은 아니지만, 현실적인 제약 조건에서 효율적으로 사용할 수 있는 실용적인 방법입니다.

---

최소 63% 이상의 성능이 보장

1. 가장 간단한 예시로 설명
   상황: 학교 홍보대사 3명을 뽑는 상황
   목표: 최대한 많은 학생에게 정보 전달

Step 1) 첫 번째 선택

- 최적해가 도달할 수 있는 전체 학생 수: 1000명이라고 가정
- 탐욕적 첫 선택으로 최소한 (1/3)명인 333명은 보장
  (왜? 최적의 3명이 각각 평균적으로 미치는 영향력의 최소 1/3은 가능)

Step 2) 두 번째 선택

- 남은 potential: 667명
- 이 중 최소한 (1/3)인 222명은 추가 보장
- 총 555명 보장 (333 + 222)

Step 3) 세 번째 선택

- 남은 potential: 445명
- 이 중 최소한 (1/3)인 148명은 추가 보장
- 총 703명 보장 (555 + 148)

2. 수학적으로 보면

첫 번째: (1/3) = 0.333
두 번째: (1/3)(2/3) = 0.222
세 번째: (1/3)(2/3)(2/3) = 0.148
----------------------------
총합: 0.703 = 70.3%

이런 식으로 계속 진행하면 극한값이 (1-1/e) ≈ 63%가 됩니다.

3. 더 직관적인 예시: 케이크 나누기

- 전체 케이크를 100%라고 할 때
- 매번 남은 케이크의 최소 1/3은 가져갈 수 있음
- 이걸 계속 반복하면
- 결국 최소 63%는 보장됨

4. 실제 적용

학교 전체 학생 1000명 중
- 첫 번째 홍보대사: 최소 333명
- 두 번째 홍보대사: 최소 222명 추가
- 세 번째 홍보대사: 최소 148명 추가
= 총 703명 이상 보장

즉, 매 선택마다 "남은 영향력의 일정 비율"을 반드시 가져갈 수 있다는 보장이 있기 때문에, 전체적으로 최소 63% 이상의 성능이 보장되는 것입니다.

이것이 이론적 하한선이라, 실제로는 대부분 이보다 훨씬 좋은 성능(90% 이상)을 보입니다.