알고리즘 동아리 3주차 수업
이번 발표 준비는 나였다
발표 자료는 이것이 코딩테스트다 책과, 코드잇 알고리즘 수업을 참고했다.
개념
코딩 테스트에서 그리디 알고리즘 문제들에 당황하지 않으려면 많은 유형을 풀어보는 것이 필요할 것 같다.
그리디 알고리즘을 이용하는것이 좋은 풀이이기 위해선 최적 부분 구조와, 탐욕적 선택 속성을 모두 만족해야 한다.
탐욕적 선택 속성은 직관적이고 간단한데, 최적 부분 구조가 처음엔 와닿지 않았다.
제일 이해를 도운 예시는 길찾기를 예로 들은 문제였다.
A에서 C까지 최대한 빠르게 가야 할 때,
A에서 B까지 가는 제일 빠른 길 + B에서 C까지 가는 제일 빠른 길 = A에서 C까지 가는 제일 빠른 길
이런식으로 원 문제에 대한 부분 문제들이 최적의 답의 구조로 되어있는 걸 말한다.
내가 이해한 방법은, 탐욕적 선택 속성은 원래 후에 어떨지는 고려하지 않고, 현재의 탐욕적인 선택만 고르는 것인데, 최적 부분 구조를 성립하려면 내가 그냥 최종으로 가는 단계마다 최적의 선택을 했더니, 그게 최종 문제의 최적의 선택으로 갔다~ 라고 받아들였다.
예시 1. 거스름돈
최대한 적은 동전을 사용해서 돈 거슬러 주기 : 1260원
n = 1260
count = 0
coin_types = [500, 100, 50, 10]
for coin in coin_types:
count += n//coin
n %= coin
print(count)예시 2. 최대 곱 구하기
문제
여럿이서 카드 게임을 하고 있는데, 각 플레이어는 3장의 카드를 들고 있습니다.
한 사람당 카드를 하나씩 뽑아서 모두 곱했을 때 가능한 최대 곱을 구하시오.접근 방법
1. 함수 max_product : 한 사람당 카드를 하나씩 뽑아서 모두 곱했을 때 가능한 최대 곱을 리턴
2. 탐욕적 선택 : 3장의 카드 중 가장 큰 값을 선택
def max_product(card_lists):
product = 1 #곱 저장 변수
for i in card_lists: #플레이어들의 카드 리스트 돌기
product = product * max(i) # 최댓값을 곱함
return product
# 테스트
test_cards1 = [[1, 6, 5], [4, 2, 3]]
print(max_product(test_cards1))
test_cards2 = [[9, 7, 8], [9, 2, 3], [9, 8, 1], [2, 8, 3], [1, 3, 6], [7, 7, 4]]
print(max_product(test_cards2))예시 3. 1이 될 때가지
문제
어떤 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택해 수행한다. 두 과정을 수행해야 하는 횟수의 최솟값을 출력해라.
단 두 번째 연산은 N이 K로 나누어질 때만 선택할 수 있다.
1. N에서 1을 뺀다
2. N을 K로 나눈다
입력 조건 : 첫째 줄에 N과 K가 공백으로 구분되며 각각 자연수로 주어진다. N>=K
출력 조건 : 첫째 줄에 N이 1이 될때까지 반복한 최소 횟수를 출력한다.접근 방법
탐욕적 기준 : 나누는 것이 더 수를 빠르게 작게 만드니, 나눌 수 있으면 나누고, 그렇지 않으면 1을 감소하자.
n, k = map(int, input().split())
result = 0
# N이 K이상이라면 K로 계속 나누기
while n >= k:
# N이 K로 나누어 떨어지지 않는다면 N에서 1씩 빼기
while n%k != 0:
n -=1
result += 1
# K로 나누기
n //= k
result += 1
# 마지막으로 남은 수에 대하여 1씩 빼기
while n > 1:
n -= 1
result += 1
print(result)
그리디 알고리즘 추천 문제
백준 11399, 1931, 2217번
