[알고리즘] 그리디 알고리즘(Greedy Algorithm)

코딩테스트 역량 강화 교육(거점형 특화 프로그램)이라는 프로그램에 참여해 공부한 내용입니다.

• IT 직무로 취업을 희망하는 지원자들이 코딩테스트를 통과할 수 있는 알고리즘을 활용한 프로그래밍 교육이며, PCCP 자격증 취득이 목표인 프로그램
• 상세 설명 - 수원대학교(대학일자리 플러스센터)

---

그리디 알고리즘(Greedy Algorithm)

탐욕 알고리즘이라고도 하며, 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최고의 상황만 을 쫓아 최종적인 해답에 도달하는 방식

---

예시

일렬로 놓여 있는 숫자 카드에서 왼쪽 맨 끝과 오른쪽 맨 끝 카드 중 하나를 가져가는 방식으로 4개의 카드를 가져갔을 때 가져간 카드의 숫자 합의 최댓값은?

• [2, 3, 7, 1, 2, 1, 5]
• 답 : 5 + 2 + 3 + 7 = 17

이렇게 왼쪽 맨 끝과 오른쪽 맨 큰 가드 중 하나를 가져가는 방식을 그리디 알고리즘으로 풀이하면
왼쪽 맨 끝과 오른쪽 맨 끝 중 큰 카드를 계속 고르면 된다.

또한, 그리디 알고리즘을 적용했을 때 가장 좋은 해답인지 아닌지 확인하는 반례를 찾는게 가장 중요하다.

---

위와 같이 그리디 알고리즘을 학습한 후 풀이한 문제는 아래와 같다.

• 최대 사과의 개수
• 선 긋기