안 쓰던 블로그

탐욕 알고리즘이란? 탐욕법이란 이름 그대로 ‘눈 앞에 보이는 최선’을 탐욕적으로 선택하는 것을 반복하는 알고리즘 설계 패러다임 중 하나입니다. 탐욕법을 이용한 일고리즘을 탐욕 알고리즘, 그리디 알고리즘이라고 합니다. 전체를 여러 조각으로 나눠서 각 단계마다 답의 일부를 만들어 간다는 점에서 완전 탐색과 비슷하지만, 모든 선택지를 보는 완전 탐색과 달리 탐욕 알고리즘은 지금 당장 가장 좋은 해답을 선택합니다. 탐욕 알고리즘의 대표적인 문제로는 각 물건의 무게와 가치가 주어졌을 때, 가방에 가치가 높은 물건을 최대한 많이 담는 경우를 찾는 배낭 문제(Knapsack problem)이 있습니다. 탐욕 알고리즘의 한계 탐욕 알고리즘은 매 순간 가장 좋은 선택지만 고르기 때문에 전체적으로 봤을 때 더 좋은 선택지..