[알고리즘/그리디] 각 상황에서 최적인 방법 선택, 예시 문제(거스름돈, 1이 될 때까지, 곱하기 혹은 더하기, 모험가 길드)

들어가며

Q. 노드에서 가장 합이 높은 방법을 선택해 보세요.

선택 기준: 없음 ⇒ 5+7+9 = 합 21이 나오는 방법 선택 ❘ 선택 기준: 각 상황에서 가장 높은 수 ⇒ 5+10+4 = 합 19가 나오는 방법 선택

 

그리디 = 각 상황에서 최적인 방법 선택

💡 즉, 현재 상황에서 지금 당장 좋은 방법 pick!

• 핵심: 선택에 대한 정당성 분석
  • 문제에서 요구하는 최적의 해를 진짜 구할 수 있는지 검토하는 것
    (∴ 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장하지 않음)
  • However! 그리디 문제에서는 그리디 알고리즘을 써야 최적의 해가 나옴
• 요약: 선택 → 정당성 → 해답 검토

 

[예시] 거스름돈 문제

• 거스름돈 문제
  • 가장 큰 화폐 단위부터 돈을 거슬러 주면 됨
  • 500원 → 100원 → 50원 → 10원
  • Why? 동전 중 큰 단위가 항상 작은 단위의 배수이므로, 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문
    • 500 == 1005 == 5010 == 10*50
    • 큰 단위가 작은 단위의 배수가 아니라면 이와 같은 최적의 해를 보장할 수 없음
    • if 거스름돈 800원, 화폐단위 500원, 400원, 100원이라면?
      • 최적의 해: 400원 2개 (기존의 500원 1개, 100원 3개가 아님)
• 답안 예시

n = 1250
count = 0

# 큰 단위 화폐부터 차례대로 확인하기
array = [500, 100, 50, 10]

for coin in array:
	count += n // coin # 1250 // 500 = 2를 count에 저장 -> 100원, 50원, 10원
	n %= coin # 1250 % 500 = 250을 거스름돈에 저장 -> 100원, 50원, 10원
print(count)

• 풀이방법 분석
  • 화폐의 종류(K)만큼만 반복 ⇒ 소스코드의 시간 복잡도: O(K)
  • 동전의 총 종류에만 영향을 받음

 

[문제] 1이 될 때까지

• 문제 설명
  • 어떠한 수 N이 1이 될 때까지 다음 두 과정 중 하나를 반복적으로 선택하여 수행한다.
  • 단, 두번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있다.
    1. N - 1
    2. N / K
  • 예를 들어 N이 17, K가 4일 경우⇒ 전체 과정에서 실행한 횟수: 3
  • (1) N - 1 = 16 → (2) N / K = 4 → (3) N/ K = 1
  • N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하세요.
• 조건
  • 난이도: 下 | 풀이 시간: 15분 | 시간제한: 2초 | 메모리 제한: 128KB
  • 입력 조건: 첫째 줄에 N(1 <= N <= 100,000)과 K(2 <= K <= 100,000)가 공백을 기준으로 하여 각각 자연수로 주어집니다.
  • 출력 조건: 첫째 줄 N이 1이 될 때까지, 1번 혹은 2번의 과정을 수행, 횟수 최솟값
• 해결방법
  • 주어진 N에 대하여 최대한 많이 나누기를 수행할 것
  • 검증: 이것이 최적의 해를 항상 보장할 수 있는가?
    • K가 2 이상이기만 하면, K로 나누는 것이 1을 빼는 것보다 항상 빠르게 N을 줄일 수 있을 것
