이것이코딩테스트다 | Ch03 그리디

Date | 2021.05.19 / 2021.07.12
Review | 문제들이 간단해서 금방 풀었다. 책에서 제시한 코드랑 다르게 코딩한 부분도 많아서 비교를 많이 했다. 파이썬으로 코딩테스트를 풀 때 필요한 몇 가지 기본적인 함수 (ex. map)도 정리했는데 유용했다.

---

1️⃣ 당장 좋은 것만 선택하는 그리디

#당장 좋은 것만 선택하는 그리디
#그리디 알고리즘 (Greedy)

## 특징
매 순간 가장 좋아 보이는 것을 선택
현재의 선택이 나중에 미칠 영향에 대해서 고려하지 않음

## 키워드
가장 큰 순서대로
가장 작은 순서대로

n = 1260
count = 0

# 큰 단위 화폐부터 차례대로 배열로 생성
coin_types = [500, 100, 50, 10]

for coin in coin_types:
  count = count + n // coin
  n = n % coin

print(count)

 

2️⃣ [실전문제] 큰 수의 법칙

# N, M, K 입력받기
n, m, k = map(int, input().split())

# N개의 수 입력받기
data = list(map(int, input().split()))

# 가장 큰 값과 그 다음으로 큰 값 구하기
data.sort()
first = data[n-1] # 가장 큰 값
second = data[n-2] # 두번째로 큰 값

# 반복한계 기준
full = 0
result = 0

for i in range(m) :
  if(full==k):
    full=0
    result += second
  else:
    full += 1
    result += first

print(result)

 

3️⃣ [실전문제] 숫자 카드 게임

# N, M 입력받기
n, m = map(int, input().split())

result = 1

for i in range(n):
  data = list(map(int, input().split())) # 카드 값 입력받기
  data.sort()
  min = data[0]
  if(result < min):
    result = min

print(result)

 

4️⃣ [실전문제] 1이 될 때까지

# N, K 입력받기
n, k = map(int, input().split())

result = 0

while(n != 1):
  if(n % k != 0): # n이 k로 나누어 떨어지지 않으면 - 1씩빼기
    n -= k
    result += 1
  else: # n이 k로 나누어 떨어지면 - k로 나누기
    n = n/k
    result += 1

print(result)