그리디(Greedy) 알고리즘

 

안녕하세요.

 

코딩테스트에서 사용하는 알고리즘에 대해서 하나하나 알아보려고 합니다.

 

그리디 알고리즘 유형의 문제는 다양하기 때문에 암기보다는 많이 문제를 풀어보면서 훈련을 해야합니다.

 

그리디 알고리즘이란?

 

그리디 알고리즘은 단순하지만 강력한 문제 해결 방법입니다.

'매 순간 가장 좋아보이는 것을 선택'하는 알고리즘 입니다.

 

예제1. 동전 거스름돈 문제 - 가장 큰 화폐의 단위부터 돈을 거슬러주는 것이 포인트

 

 

그리디 알고리즘의 정당성

 

그리디 알고리즘을 사용할 때에는 그 해법이 정당한지 확인해야합니다.

 

 

큰 수의 법칙

다양한 수로 이루어진 배열이 있을때, 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙.

단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번 초과하여 더해질 수 없다.

 

해설 포인트 🔥

 

- 반복되는 수열에 대해서 파악이 중요

- M을 K+1로 나누면 반복되는 수열의 반복횟수를 확인 가능

-반복되는 수열의 반복횟수에 K를 곱해주면 가장 큰수가 반복되는 횟수(count)를 확인 가능

- M/K+1이 정수로 나누어지지 않을때엔 int(M / (K+1)) * K + M % (K+1) 로 확인 가능

- (가장 큰수가 반복되는 횟수 * 가장 큰수) + ((전체횟수-가장큰수 반복되는 횟수)* 두번째로 큰수) 수식으로 답안 해결

 

 

숫자 카드 게임

 

각 행마다 가장 작은 수를 찾은 뒤에 그 수 중에서 가장 큰 수를 찾는 문제입니다.

반복문과 min 함수를 통해서 쉽게 답을 구할 수 있습니다.

 

1이 될 때까지

 

어떠한 수 N이 1이 될때까지

1. N을 1로 빼기

2. N을 K로 나눈다.

 

위의 두가지의 방법을 통하여 해당과정을 수행하는 최소 횟수를 구하는 문제입니다.

 

해설 포인트 🔥

 

- 1로 빼는 방법과 K로 나누는 방법이 순차적으로 일어날 필요가 없고, 최대한 K로 나누는 방법이 많이 선택되어야 최소 횟수를 구할 수 있습니다.

- while문과 if문을 통해서 문제를 해결할 수 있습니다.

- 연산 시간을 줄이기 위해서는 N이 K의 배수가 될때까지 1을 빼주는 과정을 묶어서 한번에 횟수를 더해주면 됩니다.