이코테 2021] 2. 그리디 강의 노트

https://youtu.be/2zjoKjt97vQ

 

그리디 알고리즘 (=탐욕법)

\ 현재 상황에서 지금 당장 좋은 것만 고르는 방법

\ 정당성 분석이 중요!

 

ex) 루트 노드부터 시작하여 거쳐 가는 노드 값의 합을 최대로 만들고 싶을 때,

Q: 단순히 매 상황에서 가장 큰 값만 고르는 법 : 그리디 알고리즘

 

문제점: 최적의 해를 보장할 수 없을 때가 많음

but 코테에서 대부분 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제됨

 

 

---

<문제1> 거스름 돈 문제

 

문제 해결 아이디어

• 최적의 해를 빠르게 구하기 위해서는 가장 큰 화폐 단위부터 돈을 거슬러 주면 됨
• Ex) 1,260원 : 500 / 100 / 50 / 10 => 2/2/1/1
• 정당성 분석: 최적의 해를 보장하는 이유? 큰 단위가 항상 작은 단위의 배수이므로, 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 떄문
• 따라서, 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 함

n = 1260
count = 0

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

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

화폐의 종류를 K 라 할 때,
시간 복잡도 : O(K) (화폐의 개수만큼 반복문이 실행되므로, 동전의 총 종류에만 영향을 받음)

 

---

<문제2> 1이 될 때까지

Q: 어떤 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복 선택하여 수행 (단, 두번째 연산은 N이 K로 나누어 떨어질 때만 선택 할 수 있음)

• 1. N에서 1을 뺍니다
• 2. N을 K로 나눕니다
• ex) N=17, K=4
  • 1) 17-1 = 16
  • 2) 16/4 = 4
  • 2) 4/4 = 1        > 실행횟수 : 3번

N, K가 주어질 때, N이 1이 될 때까지 1 or 2번 과정을 수행해야 하는 최소 횟수를 구하시오

 

문제 해결 아이디어

• 주어진 N에 대해 최대한 많이 나누기를 수행
• N의 값을 줄일 때, 효율성 :  2 이상의 수로 나누는 작업 > 1을 빼는 작업
• 나눌 수 있다면 나누고, 그렇지 않다면 빼라 !

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

result = 0

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

---

<문제3> 곱하기 혹은 더하기

Q:  ex) 각 자리가 숫자(0~9)로만 이루어진 문자열이 주어졌을 때,

왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 'X' or '+' 연산자를 넣어 만들 수 있는 가장 큰 수를 구하는 프로그램을 작성하기

(단, 모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정)

ex) 02984 = 0+2x9x8x4 = 576

 

- 내가 작성한 코드

num=input()

result=0 # 중간 과정의 결과 값을 저장할 변수

# i=0 일 때

add = int(num[0])+int(num[1])
mul = int(num[0])*int(num[1])

if add <= mul: result=mul
else: result+=add

# print(len(num))

i=1 # 자릿 수

while i<len(num)-1:
  add = result+int(num[i+1])
  mul = result*int(num[i+1])

  if add <= mul:
    result=mul
  else: result+=add
  
  i+=1

print(result)

모범 솔루션

data = input()

result = int(data[0])

for i in range(1, len(data)):
	# 두 수 중에서 하나라도 0 or 1인 경우, 곱하기보단 더하기 수행
    num = int(data[i])
    if num<=1 or result <=1:
    	result +=num
    else:
    	result *=num
print(result)

---

 <문제4> 모험가 길드

솔루션