Data Structures and Algorithms (10)
Data Structure and Algorithms (10)
1. 탐욕 알고리즘 (Greedy Algorithm)
탐욕 알고리즘
- 최적의 해에 가까운 값을 구하기 위해 사용
- 여러 경우 중 하나를 결정해야할 때마다, 매순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서, 최종적인 값을 구하는 방식
ㅤ
ㅤ
ㅤ
ㅤ
ㅤ
2. 탐욕알고리즘 예시문제
1) 동전 문제
지불해야하는 값이 4720일 때 1원, 50원, 100원, 500원으로 동전의 수가 가장 적게 지불
- 가장 큰 동전부터 최대한 지불해야하는 값을 채우는 방식으로 구현 가능
- 탐욕 알고리즘으로 매순간 최적이라고 생각되는 경우를 선택
code
coin_list = [500, 100, 50, 1]
def min_coin_count(value, coin_list): total_coin_count = 0 details = list() coin_list.sort(reverse=True) // 역순 sort (큰값으로, 원래 sort는 작은값으로 자동 정렬) ㅤ for coin in coin_list: coin_num = value // coin total_coin_count += coin_num value -= coin_num * coin details.append([coin,coin_num[] return total_coin_count, details
2) 부분 배낭 문제 (Fractional Knapsack problem)
무게 제한이 k인 배낭에 최대 가치를 가지도록 물건을 넣는 문제
- 각 물건은 무게(w)와 가치(v)로 표현될 수 있음
물건은 쪼갤 수 있으므로 물건의 일부분을 배낭에 넣을 수 있음 - (반대로 0/1 Knapsack problem, 물건 쪼갤 수 없는 문제도 있음)
code
data_list = [(10,10), (15,12), (20,10), (25,8), (30,5)] / 무게(w), 가치(v) data_list = sorted(data_list, key=lamda x:x[1] / x[0], reverse = True) ㅤ // sorted라는 내장함수를 사용하는데 , 앞에는 list 변수가 입력으로 들어가고 어떤 기준으로 정렬할건지 key를 통해 정함 . -> x = 각 데이터, x[1] = 가치, x[0] = 무게 = 가치 / 무게 = 무게 단위당 가치 reverse True = 무게단위당 가치가 높은 것부터 봐야하기 때문에 큰순으로
def get_max_value (data+list, capacity): data_list = sorted(data_list, key=lamda x:x[1] / x[0], reverse = True) total_value = 0 details = list() ㅤ for data in data_list if capacity – data[0] >= 0: capacity -= data[0] total_value += data[1] details.append([data[0], data[1], 1] else: fraction = capacity / data[0] total_value += data[1] * fraction details.append([data[0], data[1], fraction]) break // capacity는 어차피 0이 될 것이기 때문에 코드 삽입 필요 X return total_value, details
탐욕알고리즘의 단점
그 순간의 최적의 해를 구하기 때문에 전체 문제에서의 최적 해라고 볼 수는 없음
-> 근사치 추정에 활용
-> 탐욕 알고리즘 최적해와 전체 최적해가 다름
본 게시글은 fastcampus 이준희강사 수업을 듣고 개인적으로 정리한 내용임을 밝힘.
Author And Source
이 문제에 관하여(Data Structures and Algorithms (10)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@anthony16/Data-Structure-and-Algorithms-10저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)