📌 그리디 (이것이 취업을 위한 코딩 테스트다 with python)

📖 01. 그리디 알고리즘 개요

✏️ 문제

✍️ 입력

n = 1260
count = 0

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

for coin in array:
    count += n // coin # n을 doin으로 나눈 몫
    n %= coin

print(count)

💻 출력
6

---

📖 02. 그리디 유형 문제 풀이

01. 1이 될 때까지

✏️ 문제

🕶️ 해설

✍️ 입력

N = 25
K = 3
count = 0

while True:
    if N == 1:
        print("{0}".format(count))
        break

    count += 1

    if N % K == 0:
        N = N // K
    else:
        N -= 1

💻 출력
25 6

• 로그시간 복잡도로 문제를 해결할 수 있다.
  -> 나눌때마다 기하급수적으로 떨어지기 때문에 로그시간 복잡도이다.

02. 곱하기 혹은 더하기

✏️ 문제

• int형의 최댓값이 21억정도이다.
  -> 자료형 int 쓰라고 배려해 준 문제

🕶️ 해설

✍️ 입력

datas = input()

result = int(datas[0])

for i in range(1, len(datas)):
    num = int(datas[i])
    if num <=1 or result <=1:
        result += num
    else:
        result *= num

print(result)

💻 출력
>02984
576

03. 모험가 길드

✏️ 문제

🕶️ 해설

✍️ 입력

n = int(input())
data = list(map(int, input().split()))
data.sort()

count = 0 # 현재 그룹에 포함된 모험가 수 총
result = 0 # 그룹의 수
for i in data: # 공포도를 낮은 것부터 하나씩 확인하며
    count += 1 # 현재 그룹에 해당 모험가를 포함시키자

    if count >= i: # 현재 그룹에 포함된 모함가의 수가 현재의 공포도 이상이라면, 그룹결성
        count = 0 # 현재 그룹에 포함된 모험가의 수 초기화
        result += 1 # 총 그룹의 수 증가시키기

print(result) # 총 그룹의 수 출력

💻 출력
> 5
> 2 3 1 2 2
2

[출처] 이것이 취업을 위한 코딩 테스트다 with 파이썬