주의! 이글은 개인 공부 목적으로 작성된 포스팅입니다. 잘못된 내용이 있을 수 있음을 주의해주세요.
🧐그리디 알고리즘?
오늘은 그리디 알고리즘에 대해 알아보려 한다. 그리디 알고리즘은 뭘 까?
다른말로 탐욕 알고리즘이라고도 한다.
핵심 내용은 미래를 고려하는 게 아닌 현재 가장 최적의 해를 구하는 알고리즘이다.
🥇 동전 개수 구하기
가장 쉬운 예로 동전 개수 구하기 문제가있다.
뒤에서 백준 문제를 예를 들어 설명하겠지만 우선 이론적 내용을 살펴보자.
A 마트에 간 훈이는 사장님에게 동전으로 물건을 계산해야 했다.
하지만 사장님은 지폐를 좋아하셔서 동전으로 물건을 계산한다면 최소한의 동전만 받고 싶어 하신다.
만약, 훈이가 최적의 동전 개수를 주지 않고 임의대로 준다면 사장님에게 엄청 혼날 것이다.
이때 물건 가격은 1000원이며, 훈이가 보유한 동전의 종류는 100원 / 10원 / 1원이다.
훈이가 사장님에게 드려야 할 최적의 동전의 금액별 총 개수는?
정답 : 100원 10개 / 10원 0개 / 1원 0개
우리는 문제를 보며 정답을 금방 떠올렸을 거다. 핵심은 뭐였을까?
바로, 큰 수부터 훈이가 지급해야 할 금액을 하나씩 빼본 거다.
누군가는 나누기를 사용해 몫과 나머지로 구하는 방법을 사용했을 거다.
하지만, 여기서는 나누기, 더하기가 중요한 게 아니다. 큰 거에서 작은 것을 중점으로 문제를 풀었다는 거다.
이처럼 그리디 알고리즘은 우리가 방금 떠올린 내용과 같이 최적의 해를 지금 당장 구할 수 있는 알고리즘이다.
👀 그럼 항상 최적의 해를 보장하나요?
앞에 기록한 내용 중 "미래를 고려하지 않고"라는 말이 있다. 이는 미래의 경우의 수가 연관될 때 해당 알고리즘은 최적의 해를 보장하지 않는다.
아래 예를 통해 알아보자.
짱구는 철수와 300원을 최소 동전 개수로 만들기 놀이했다. 사용할 수 있는 동전은 250원 / 100원 / 10원이다.
이때 300원을 만드는 데 사용되는 동전의 금액과 개수를 구하시오.
만약, 우리가 위에서 배운 방식으로 문제를 푼다면 250원 1개와 / 10원 5개를 써서 총 6개의 동전 개수가 나올 거다.
하지만, 100원을 3개 써서 총 3개의 동전으로 300원을 만들 수 있다.
이는 250원이라는 앞의 선택이 100원을 선택할 수 없게 만들어 10원 5개의 선택지를 만든 것이다.
만약, 앞에 250원을 선택하지 않고, 100원을 선택했다면 3개의 동전으로 금액을 만들었을 것이다.
이처럼 그리디 알고리즘은 지금의 선택이 위와 같이 미래에 연관되는 순간 최적의 해는 보장되지 않는다.
💡 어디에 쓰여요?
간단하게 그리디 알고리즘이 어디에 쓰이는지 알아보자.
그리디 알고리즘은 어느 정도 오차 범위가 허용된 최적의 해를 구할 때 빛이 나는 알고리즘이다.
예를 들어 내비게이션의 최단 경로를 생각해보자.
만약 목적지와 출발지의 모든 경로를 고려하여 최적의 경로를 뽑으려면 엄청난 시간이 걸릴 것이다.
하지만 우리는 경로 탐색을 시작하면 빠른 시간안에 정보를 받을 수 있다.
이때 사용되는 게 그리디 알고리즘이다. 물론 많은 알고리즘이 사용되겠지만 지금은 그리디 알고리즘에 집중해보자.
반드시 계산한 시간 안에 도착해야 한다는 조건이 없고 "예상 도착 시간" 이라는 말이 존재하기 때문에 어느 정도 오차가 인정된다.
고로 지금 상황을 고려하여 최적의 경로를 찾아 안내하면 위와 같이 빠른 시간안에 최적의 경로를 받을 수 있는 것이다.
🔥 연습해보자!
백준 2720번 문제를 풀어보자.
링크 : https://www.acmicpc.net/problem/2720
⚙️ 정답
fun main(args: Array<String>) {
var count = readln().toInt() // 입력 카운트를 저장한 변수
for (i in 0 until count){
var c = 0 // 쿼터 갯수
var d = 0 // 다임 갯수
var n = 0 // 니켈 갯수
var p = 0 // 페니 갯수
var total = 0 //금액을 더할 변수
var line = readln().toInt() // 금액을 입력받아 저장하는 변수
while (line != total){
if(total + 25 <= line){ // 가장 큰 금액인 25부터 더해보고 입력받은 금액과 비교해본다.
c ++
total += 25
}else if(total + 10 <= line){ // 위와 동
d ++
total += 10
}else if(total + 5 <= line){ // 위와 동
n ++
total += 5
}else if(total + 1 <= line){ // 위와 동
p ++
total += 1
}
}
println("$c $d $n $p") //최종적으로 동전 갯수가 구해지면 출력한다.
}
}
오늘은 여기까지 하면 좋을 것 같다.
다음 시간에는 BFS / DFS 알고리즘을 기록해볼까 한다.
💬 소중한 시간 사용해서 글 읽어주셔 감사합니다. 틀린 내용이 있다면 언제든지 댓글로 남겨주세요.
