그리디 & 구현 (시뮬레이션)

Juhee Kim·2024년 7월 24일

파이썬으로 코테 부수기

목록 보기

2/3

참조 유튜브

그리디 알고리즘

개념

➡️ 그리디 알고리즘으로 나온 결과는 19. 그러나 최대값은 21

이처럼 최적의 해를 보장할 수 없을 때가 많음
But,
코딩 테스트에서의 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 경우에 한해 문제 출제됨

예시 문제 1: 거스름 돈

해결 아이디어

최적의 해를 빠르게 구하기 위해서 가장 큰 화폐 단위부터 돈을 거슬러 주기
- N원을 거슬러 줘야 할 때, 가장 먼저 500원으로 거슬러 줄 수 있을 만큼 거슬러 주기
- 이후에 100원, 50원, 10원짜리 동전을 차례대로 거슬러 줄 수 있을 만큼 거슬러 주기

정당성 분석

가장 큰 화폐 단위부터 돈을 거슬러 주는 것이 최적의 해를 보장하는 이유는?
- 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문

만약에 800원을 거슬러 주어야 하는데 화폐 단위가 500원, 400원, 100원이라면?
- 그리디 알고리즘으로는 500x1 + 100x3, 즉 4개를 거슬러줘야 함
- 그러나 최적의 방법은 400x2, 즉 2개

그리디 알고리즘 문제에서는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 함

답안 예시

n = 1260
count = 0

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

for coin in array:
    count += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
    n %= coin
    
print(count)

화폐의 종류가 K개 할 때, 소스코드의 시간 복잡도는 O(K)

이 알고리즘의 시간 복잡도는 거슬러줘야 하는 금액과는 무관하며, 동전의 총 종류에만 영향 받음

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

해결 아이디어

주어진 N에 대하여 최대한 많이 나누기를 수행
- N의 값을 줄일 때 2 이상의 수로 나누는 작업이 1을 빼는 작업보다 수를 훨씬 많이 줄일 수 있음

우선 N이 K로 나누어 떨어지면 나누고, 그렇지 않으면 1씩 빼며 나누어 떨어지는 수로 만들어 나누기

답안 예시

# N, K을 공백을 기준으로 구분하여 입력 받기
n, k = map(int, input().split())

result = 0

while True:
	#N이 K로 나누어 떨어지는 수가 될 때까지 빼기
	target = (n // k) * k # N이 K로 나누어 떨어지지 않을 경우 N과 가장 가까운, K로 나누어 떨어지는 수 구하기
	result += (n - target) # 1을 빼는 연산 수행의 횟수 구하기
	n = target
    
	# N이 K보다 작을 때 (더 이상 나눌 수 없을 때) 반복문 탈출
	if n < k:
		break
        
	# K로 나누기
	result += 1
	n //= k
    
# 마지막으로 남은 수에 대하여 1씩 빼기
result += (n - 1)
print (result)

반복문 안에서 조건문을 사용해 뺄지, 나눌지 정할 수도 있음. O(n)

그러나 위 예시코드는 반복문을 거칠 떄마다 나눗셈 수행하므로 기하급수적으로 빨라짐. O(logn)

구현 알고리즘

예시 문제: 왕실의 나이트

그리디 aka 구현 aka 시뮬레이션 aka 완전 탐색 문제

답안 예시

# 현재 나이트의 위치 입력받기
pos = input()
row = int(pos[1])
col = int(ord(pos[0]) - ord('a')) + 1

# 나이트가 이동할 수 있는 8가지 방향 정의
steps = [(-2, -1), (-2, 1), (2, -1), (2, 1), (1, -2), (1, 2), (-1, 2), (-1, -2)]

# 8가지 방향에 대하여 각 위치로 이동이 가능한지 확인
result = 0
for step in steps:
  # 이동하고자 하는 위치 확인
  next_row = row + step[0]
  next_col = col + step[1]
  # 해당 위치로 이동이 가능하다면 카운트 증가
  if next_row < 1 or next_row > 8 or next_col < 1 or next_col > 8:
    continue
  result += 1 

print(result)