• 답안
  • 내가 생각한 것
    • n이 1이 될 때까지 반복하기
    • k로 나눌 수 있으면 나누고, 그렇지 않으면 1씩 빼는 방식

      시간 복잡도
      n을 매번 k로 나눌 수 있을 때(한 번 나누기)	O(1)
      n을 k로 나눌 수 없을 때(한 번 빼기)	O(1)
      최악의 경우(n이 될 때까지 1씩 빼기)	O(n)

    def solution(n, k):
        count = 0
        while(n != 1):
            if n % k == 0:
                n /= k
                count += 1
            else:
                n -= 1
                count += 1
        return count
    

  • 동빈나 예시
    • n이 k로 나누어 떨어질 때까지 한 번에 빼고 → 그 다음에 k로 나누기
      

      시간복잡도
      n이 k로 나누어 떨어질 때까지 빼는 연산	O(log k(n))
      n을 k로 나누는 연산	O(log k(n))

      # n, k를 공백으로 구분하여 입력 받기
      n, k = map(int(input().split())
      
      result = 0
      
      while True:
      	# n이 k로 나누어 떨어지는 수가 될 때까지 빼기
      	target = (n // k) * k
      	result += (n - target)
      	n = target
      	
      	# n이 k보다 작을 때 반복문 탈출
      	if n < k:
      		break
      	
      	# k로 나누기
      	result += 1
      	n //= k
      
      # 마지막으로 남은 수에 대하여 1씩 빼기
      result += (n-1)
      print(result)
      

[문제] 곱하기 혹은 더하기

• 문제 설명
  • 각 자리가 숫자로만 이루어진 문자열 S
  • 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 ‘x’ 혹은 ‘+’ 연산을 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 작성하세요.
  • 단, +보다 x를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽부터 순서대로 이루어진다고 가정합니다.
• 조건
  • 난이도: 下 | 풀이시간: 30분 | 시간제한: 1초 | 메모리제한: 128MB | 기출: Facebook 인터뷰
  • 입력조건: 첫째 줄에 여러 개의 숫자로 구성된 하나의 문자열 S가 주어집니다. (1 ≤ S의 길이 ≤ 20)
  • 출력조건: 첫째 줄에 만들어질 수 있는 가장 큰 수를 출력합니다.
• 답안
  • 내가 생각한 것
    • s의 길이만큼 반복 → i가 0이면 +, 0이 아니면 *
    • result의 초기값을 0으로 하면 모든 곱의 결과가 0이 되기 때문에 1로 하고, 마지막에 1을 뺌
    • [fail] 정당성 검토 1인 경우에도 더하기가 더 유리함
    
    

    시간복잡도
    문자열의 길이만큼 한번의 루프 수행	O(n)

  s = input()
  result = 1
  for i in s:
      if i == '0': # or i == '1' 추가 필요
          result += int(i)
      else:
          result *= int(i)
  print(result-1)
  

  • 동빈나 예시
    • 0 혹은 1인 경우, 곱하기보다 더하기를 수행하는 것이 효율적임
    
    

    시간복잡도
    문자열의 길이만큼 한번의 루프 수행	O(n)

  data = input()
  
  # 첫 번째 문자를 숫자로 변경하여 대입
  result = int(data[0])
  
  for i in range(1, len(data)):
  	# 두 수 중 하나라도 '0' 혹은 '1'인 경우, 더하기 연산 수행
  	num = int(data[i])
  	if num <= 1 or result <= 1
  		result += num
  	else:
  		result *= num
  print(result)
  

 

[문제] 모험가 길드

• 문제 설명
  • 모험가 길드에서는 N명의 모험가를 대상으로 ‘공포도’를 측정했는데, ‘공포도’가 높은 모험가는 쉽게 공포를 느껴 위험 상황에서 제대로 대처할 능력이 떨어진다.
  • 모험가 길드장인 동빈이는 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했다.
  • 동빈이는 최대 몇 명의 모험가 그룹을 만들 수 있을까?
  • N명의 모험가에 대한 정보가 주어졌을 때, 여행을 떠날 수 있는 그룹 수의 최댓값을 구하는 프로그램을 작성하세요.
• 조건
  • 난이도: 下 | 풀이시간: 30분 | 시간제한: 1초 | 메모리제한: 128MB | 기출: 핵심유형
  • 입력조건
    • 첫째 줄에 모험가의 수 N이 주어집니다.(1 ≤ N ≤ 100,000)
    • 둘째 줄에 각 모험가의 공포도의 값을 N 이하의 자연수로 주어지며, 각 자연수는 공백으로 구분합니다.
  • 출력 조건: 여행을 떠날 수 있는 그룹 수의 최댓값을 출력합니다.
• 답안
  • 내가 생각한 것
    • 처음 생각: 공포도가 전체 모험가의 수보다 높은 애는 없애고, 나머지 애들끼리 조를 짜자 근데 나머지 애들끼리는… 음….
    • 어떻게 짜야할지 모르겠음. 망함.

    # 모험가 길드
    n = int(input("모험가의 수: "))
    fear = list(map(int, input("각 모험가의 공포도 값: ").split()))
    count = 0
    fear.sort()
    
    # 공포도 값이 모험가의 수를 뛰어넘는 경우 해당 인원은 팀에서 제외
    while (n!=0):
        if sum(fear) > n:
            fear.pop()
        else:
    	    # 포기
    

  • 동빈나 예시
    • 오름차순 정렬 → 공포도가 가장 낮은 모험가부터 하나씩 확인
    • 앞에서부터 공포도를 하나씩 확인하여 ‘현재 그룹에 포함된 모험가의 수’ ≥ 현재 확인하고 있는 공포도’보다 크거나 같다면 이를 그룹으로 설정
    • 공포도가 오름차순으로 정렬되어 있기 때문에, 항상 최소한의 모험가의 수만 포함하여 그룹을 결성하게 됨

    # 모험가 길드
    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) # 총 그룹 수 출력
    

---

참고자료

https://www.youtube.com/watch?si=m5TNrlxBJAuj58d0&v=2zjoKjt97vQ&feature=youtu.be