내일배움캠프 69일차 - 자료구조 & 알고리즘 12주차 : 그리디(Greedy)
그리디(Greedy)
매 단계에서 "지금 가장 좋아 보이는 선택" 을 하고, 한번 선택하면 되돌아가지 않는다.
- 완전탐색(10주차): 모든 경로를 본다. O(2^n) ~ O(n!) → 느리지만 확실
- 백트래킹(11주차): 막히면 되돌아간다. O(2^n) 이하 → 빠르지만 보장되지 않음
- 그리디: 지금 최선만 본다, 되돌아가지 않는다. O(n) ~ O(n log n) → 매우 빠름 (조건부)
※ 이 세 개를 "탐색을 줄이는 세 단계" 로 본다. (정확성과 속도에 따라 도구를 고른다)
그리디의 사용법
편의점에서 거스름돈 730원을 받아야 할 때,
동전은 {500원, 100원, 50원, 10원} 을 조합해서,
사용할 동전의 최소개수를 구하라.
: 가장 큰 순서대로(그리디) = 500 + 100 + 100 + 10 + 10 + 10 → 6개 (정답)
그리디의 단점
거스름돈 800원을 받아야 할 때,
동전 {500원, 400원, 100원} 을 조합해서 사용 최수개수를 구하라.
: 가장 큰 순서대로(그리디) = 500 + 100 + 100 + 100 → 4개 (오답)
: 실제 정답 = 400 + 400 → 2개 (정답)
→ 매 순간 최선의 선택이 전체 최선이 아닐 수도 있다.
그리디가 통하는 조건 - 배수관계
큰 동전이 작은 동전의 정수배일 때
: 그리디가 항상 최적
ex) {500원, 100원 ,50원} → 500 = 5×100 / 100 = 2×50 / 50 = 5×10
큰 동전 1개를 안 쓰면 → 작은 동전 여러 개로 채워야 함 → 반드시 더 손해.
: 따라서 "큰 동전 우선"이 항상 최적
※ 우리가 쓰는 동전이 우연히 배수 관계가 그리디가 통하는 것 뿐, "수 사이의 관계"가 그리디의 본질이다.
그리디의 함정 - 배수관계가 아니면?
동전 {500원, 400원, 100원} - 400은 500의 배수가 아니다.
: [그리디의 단점] 예시에서처럼 그리디가 최선이 아니게 된다.
그리디가 실패하는 이유
: 500원을 쓰는 "지금의 최선"이 전체 최선에 포함되지 않는다.
: 큰 동전이 작은 동전을 완전히 대체하지 못하는 구조 → DP를 사용해서 해결해야함.
그리디 문제 예시
회의실 문제 - 정해진 시간에 최대 몇 개?
 |
| 하나의 회의실에 6개 회의를 신청할 때, 겹치지 않게 최대 몇 개를 잡을 수 있을까? |
완전 탐색이라면 2^6 = 64가지 부분집합이 나온다. 그리디는 어떻게 풀어야 할까?
"종료 시간이 가장 빠른 회의부터 선택"
- 시작 시간 기준이라면: 일찍 시작해도 늦게 끝나면 뒤 회의를 다 막음.
- 종료 시간 기준이라면: 빨리 끝나는 회의부터 → 남은 시간 최대화 → 더 많은 회의를 넣을 여지 있음.
: sort()로 종료 시간을 정렬 → 한 번 순회하며 "겹치지 않으면 선택"
※ 정렬이 그리디의 동반자 - 정렬 한 번이 폭발적 효율을 만든다.
 |
| 종료 시간 빠른 순으로 재배열 - 위에서 아래로 그리디 진행 |
 |
