[알고리즘] 그리디 알고리즘

yesjuhee·2023년 1월 10일

ps 알고리즘

코테공부

목록 보기

2/12

그리디 알고리즘이란

이코테 강의를 통해 공부했습니다!!

그리디 알고리즘(탐욕법)은 현재 상황에서 지금 당장 좋은 것만 고르는 방법
일반적인 그리디 알고리즘 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구함
그리디 해법은 그 정당성을 분석하는 것이 중요함
- 단순히 가장 좋아보이는 것을 반복적으로 선택해도 최적의 해를 구할수 있는가? → 그리디 알고리즘 이용
일반적인 상황에서 그리디 알고리즘이 최적의 해를 보장할 수 없을 때가 많음
하지만 코딩 테스트에서 그리디 알고리즘으로 분류가 되는 문제는 탐욕법을 이용하면 최적의 해로 풀리도록 설계가 되어있음

그리디 알고리즘 예제

1이 될 때까지

처음 생각한 풀이는 아래와 같음

n이 k로 나누어 떨어지는지 체크해서 나누어 떨어지는 경우 나누고, 아닌 경우 1씩 빼는 풀이

# 입력
n, k = map(int, input().split())

result = 0

while n > 1:
    if n % k == 0: 
        # n이 k로 나누어 떨어지는 경우
        n //= k
        result += 1
    else:
        # n이 k로 나누어 떨어지지 않는 경우
        n -= 1
        result += 1

print(result)

강의의 해답에서 시간 복잡도를 줄이는 방식이 인상 깊었음

target = (n // k) * k → n이하의 가장 큰 k 배수 구하기

1씩 줄이는걸 반복해서 구하는게 아니라 한번에 구함

# 입력
n, k = map(int, input().split())

result = 0

while True:
    target = (n // k) * k  # n이하의 n과 가장 가까운 k의 배수
    result += (n - target)
    n = target
    if n < k:
        break
    result += 1
    n //= k

result += (n - 1)
print(result)

곱하기 혹은 더하기

# 곱하기 혹은 더하기

# 입력
string = input()

max = int(string[0])

for i in range(1, len(string)):
    num = int(string[i])
    # 둘 중 하나가 0인 경우 더하기
    if max * num == 0:
        max += num
    # 둘 중 하나가 1인 경우 더하기
    elif max == 1 or num == 1:
        max += num
    # 이외의 모든 경우는 빼기
    else:
        max *= num

print(max)

0인 경우를 재치있게 확인했다고 생각했는데...
- 해답을 보니까 그냥 1 이하로 체크하면 됐음!

모험가 길드

모험가 그룹을 공포도가 높은 사람부터 짤지, 낮은 사람부터 짤지 고민을 해봤음 (예시가 단순해서 생각하기가 쉽지 않음)
- 처음 생각은 낮은 사람부터 해야한다고 판단했는데 오히려 예시 (2 3 1 2 2)에서 그룹을 (1 2 3) (2 2) 이렇게 짜니까 의아했음…
(1 1 3)인 경우 낮은 사람부터 구성하는게 맞음
- 낮은 사람부터 구성 → (1) (1)
- 높은 사람부터 구성 → (3 1 1)
그냥 해답을 먼저 보기로 함~!
내가 잘못 생각했음. 예시가 헷갈리게 해놨네!!! 낮은 사람부터 구성하는게 맞음

# 모험가 길드

n = int(input())
data = list(map(int, input().split()))
data.sort()

result = 0
count = 0

for i in data:
    count += 1
    if count >= i:  # 현재 그룹에 포함된 모험가의 수가 현재의 공포도 이상이라면 그룹 결성
        result += 1
        count = 0

print(result)

그리디 문제 추가 풀이 (백준)

추가 공부를 위해 백준에서 그리디 유형 문제를 선별하여 풀어보았다.

5585번 : 거스름돈

5585번: 거스름돈

솔루션 코드

# 거스름돈

coins = [500, 100, 50, 10, 5, 1]  # 거스름돈 리스트
count = 0

price = int(input())
change = 1000 - price

for coin in coins:
    # while문 대신 몫과 나머지를 이용
    count += change // coin
    change = change % coin

print(count)

2389번 : 설탕 배달

2839번: 설탕 배달

문제 파악

이 문제는 설탕 n킬로그램을 5킬로그램 비닐 봉지 몇개와 3킬로그램 비닐 봉지 몇개로 구성할 수 있는지, 봉지의 최소 개수를 구하는 문제이다.
즉 5kg 비닐 봉지의 개수를 a, 3kg 봉지의 개수를 b라고 한다면 $n = 5 * a + 3 * b$ 식을 만족하는 정수 a와 b의 합의 최소값을 구해야 한다.
이때 a의 범위는 $0\le a \le \lfloor{n\over5}\rfloor$ 이고, b의 범위는 $0\le b \le \lfloor{n\over3}\rfloor$ 이다.
만약 이 범위 내에서 정수인 a와 b 값을 찾을 수 없다면 -1을 출력해야 한다.
n = 15인 경우 a와 b의 해로 (3, 0), (0, 5)의 두 가지 경우가 나오는데 이 경우 합이 최소인 (3, 0)이 답이다.
즉 적절한 해를 구하기 위해서는 a가 최대인 경우부터 위의 방정식을 만족하는 a와 b의 해를 찾아야 한다.

솔루션 흐름

$n = 5 * a + 3 * b$

n 입력
a = n // 5 계산
a가 해당 값일 때 나머지 값이 3으로 나누어 떨어지는지 확인
1. 나누어 떨어지면 → 최적의 값 찾음! print하고 프로그램 종료
2. 나누어 떨어지지 않으면 → 그다음 값 확인, a를 1 줄이고 3번 반복
a가 0까지 갔는데 프로그램이 종료되지 않았다면 n은 3과 5의 배수의 합으로 계산될 수 없는 수라는 의미 → -1 출력

솔루션 코드

# 설탕 배달

n = int(input())

# n = 5 * a + 3 * b
a = n // 5

while a >= 0:
    gap = n - a * 5
    if gap % 3 == 0:
        print(a + gap//3)
        exit()
    else:
        a -= 1

print(-1)