[코딩테스트] 그리디 알고리즘(Greedy), 탐욕법

그리디 알고리즘(Greedy) : 탐욕법

그리디 알고리즘이 뜻하는 것은 한 마디로

지금 상황에서, 지금 당장 좋은 것만 고르는 방법이다.

 

문제를 풀기 위한 최소한의 아이디어가 중요하며, 정당성(단순히 가장 좋아 보이는 걸 반복적으로 선택해도 최적의 해를 구할 수 있는가?) 검토 및 분석이 필요하다.

 

사실 일반적으로 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다.

하지만 코딩 테스트에서 대부분의 그리디 문제는 이 그리디 알고리즘으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제된다.

 

그러면 언제 이 그리디 알고리즘으로 구한 값이 최적의 해가 될까?

대표적으로 거스름돈 문제가 있다.(거슬러 주어야 할 동전의 최소 개수를 구하기)

 

문제1 : 거스름돈

가장 큰 화폐 단위부터 돈을 거슬러 주는, 즉 500원->100원->50원->10원짜리 동전을 차례대로 거슬러줄 수 있는 만큼 거슬러 주면 되는 방식이다.

몫은 //, 나머지는 %를 이용해서 구하자.

 

이 방식이 통하는 이유는, 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로, 작은 단위의 동전을 종합한 다른 해가 존재할 수 없기 때문이다.

만일 800원을 거슬러 주어야 하는데 화폐가 500원, 400원, 100원 단위라면 이렇게 가장 큰 화폐 단위부터 거슬러주는 방법이 통하지 않는다.(400원짜리 2개를 주는 게 최적이기 때문)

 

이렇게 문제를 풀기 위해서 최소한의 아이디어를 떠올리고, 이 방법이 정당한지 스스로 검토할 수 있어야 한다.

 

* 시간 복잡도 : 화폐종류만큼 반복되므로 0(K)이다.( K=화폐 종류 수)

 

 

문제 2: 1이 될 때까지 문제

N과 K가 주어질 때, N이 1이 될 때까지 "N에서 1을 빼거나/N을 K로 나누거나" 하는 과정을 수행해야 하는 최소 횟수를 구할 때도 그리디 알고리즘의 활용이 가능하다.

 

*이 때, tip이 있다면

target = (n//k) * k 와 같은 코드를 작성해서,

n이 k로 나누어 떨어지지 않을 때, n을 k로 나눈 몫에 k를 곱하는 것이므로,

가장 가까운 k로 나누어떨어지는 수를 찾을 수 있다.

그러면 그 다음으로

result += (n-target) 으로 1을 몇번 빼야 하는지 계산할 수 있다.

 

이렇게 짜면 로그시간복잡도로 빠르게 문제를 해결할 수 있으므로,이런 tip을 잘 활용해야 한다.

 

 

문제3 : 곱하기 혹은 더하기

어떤 숫자로 이루어진 문자열이 주어지면, 모든 숫자를 곱하거나 더하여 만들 수 있는 가장 큰 수를 구하는 문제.

0이나 1이 나오면(두 수 중 하나라도 1 이하이면) 더하고, 나머지(두 수가 모두 2 이상)는 곱해야 할 것이다.

또한 만들 수 있는 가장 큰 수는 20억 이하의 정수가 되어야 한다는 조건이 종종 주어진다.

이는 프로그래밍 언어에서 int형을 사용하면 약 21억정도까지 값이 형성될 수 있기 때문이다.(파이썬은 ok)

 

 

문제4 : 모험가 길드

N명의 모험가가 있을 때, 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 그룹에 참여해야 여행을 떠날 수 있다고 하자. N명의 모험가의 공포도가 주어졌을 때, 여행을 떠날 수 있는 그룹 수의 최댓값은?

-> 현재 그룹의 모험가의 수가 현재 공포도보다 크거나 같다면 이를 그룹으로 설정.

-> 먼저 오름차순으로 정렬하고, 항상 최소한의 모험가의 수만 오도록 하자.

 

 

코딩테스트 차근차근 준비하기

2022.12.18 - [Data Science] - [코딩테스트] 코딩테스트 및 관련 알고리즘의 개요

2022.12.19 - [Data Science] - [코딩테스트] 파이썬 문법 기초 복습 : 자료형

2022.12.20 - [Data Science] - [코딩테스트] 파이썬 문법 기초 복습 : 입출력부터 자주 쓰이는 라이브러리까지