이번 글에서는 그리디 알고리즘에 대해 다루어 보겠습니다. 가장 대표적인 예제인 동전 문제와 회의실 배정 문제와 함께 다룰 예정이니 참고해 주세요 1. 탐욕법이란? 탐욕법이란 미래를 고려하지 않고 현재 가장 최선의 선택을 하는 알고리즘입니다. 쉽게 말하면 한 번 선택하고 난 후 앞이나 뒤를 전혀 돌아보지 않는 알고리즘입니다. 2. 특징 그리디 알고리즘에서는 다음의 특징을 가집니다. 그리디 선택 속성(Greedy Choice Property) 현재 선택은 미래의 선택에 영향을 미치지 않습니다. 이를 그리디 선택 속성이라고 합니다. 최적 부분 구조 현재 선택들이 모여 전체의 최적해를 보장해야만 믿고 현재 최선의 선택을 할 수 있습니다. 앞에서 말했듯이 미래의 선택을 고려하지 않고 과거도 돌아보지 않기 때문에 ..

[목차] Task Scheduling Problem이란? Task Scheduling 알고리즘 Dynamic Programming 알고리즘 Greedy 알고리즘 예제 1. Task Scheduling Problem이란? 예제로는 [백준 1931번 회의실 배정]이 있다. 2. Task Scheduling 알고리즘 1) DP 2) Greedy 나중에 다른 그리디 문제를 풀 때에도 내가 떠올린 그리디 알고리즘이 올바른지 확인할 때 지금 당장 손해를 보더라도 나중 가서는 이득인 경우가 있을 수는 없는지 고민해보면 정당성을 확인하거나 반례를 찾을 때 도움이 됩니다. 3. 예제 유명한 예제 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11..