패스트캠퍼스 챌린지 14일차

---

Part 2. 알고리즘 이론

Ch 19. 탐욕 알고리즘

01. 탐욕 알고리즘의 이해 (1)

02. 탐욕 알고리즘의 이해 (2)

 

---

오늘은 탐욕 알고리즘에 대해 배웠다. 처음 탐욕 알고리즘이란 단어를 들었을 때, 신기하다고 생각했다. 알고리즘이 다른 학문으로 비교하자면 이론과 같을 텐데 내가 그동안 공부했던 법학이나 경영학에서 어떤 이론에 `탐욕`이라는 부정적인 단어가 붙은 걸 본 기억이 없기 때문이다. 아마 내일 공부할 다익스트라 알고리즘을 보면서 알고리즘의 이름들이 심상치 않다고 생각했다. 오늘 공부하기 전 난이도 조절을 위해 쉬운 탐욕 알고리즘을 먼저 배운다고 하셨다. 앞에서 배웠던 것과 다르게 탐욕 알고리즘이나 다익스트라 알고리즘은 용어만 듣고 그 내용은 공부한 적이 없어서 어려웠다. 탐욕 알고리즘도 어려웠는데 이다음은 얼마나 어려울까 걱정됐다.

 탐욕 알고리즘은 매 순간 가장 적합하다고 생각하는 경우를 선택하는 알고리즘이다. 트리에서 여러 개의 자식 노드 중 하나를 선택해 잎 노드에 이르듯 탐욕 알고리즘도 매 순간 최적의 선택을 하여 최종값을 구하는 방식이다. 이 예시로 동전 문제와 부분 배낭 문제를 알려주셨다. 동전 문제는 주어진 동전으로 일정 금액을 채우는 문제이다. 예를 들어 500원, 100원, 10원의 동전을 가장 적게 사용하여 3,390원을 만드는 것이다. 가장 큰 단위부터 생각해보면 500원 6개, 100원 3개, 10원 9개, 총 18개로 만들 수 있다. 부분 배낭 문제는 무게와 가치가 다른 여러 개의 물건을 두고 N 키로까지 넣을 수 있는 배낭에 최대 가치를 갖도록 물건을 넣는 것이다. 이때도 무게/가치로 무게별 가치를 구하고 가장 가치 있는 물품부터 가방에 넣는다. 동전 문제의 경우 코드로 구현하는 게 쉬웠지만 부분 배낭 문제는 코드가 어렵다. 예전에 배운 Comparable 인터페이스를 이용하는데 다시 봐야 할 것 같다.

 

 

 

---

https://bit.ly/3FVdhDa

수강료 100% 환급 챌린지 | 패스트캠퍼스

- 본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.-