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

이 글은 비전공자 취준생이 개인적인 공부를 위해 작성한 글입니다.

자세한 내용을 원하실 경우 https://yurimac.tistory.com/30, 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/ 이곳을 방문해주시기 바랍니다.

이글의 출처는 위의 링크입니다.

그리디 알고리즘

현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미합니다.

최적 해에 가까운 값을 구할 때 사용합니다.

매 순간마다 최적의 방법을 선택하여 값을 구하지만 결과적으로 최적 해라는 보장은 없습니다.

합이 가장 큰 값을 구해야하는 예제에서

다음 그림을 그리디 알고리즘으로 풀면 13 + 11 = 24 라는 값이 도출됩니다.

하지만 실제로는 7 + 100 = 107이 나올 수 있는 최대값입니다.

이렇게 그리디 알고리즘은 최적해라는 보장이 없습니다.

동전과 거스름돈 예시

물건 가격이 4,040원이 나왔다.

손님이 계산을 하기 위해 5,000원을 내밀며, 거스름돈은 동전의 개수를 최소한으로 하여 거슬러 달라고 하였다.

 

그리디 알고리즘의 문제해결과정 적용

1. 선택 절차
- 거스름돈의 동전 개수를 줄이기 위해 현재 가장 가치가 높은 동전을 우선 선택한다.

2. 적절성 검사
- 1번 과정을 통해 선택된 동전들의 합이 거슬러줄 금액을 초과하는지 검사한다.
- 초과하면 가장 마지막에 선택한 동전을 삭제하고, 1번으로 돌아가 한 단계 작은 동전을 선택한다.

3. 해답 검사
- 선택된 동전들의 합이 거슬러 줄 금액과 일치하는 지 검사한다.
- 액수가 부족하면 1번 과정부터 다시 반복한다.