그리디 알고리즘의 최적화의 경우를 알고리즘 예시를 들어 설명하고

소개글

교과목명 : 알고리즘
<과제명> 그리디 알고리즘의 최적화의 경우를 알고리즘 예시를 들어 설명하고, 그러디 알고리즘이 최적화 적용 알고리즘으로 선택이 안되는 경우도 예시를 들어 이유를 설명하시오

목차

Ⅰ. 서론

Ⅱ. 본론
1. 그리디 알고리즘
2. 그리디 알고리즘이 최적화 결과를 가지고 오는 경우
3. 그리디 알고리즘이 최적화 결과를 가지고 오지 않는 경우

Ⅲ. 결론

Ⅳ. 참고문헌

본문내용

우아한 형제들 배달 플랫폼 팀 개발자는 우아한 형제들 주최로 열렸던 온라인 개발자 행사에서 겉바속촉 치킨 최적 시간을 지키기 위해서 배달의민족이 하는 일을 주제로 인공지능 추천 배차 알고리즘 설계 방법과 이러한 과정에서 발생한 개발상 고민을 공유했다. 우아한 형제들은 2020년부터 배민 라이더스와 배달의민족 커넥터 등을 대상으로 인공지능 추천 배차제도를 시범 도입했는데 주문이 들어오면 적절한 라이더를 알고리즘이 골라서 배차를 띄우는 방식이다. 배달의민족 추천 배차 알고리즘은 비용, 경로 선택, 라이더 선정, 거리 계산 등의 순서로 이루어진다. 비용은 라이더가 가게까지 도착하는 시간과 음식이 나오는 시간, 라이더가 음식을 픽업하고 손님에게 배달할 때까지 걸리는 시간을 의미하는 것으로 초과시간이 늘어나게 되면 비용도 증가하는 방식이다. 한 건으로 배달을 수행하면 경로가 단순하지만 여러 개의 배달을 수행하면 연산이 복잡해진다. 비가 오는 날에는 라이더가 적지만 배달은 많고 동시에 처리해야 하는 숫자가 증가하게 되는데 이는 라이더 수급에 실패한 부정적인 현상이지만 플랫폼은 비용을 계산해야 한다. 한 명의 라이더가 배달 하나를 추가할 때마다 최적 경로를 선택해야 하는데 이때 모든 라이더 비용을 동시에 계산해야 하며 이를 위한 연산을 최적화하는 방법이 필요하다. 배달의 민족은 이러한 기하급수적인 연산을 처리하는 방법으로 그리드 알고리즘을 선택했다. 그리드 알고리즘은 매 순간 최적으로 생각하는 답을 선택해서 최종 결론을 만드는 방식을 의미하는 것으로 기존에 정한 최적 배달 경로에서 추가되는 배달이 있다면 이를 사이에 추가해 처리할 수 있게 하고 기존의 비용과 새로운 배달로 추가한 비용의 증분 값이 가장 적은 라이더를 선택할 수 있도록 설계했다. 일상에서도 사용하는 그리드 알고리즘에 관해서 살펴보고자 한다.

참고 자료

"치킨 왔습니다" 배민 개발자가 말하는 추천 배차 알고리즘, 김인경, B BLOTER, 2020.12.16.
[NDC 19] 아, 잘 달리는 쿠키 찾으시는구나!, 송주상, THIS IS GAME, 2019.04.25.
박우길, 예제로 배우는 컴퓨터 알고리즘, 계명대학교출판부, 2018, p.125~126
하나몬, 2021, [알고리즘] 탐욕 알고리즘(Greedy Algorithm), 2023년 9월 15일 접속,
https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%83%90%EC%9A%95%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-greedy-algorithm/