[이것이 취업을 위한 코딩 테스트다 with 파이썬] 2-1강(그리디 알고리즘, 예제)

그리디 알고리즘

 

• 그리디 알고리즘(탐욕법)은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다.
• 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.
• 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다.
• 그리디 해법은 그 정당성 분석이 중요하다. 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토한다.

5 + 7 + 9 = 21(최적의 해)

 

5 + 10 + 4 = 19

• 그리디 알고리즘은 위와 같이 단순히 매 상황에서 가장 큰 값만 고르는 방식어서 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다.
• 하지만 코딩 테스트에서의 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제된다.

 

n = 1260
count = 0

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

for coin in coin_types:
  count += n // coin #해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
  # count에 n을 coin으로 나눈 몫을 담는다. 
  # 즉, 현재 남아있는 돈을 현재의 동전으로 최대한 많이 거슬로 줄 수 있도록 하며
  # 그 거스름돈의 개수를 더하는 것이다.
  n %= coin
  # n은 남아있는 동전보다 작아져야 하기 때문에 n을 coin으로 나눈 나머지 값이 될 수 있도록 한다.
  
print(count)
# 6

화폐의 종류만큼 반복을 수행해야하기 때문에 화폐의 종류가 K라고 할 때 위의 코드의 시간 복잡도는 O(K)이다.

이 알고리즘의 시간 복잡도는 동전의 총 종류에만 영향을 받고, 거슬러 줘야하는 금액의 크기와는 무관하다.

최적의 해는 2개의 동전(400원 + 400원)을 거슬러 주는 것이다.

거스름돈 문제를 보고 '만약 10원짜리로만 모두 거슬러 주면 어떻게 되지?

10원짜리로만 모두 거슬러 주면 최적의 해를 구할 수 없겠구나!'라고 문제점을 인식하고,

'거스름돈 문제에서는 큰 단위가 항상 작은 단위의 배수 형태이므로,

이렇게 하면 항상 최적의 해를 보장할 수 있겠구나!'까지 떠올릴 수 있어야 한다. 

 

c++

java

---

1이 될 때까지

# 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)

 

---

곱하기 혹은 더하기

정수 데이터를 위해 기본 int형을 사용할 경우 약 21억까지 값이 형성될 수 있기 때문에 20억 이하로 최댓값 명시

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 = 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) # 총 그룹의 수 출력