Greedy Algorithm
Reviewing what I studied, how this work will be explained as well.
Greedy 는 뒷일을 생각하지 않고, 가장 좋아보이는것부터 하나씩 순서대로 처리한다는 의미 (즉 명확한 기준 하나를 정하고 그기준에 따라 미리 정렬을 한다음에 하나씩 처리)! 즉 문제의 크기가 줄어드는 현상이 있다. 문제의 크기가 줄어들기 때문에, 전체의 시간 복잡도가 정렬에 더 치중이 많이 간다. 최적화 문제를 다룬다는 입장에서의 비교! 를 해보자.
Dynamic Programming 안에서는, n 번째 아이템을 넣는다 안넣는다의 차이가 있고, 그거에 따른 n-1 의 선택 을 하는지 안하는지에 따라서 Tree 를 결정할수 있다. Greedy 는 분기를 고려하지 않는다. 가장 좋은 아이템이 있다면, 넣는다, 아니면 안넣는다. 라는 방식으로 분기를 고려할 필요가 없다.
Greedy 의 장점으로서는 1. 구현하기가 쉽고 빠르며, 문제에 따라서 결과가 최적이 아닐 경우가 있다는 소리가 된다.
정리하자면, Greedy Algorithm 에서는 당장 눈에 보이는 최적의 것을 쫓는 알고리즘이라고 할수 있다. 항상 최적은 아니지만, 어느정도의 최적의 근사값? 을 빠르게 구할수 있다라는게 된다.
단순한 문제중 하나는 바로 거스름 돈 문제이다. 항상 적은 양의 화폐를 주는게 제일 편하다. 즉 560 원이라는게 있다면, 10 원짜리 56 개를 주는것이 아닌 500 원짜리 하나, 50 짜리 1개 10 원짜리 1개를 주는것이 총 3개로 편하다. 즉 무조건 더 큰 화폐단위 만큼 거슬러 주는게 좋다라는것으로 생각해서 이 문제는 Greedy 알고리즘으로 풀 수가 있다.
int main() {
int n, result = 0;
cin >> n;
result += n / 500;
n % = 500;
result += n / 100;
n % = 100;
result += n / 50;
n %= 50;
result += n/ 10;
cout << result;
}
이러한 문제 처럼 주로 무조건 긴대로, 많은대로, 짧은대로 라는 개념이 들어가서, Sort 기법이 들어간다. 대표적인 Kruskal Algorithm 이 될것 같다. 모든 간선을 정렬한 이후 짧은 간선부터 연결하는 MST 가 있을것 같다.
Activity Selection
def activitySelection(start, end):
ans = 0
finish = -1
for i in range(len(start)):
if start[i] > finish:
finish = end[i]
ans += 1
return ans
def activitySelectionNotSorted(start, end):
ans = 0
arr = []
for i in range(len(start)):
arr.append((end[i], start[i]))
arr.sort()
finish = -1
for i in range(len(start)):
if start[i] > finish:
finish = end[i]
ans += 1
return ans
if __name__ == "__main__":
# all sorted by the finished time.
start = [1, 3, 0, 5, 8, 5]
end = [2, 4, 6, 7, 9, 9]
print(activitySelection(start, end))