| 그리디 알고리즘 진행 결과: A,C,D 3개 회의로 최적해 도달 |
그리디의 속성
① 탐욕적 선택 속성
"지금 최선의 선택"이 전체 최선에 포함된다.
ex1) 동전(배수): 큰 동전 우선이 최적의 일부
ex2) 회의실: 종료 빠른 회의가 최적의 일부
② 최적 부분 구조
부분 문제의 최적해가 전체 최적해의 일부.
ex) 730원 → 500원 쓰면 "남은 230원의 최적해" 문제로 축소
→ 두 조건 모두 만족하면 그리디, 하나라도 부족하면 백트래킹이나 DP를 사용하도록 한다.
 |
| 그리디는 눈앞의 최선(지역 최점)만 보기 때문에 결과적인 최선(전역 최적)을 보기 위해서는 DP를 사용해야 한다. ex) 동전{500,400,100}, 0/1 배낭 문제 등 |
그리디 문제 예제
예제 ① - 동전 교환
{500, 100, 50, 10}으로 730원을 만들어내라: 500 + 100 + 100 + 10 + 10 + 10 → 6개 (성공)
{500, 400, 100}으로 800원을 만들어내라: 500 + 100 + 100 + 100 → 4개(실패, 최적 2개)
판별: 배수 관계면 그리디 보장, 아니면 DP 필요
예제 ② - 회의실 배정
6개 회의 {A(1,3), B(2,5), C(3,4), D(4,7), E(6,8), F(5,9)} 에서 겹치지 않게 최대한 고른다.
종료 시간 기준 정렬 후 한번 순회
→ {A(1,3), C(3,4), B(2,5), D(4,7), (E6,8), F(5,9)}
→ {A(1,3), C(3,4), D(4,7)}
결과: 3개(A,C,D), 완전 탐색 2^6 = 64 대비 압도적 성능
예제 ③ - 배낭 문제
배낭 50kg과 물건 A(10kg/60원), 물건 B(20kg/100원), 물건 C(30kg/120원)이 있다. 배낭이 담을 수 있는 물건들의 최대 총합가치를 구하라. (물건은 한 종류당 하나씩이다.)
가정1) 물건은 쪼갤 수 있다.
무게당 가치순으로 정렬 (그리디)
: 물건A(60원/10kg = 6.0/kg), 물건B(100원/20kg = 5.0/kg), 물건C(120원/30kg = 4.0/kg)
: A→B→C 순으로 물건을 담는다.
→ 물건A 전체 담기 = 10kg, 60원
→ 물건B 전체 담기 = 10kg+20kg=30kg, 60원+100원=160원
→ 물건C 일부 담기 = 10kg+20kg+20kg(전체의 2/3)=50kg, 60원+100원+(4×20kg:80원)=240원
결과: 240원 : 정답
→ 그리디 보장 가능
가정2) 물건은 쪼갤 수 없다.
무게당 가치순으로 정렬 (그리디)
: 물건A(60원/10kg = 6.0/kg), 물건B(100원/20kg = 5.0/kg), 물건C(120원/30kg = 4.0/kg)
: A→B→C 순으로 물건을 담는다.
→ 물건A 전체 담기 = 10kg, 60원
→ 물건B 전체 담기 = 10kg+20kg=30kg, 60원+100원=160원
→ 물건C 전체 담기 = 10kg+20kg+30kg=60kg > 배낭 50kg (담을 수 없음)
결과: 160원 (실제 최적해: 220원) : 오답
→ 이런 경우에는 DP가 필요
예제 ④ - 최소 신장 트리 (크루스칼)
5개 도시를 잇는 간선을 최소비용으로 모두 연결하라.
: 서울, 부산, 대구, 인천, 광주
간선 목록(비용 오름차순)
: 서울-인천 (비용: 2)
: 서울-대구 (비용: 3)
: 대구-광주 (비용: 4)
: 대구-부산 (비용: 5)
: 서울-부산 (비용: 6)
: 대구-광주 (비용: 7)
: 부산-광주 (비용: 8)
: 인천-대구 (비용: 9)
간선을 비용 오름차순로 정렬(그리디)하고 현재 연결되지 않은 도시쌍만(사이클X) 채택
→ 서울-인천 (비용: 2) ✓
→ 서울-대구 (비용: 3) ✓
→ 대구-광주 (비용: 4) ✓
→ 대구-부산 (비용: 5) ✓ → 서울-부산 (비용: 6)
→ 대구-광주 (비용: 7)
→ 부산-광주 (비용: 8)
→ 인천-대구 (비용: 9)
총 비용: 14
세 전략 비교
CS 돋보기
OS 스케줄링 - SJF
내 컴퓨터에서 여러 프로그램이 돌아갈 때 CPU 시간을 어떻게 나눌까?
Shortest Job First(SJF): 가장 짧은 작업부터 처리 - 평균 대기 시간 최소화
작업 시간: A(5초), B(2초), C(8초), D(1초)
SJF 실행 순서: D(1초)→B(2초)→A(5초)→C(8초)
매 단계 "지금 가장 빨리 끝날 작업" 선택을 한다. (그리디)
허프만 인코딩 - 압축의 핵심
 |
