[알고리즘] 그리디 알고리즘

 

 

 

 

교재 : "이것이 취업을 위한 코딩테스트다"

 

 

그리디 알고리즘¶

• 현재 상황에서 가장 좋아 보이는 것만 선택하는 알고리즘
• 정확한 답 도출보단 그럴싸한 답을 도출하는데 도움됨
• 그리디 알고리즘의 정당성을 고민하면서 문제를 해결해야 함연계 알고리즘 : 다익스트라 최단 경로 알고리즘, 크루스칼 알고리즘

 

 

거스름돈 p87¶

• '가장 큰 화폐 단위부터' 돈을 거슬러 주는 것화폐의 종류가 $K$개라고 할 때, 시간 복잡도 $O(K)$
  아래 알고리즘의 시간 복잡도는 동전의 총 종류에만 영향을 받고, 거슬러 줘야하는 금액의 크기와 무관

 

In [ ]:

x = int(input())
x

 

 

1260

Out[ ]:

1260

 

In [ ]:

cash_list = [500, 100, 50, 10]
count = 0

for cash in cash_list:
    count += x//cash
    x = x%cash

print(x)
print(count)

 

 

0
6

 

In [ ]:

# 그리디 알고리즘의 정당성
# 가장 큰 화폐 단위부터 돈을 거슬러 주면 항상 최적의 해가 아님
# 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문
# 그리디로 문제를 풀때 최소한의 아이디어를 떠올리고 정당한지 검토할 수 있어야 함

 

 

큰 수의 법칙 p92¶

 

In [ ]:

n, m, k = map(int, input().split())
num_list = list(map(int, input().split()))
print(n,m,k)
print(num_list)

 

 

5 8 3
2 4 5 4 6
5 8 3
[2, 4, 5, 4, 6]

 

In [ ]:

num_list.sort()
print(num_list)

 

 

[2, 4, 4, 5, 6]

 

In [ ]:

max_num = num_list[-1]
second_max_num = num_list[-2]
print(max_num)
print(second_max_num)

 

 

6
5

 

In [ ]:

result = 0

while True:
  for i in range(k):
    if m == 0:
      break
    result += max_num
    m -= 1
  if m == 0:
    break
  result += second_max_num
  m -= 1

print(result)

 

 

46

 

In [ ]:

# 이 문제의 M의 크기가 100억 이상처럼 커진다면 시간 초과 판정을 받을 것이다.
# 반복되는 수열에 대해 파악
# int(M / (K + 1)) * K + M % (K + 1)

 

In [ ]:

#  시간 효율성을 고려한 다른 코드
n, m, k = map(int, input().split())
data = list(map(int, input().split()))

data.sort()
first = data[n-1]
second = data[n-2]

# count : 가장 큰 수가 더해지는 횟수
count = int(m/(k+1)) * k
count += m%(k+1)

result = 0
result += (count) * first
result += (m-count)*second

print(result)

 

 

5 8 3 
2 4 5 4 6
46

 

 

숫자 카드 게임 p 96¶

• 각 행마다 가장 작은 수를 찾은 뒤에 그 수 중에서 가장 큰 수

 

In [ ]:

n, m = map(int, input().split())

matrix = []
for _ in range(n):
  row_list = list(map(int, input().split()))
  matrix.append(row_list)

print(matrix)

 

 

2 4
7 3 1 8
3 3 3 4
[[7, 3, 1, 8], [3, 3, 3, 4]]

 

In [ ]:

min_list = []
for i in range(n):
  min_element = min(matrix[i])
  min_list.append(min_element)

print(max(min_list))

 

 

3

 

In [ ]:

# 다른 풀이
n, m = map(int, input().split())

result = 0
for i in range(n):
  data = list(map(int, input().split()))
  min_value = min(data)
  result = max(result, min_value) # '가장 작은 수'들 중에서 가장 큰 수 찾기

print(result)

 

 

2 4
7 3 1 8
3 3 3 4
3

 

In [ ]:

# 다른 풀이 2
n,m = map(int, input().split())

result = 0
for i in range(n):
  data = list(map(int, input().split()))
  min_value = 10001
  for a in data:
    min_value = min(min_value, a)

  result = max(result, min_value)
print(result)

 

 

2 4 
7 3 1 8
3 3 3 4
3

 

 

1이 될 때까지 p99|¶

• N에서 1을 뺀다
• N을 K로 나눈다

 

In [ ]:

n, k = map(int, input().split())

count = 0
while True:
  if n == 1:
    break

  if n%k == 0:
    n = n//k
    count += 1
  else:
    n = n-1
    count += 1

print(n)
print(count)

 

 

25 3
1
6

 

In [ ]:

# 다른 답안
n, k = map(int, input().split())
result = 0

while n>= k:
  while n % k != 0:
    n -= 1
    result += 1
  n //= k
  result += 1

while n>1:
  n -= 1
  result += 1

print(result)

 

 

25 3
6

 

In [ ]:

# 다른 답안 2
n, k = map(int, input().split())
result = 0

while True:
  target = (n//k) * k
  result += (n-target)
  n = target

  if n<k:
    break

  result += 1
  n //= k

result += (n-1)
print(result)

 

 

25 5
2

 

 

모험가 길드 p311¶

 

In [ ]:

n = int(input())

horror_list = list(map(int, input().split()))
horror_list.sort()

max_team = horror_list[-1]

len_horror = len(horror_list)
count = 0

while True:
  if len_horror == 0:
    break
  len_horror -= max_team
  count += 1

  max_team = horror_list[len_horror-1]

print(count)

 

 

6
1 1 1 2 3 4
3

 

In [ ]:

# 다른 풀이
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)

 

 

6 
1 1 1 2 3 4
3

 

 

곱하기 혹은 더하기 p312¶

 

In [ ]:

S = list(input())
print(S)

 

 

567
['5', '6', '7']

 

In [ ]:

result = 0
prev_s = 0
for s in S:
  s = int(s)
  if s==0:
    result += s
    prev_s = s

  if prev_s == 0:
    result += s
    prev_s = s
  else:
    result *= s
    prev_s = s
print(result)

 

 

210

 

In [ ]:

# 다른 풀이
data =input()
result = int(data[0])

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

print(result)

 

 

567
210