알고리즘
욕심쟁이 (Greedy)
현재 상태에서 가장 좋아 보이는 선택을 반복하는 알고리즘. 전체 최적해를 보장하지 않지만 특정 조건에서 최적해를 구할 수 있다.
시간 복잡도
O(n log n) ~ O(n)
공간 복잡도
O(1)
핵심 포인트
- 탐욕적 선택 속성 (Greedy Choice Property) 확인이 선행 조건
- 최적 부분 구조 (Optimal Substructure) 가 성립해야 함
- 대표 문제: 거스름돈, 활동 선택, 크루스칼 MST
- DP 보다 구현이 단순하고 빠르나 적용 범위가 좁음
실습 코드 및 문제풀이 콘텐츠 준비 중입니다.