Algorithm
그리디 알고리즘 (Greedy Algorithm)
n_0_jun
2025. 1. 7. 14:00
반응형
그리디 알고리즘은 매 단계에서 가장 좋아 보이는 선택을 하는 방법론입니다. 최적화 문제를 해결하는 데 사용되지만, 항상 최적의 해를 보장하지는 않습니다.
주요 개념
- 욕심쟁이 방법: 현재 상황에서 가장 좋은 선택을 반복적으로 수행.
- 최적해 보장 조건: 선택한 해가 전체 문제의 최적해와 같음을 보장하려면 문제 자체가 특정 조건을 만족해야 함.
동전 바꾸기 문제
문제 설명
어떤 금액을 동전으로 바꿀 때 동전의 수를 최소화하는 문제입니다.
예시
- 동전 종류: 100원, 50원, 10원
- 금액: 200원
- 최적해: 100원 2개
- 160원짜리 동전 추가 시 그리디 알고리즘은 160원 1개 + 10원 4개를 반환, 최적해는 아님.
해결 방법: DP(Dynamic Programming)로 변형
- 각 금액에 대해 최소 동전 수를 배열에 저장하며 점진적으로 계산.
부분 배낭 문제
문제 설명
무게 제한이 있는 배낭에 최대 가치를 넣는 문제입니다.
- 시간 복잡도: O(nlogn)
- 가치가 높은 순서로 아이템을 배낭에 추가, 공간 부족 시 분할 추가.
활용
- 원자재 절단 최적화
- 금융 포트폴리오 구성
- Merkle-Hellman 배낭 암호 시스템
집합 커버 문제
문제 설명
최소한의 부분집합으로 전체 집합 U를 덮는 문제입니다.
예시: 신도시 학교 배치
- 전체 집합 U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
- 부분집합 S1 = {1, 2, 3, 8}, S2 = {1, 2, 3, 4, 8}, S6 = {5, 6, 7, 9, 10}
- 최적해: S2와 S6 선택 (U = S2 \u222a S6)
그리디 근사법
- 전체 집합 U에서 부분집합 탐색
- 가장 많은 커버를 제공하는 부분집합 선택
- 선택된 부분집합을 U에서 제거
- 반복 후 선택된 부분집합 출력
- 시간 복잡도: O(n^3)
활용
- 도시 계획 (공공 기관 배치)
- CCTV 최적 배치
- 바이러스 탐지, 기업 채용, 정보 검색 등
작업 스케줄링 문제
예시 1: 공장 기계 스케줄링
- 기계 수: 3
- 작업 시간 배열: {[0,2], [1,6], [1,5], [3,7], [5,9], [6,8], [7,8]}
- 종료 시간이 가장 빠른 기계에 작업 부여
예시 2: 회의실 배정
- 종료 시간이 가장 이른 회의부터 배정
- 최적해 보장
활용
- 생산 공정, 강의실 배정, 태스크 스케줄링 등
- 시간 복잡도: O(nlogn) + O(mn)
허프만 압축
원리
- 각 문자의 빈도수를 기반으로 이진 트리 생성.
- 왼쪽 자식엔 0, 오른쪽 자식엔 1을 할당.
예시
- 문자 빈도: A: 450, T: 90, G: 120, C: 270
- 허프만 코드 생성 후 압축:
- 압축된 파일 크기: 1,620 bits
- 아스키 코드 파일 크기: 7,440 bits
- 압축률: 21.8%
복호화
- 압축된 데이터: 10110010001110101010100
- 복호화 결과: G T T A C G A G A T
활용
- 팩스, 대용량 데이터 저장, MP3 압축
- 정보 이론에서 엔트로피 계산
- 시간 복잡도: O(nlogn)
결론
그리디 알고리즘은 단순하면서도 다양한 문제에 활용 가능합니다. 하지만 최적의 해를 보장하지 않는 경우도 있으므로, 문제의 특성을 잘 파악하고 필요에 따라 다른 알고리즘(DP 등)을 적용해야 합니다. 활용 예시는 도시 계획, 생산 공정 최적화, 데이터 압축 등 다양합니다.
반응형