| 매 단계 "빈도가 가장 낮은 두 노드를 합친다" = 그리디 ZIP·JPEG·MP3 - 모든 압축의 근간 |
네트워크 라우팅 - 패킷도 그리디 사용
인터넷의 데이터 패킷이 목적지까지 갈 때, 각 라우터는 "지금 가장 빠른 다음 경로"를 선택
전체 네트워크 상태를 파악할 수 없으니 지역적 최선으로 진행.
실전에서는?
게임 개발
게임 AI에서 "매 턴 가장 유리한 행동"이 그리디 방식.
- 자원 관리 게임: "지금 가장 효율적인 건물을 짓는다."
- 전투 AI: "HP가 가장 적은 적을 먼저 공격" / "지금 대미지 최대인 스킬"
- A* 휴리스틱: "목적지에 가까워지는 방향 우선 탐색" - 그리디적 사고
- 매치메이킹: "현재 대기 중인 비슷한 실력의 플레이어부터 매칭"
빠른 결정이 필수인 실시간 게임에서는 그리디는 가성비 최강을 자랑한다.
웹·서버
"지금 가장 좋은 선택"이 곳곳에 쓰인다.
- CDN: 사용자에게 가장 가까운 서버 선택 (지역 그리디)
- 로드 밸런서: "현재 가장 여유로운 서버"에 요청 분배
- LRU 캐시: 가장 오래 안 쓴 것을 버린다. (지금 가장 안 중요해 보이는 것)
- 광고 입찰: "지금 가장 가치 높은 광고"부터 노출
백엔드 인프라의 결정 로직 상당 부분이 그리디 변형이다.
일반 CS
효율적이면서 최적해를 보장하는 황금 알고리즘 - 조건이 맞을 때만.
- 허프만 인코딩: 데이터 압축의 근간
- 크루스칼 / 프림: 최소 신장 트리
- 다익스트라: 최단 경로 (프로그래머스 Level5 알고리즘)
- Greedy Approximation: "완벽보다 빠른 실용"의 근사 해법
"완벽한 정답"이 필요 없고 "빠르게 괜찮은 답"이 필요할 때 자주 등장한다.
오늘의 핵심
- 그리디 = "매 순간 최선, 번복 없음": 미래를 보지 않고 현재만 본다. O(n)~O(n log n)
- 두 조건이 필요: ① 탐욕적 선택 속성, ② 최적 부분 구조. 둘 다 만족해야 그리디 보장.
- 함정 (지역≠전역): 동전 비배수, 0/1 배낭은 그리디 실패 → DP가 필요
- 정렬이 그리디의 동반자: 종료 시간 / 무게당 가치 / 거리 - 정렬이 전처리
- Level3 흐름: 완전 탐색 → 백트래킹 → 그리디 → DP
댓글
댓글 쓰기