-
탐욕 알고리즘 (Greedy Algorithm) 이란??Algorithm 2019. 2. 18. 15:48반응형
알고리즘 공부순서가 뒤죽박죽.. ㅎㅎ 개념을 알고난 뒤 다시 정리해야겠다.
이번 포스팅과 다음 포스팅은 탐욕 알고리즘과 다이나이믹 프로그래밍에 대해서 하겠습니다.
1. 탐욕 알고리즘이란
- 현재 상황에서 가장 좋아보이는 답을 선택합니다.
- 각 부분에서 최적을 선택하면 전체에서 최적이 될 것이라는 가정을 전제로 합니다.
- 기본적으로 값이 큰 경우대로 극단적으로 문제를 접근합니다.
2. 탐욕 알고리즘의 사용 예
① 분할 가능 배낭문제
- 여행가가 가지고 있는 배낭에는 담을 수 있는 무게의 최댓값이 정해져있고,
일정 가치와 무게가 있는 짐들을 배낭을 넣을 때 가치의 합이 최대가 되도록 짐을 고르는 문제
② 최소수의 동전으로 거스름돈 내주기
- 거스름돈을 내줄때 가장 적은 양의 동전을 내주는 문제
ex 1) 930원의 거스름돈을 500원, 200원, 50원, 10원의 동전으로 내줄 때,
500원 동전 1개 + 200원 동전 2개 + 10원 동전 3개 = 총 6개
총 6개의 동전으로 가장 적은 양의 동전으로 내줄 수 있다.
ex 2) 동전의 단위가 다르게 바뀐다면?
930원의 거스름돈을 500원, 300원, 30원, 10원의 동전으로 내줄 때,
500원 동전 1개 + 300원 동전 1개 + 30원 동전 4개 + 10원 동전 1개 = 총 7개 이지만
300원 동전 3개 + 30원 동전 1개 = 총 4개의 더 작은 동전의 양으로 내줄 수 있다.
* 이렇게 동전의 단위가 바뀌었을 때 그리디알고리즘으로 푼다면 성립하지 않게되는데, 이때 동적 프로그래밍이 필요합니다.
3. 탐욕 알고리즘 vs 동적 프로그래밍
탐욕 알고리즘
동적 프로그래밍
하위 문제를 풀기전에 선택합니다.
하위 문제를 풀고 나서 선택합니다.
항상 하나의 문제만을 고려합니다.
동시에 여러 개의 하위 문제를 고려합니다.
4. 탐욕 알고리즘 구현
반응형'Algorithm' 카테고리의 다른 글
깊이 우선 탐색(Depth First Search) - DFS에 대해 알아보자 (0) 2019.02.16 너비 우선 탐색(Breath First Search) - BFS 에 대해 알아보자 (0) 2019.02.16 유클리드 호제법에 대해 알아보자!! (0) 2019.02.11 에라토스테네스의 체에 대해 알아보자 (2) 2019.02.09 크루스칼 알고리즘(Kruskal Algorithm)에 대해 알아보자!! (0) 2019.02.07