그리디

정의

• 현재 상태에서 선택할 수 있는 방법 중 최선의 선택을 하다 보면 전체 문제에 대한 최선의 선택지가 나올 거라고 가정하는 알고리즘

• 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정

특징

• 각 단계에서 선택한 값이 전체를 아우렀을 때 항상 최적의 해를 보장하진 않음
• 그리디로 풀었을 때 최적의 해 도출할 수 있는 문제가 있고, 아닌 문제가 있기에 문제 풀기 전에 그리디로 풀어도 되는지 안되는지 먼저 판단해야 함.

과정

1. 해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해를 선택

2. 적절성 검사 : 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사

3. 해 검사 : 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사
• 전체 문제를 해결하지 못한다면 1번으로 돌아가 같은 과정을 반복

예시

• 내 풀이) k=4200원, 동전=1,5,10,50,100,500,1000,5000,10000,50000
• 4200원보다 보다 작은 수 중 최대값은 1000원이므로
• 1000원짜리 동전으로 최대한 4200원에 가깝게 구성해보기
• 1000원 * 4개 → 남은 돈 : 200원
• 200원보다 작은 수 중 최대값은 100원이므로
• 100원짜리 동전으로 최대한 200원에 가깝게 구성해보기
• 100 * 2개 → 남은 돈 : 0원 (문제 해결!)

• 내 풀이가 그리디인 이유)
• 동전을 최소로 쓰려면 큰 액수의 동전부터 먼저 사용해야 한단 점이 최선이라는 점에 착안해서,
• 현재 남은 금액을 동전으로 채우기 위해 매번 가장 큰 액수의 동전을 고르는 최선의 행동을 함.

• 내 풀이를 그리디 과정에 대입해보자면면)
1. 해 선택 : 현재 남은 금액을 채울 수 있는 가장 큰 액수의 동전 고르기 (1000원)
2. 적절성 검사 : 고른 동전을 몇 개 사용할 지 정하기 (4개)
3. 해 검사 : 현재 남은 금액이 0원인지 확인하기 (200원 남음)
• 전체 문제 해결하지 못했다면 1번부터 다시 반복 (남은 금액 0원 될 때까지 반복)

• 이 문제에 그리디를 쓸 수 있는 이유)
• 동전들이 배수의 형태로 주어지기 때문에
• 200원 2개보단 400원 짜리 1개가 더 의미 있음

• 항상 해가 존재하는 이유) 해가 없다면 예외 처리 해주기
• 1원짜리 동전이 항상 존재해서
• 주어진 동전들로 주어진 금액 k를 못 만드는 경우가 절대 나오지 않기 때문임

코드

💡

전체 코드와 추천 문제는 아래에서 확인하실 수 있습니다.

GitHub - ChooSeoyeon/algorithm: 알고리즘 학습 시 사용한 코드를 모아뒀습니다. 전체 학습 과정에 대한 내용은 아래 링크에서 확인할 수 있습니다.

알고리즘 학습 시 사용한 코드를 모아뒀습니다. 전체 학습 과정에 대한 내용은 아래 링크에서 확인할 수 있습니다. - GitHub - ChooSeoyeon/algorithm: 알고리즘 학습 시 사용한 코드를 모아뒀습니다. 전체 학습 과정에 대한 내용은 아래 링크에서 확인할 수 있습니다.

https://github.com/ChooSeoyeon/algorithm/tree/main