알고리즘1. 그리디

그리디란? 현재 상황에서 지금 당장 좋은 것만 고르는 방법, 현재의 선택이 나중에 미칠 영향에서 고려하지 않음

특징

1. 문제의 폭이 넓다
2. 문제를 풀기 위한 최소한의 아이디어를 요한다
3. 기준에 따라 좋은것을 선택하는 알고리즘이므로 문제에서 가장 큰 순서대로, 가장 작은 순서대로 등 기준을 제시해줌(정렬 알고리즘과 짝을 이뤄 출제됨)
   4.그리디 알고리즘 정당성 검토 요구
   5.바로 문제유형 파악 어려울 시 그리디 알고리즘을 의심해보고, 해결방법 찾을 수 없다면 다이나믹 프로그래밍이나 그래프 알고리즘 등으로 해결할 수 있을지 고민해보자!

그리디 알고리즘 예제

예제1) 거스름돈
거스름돈으로 사용할 500원, 100원, 50원, 10원 동전 존재
거슬러 줘야할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 갯수.(단 , N은 항상 10의 배수)

1.핵심
가장 큰 화폐단위부터 돈을 거슬러 준다!

2.풀이적용
예) 거스름돈 1260원이라면
1260원에서 500원으로 거슬러 줄 수 있는 돈 1000원(2개)
260원에서 100원으로 거슬러 줄 수 있는 돈 200원(2개)
60원에서 50원으로 거슬러 줄 수 있는 돈 50원(1게)
10원(1개)
-> 총 4개 필요

3.파이썬 적용

n  = 1260
count = 0

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

for coin in coin_types:
    count += n //coin #count = count + n // coin (// : 나누기 연산 후 정수만)
    n %= coin #n = n%coin 나머지

print(count)

4.위 소스의 복잡도
1)화폐의 종류가 k개일 떄, k 만큼 반복문 수행.
2)시간복잡도 = O(k)
알고리즘 시간복잡도는 동전의 총 종류(k)에만 영향 받고 거슬러 줘야하는 금액(n)과는 무관

5.그리디 알고리즘 정당성 검토
화폐의 큰 단위가 작은 단위의 배수 형태이므로 가장 큰 둔위의 화폐부터 가장 작은 단위 화폐까지 차례대로 확인해 거슬러 주는 작업을 수행하면 된다는 아이디어는 정당!

실전문제 1. 큰 수의 법칙

1)의미
배열이 있을 때 주어진 수를 m번 더해서 가장 큰 수를 만드는 법칙

• 단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 k번을 초과해 더해질 수 없는 것이 이 법칙의 특징
  예) 2,4,5,4,6이 배열, m = 8, k = 3 가정시
  => 6+6+6+5+6+6+6+5 = 46
• 단, 서로다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주
  예)3,4,3,4,3 배열, m = 7, k = 2
  => 4+4+4+4+4+4+4+ = 28

2)예시문제 파악

-입력조건

• 첫째 줄에 N(2~100), M(1~10000) K(1~10000)의 자연수가 주어지며 각 자연수는 공백으로 구분
• 둘째 줄에 N개의 자연수가 주어지고 각 자연수는 공백으로 구분. 단 각각의 자연수는 1~10000이하의 수로 주어짐.
• 입력으로 주어지는 K는 항상 M보다 작거나 같다

-출력조건 : 첫재 줄에 동빈이의 큰 수의 법칙에 따라 더해진 답을 출력

3)문제 해설
실수 많은 문제유형 꼭 코드 작성해볼 것!

문제해결 포인트
1.일단 입력값 중 가장 큰 수와 두번째로 큰 수만 저장하면 됨
2.가장 큰 수를 K번 더하고 두 번째로 큰 수를 한 번 더하는 연산 을 반복!

#N, M, K를 공백으로 구분해 입력받기
n, m, k = map(int, input().split())

#N개의 수를 공백으로 구분해 입력받기
data = list(map(int, input().split()))
# input() : 파이썬에서 데이터 입력받을 때 한 줄의 문자열을 입력 받도록 함.
# 입력받은 문자열을 split()를 이용해 공백으로 나눈 리스트로 바꿈
# 이 입력받은 데이터를 정수형으로 처리하기 위해 int()사용
# int 적용시킬 때 map을 이용해 해당 리스트의 모든 원소에 적용시킴.
# 그 결과를 다시 리스트로 바꿔서 문자열을 띄어쓰기로 구분해 각각 숫자 자료형으로 저장하게 되는 것

data.sort()# 입력받은 수 정렬
firt = data[n -1] #가장 큰 수
second = data[n-2] # 두 번째로 큰 수

result = 0

while True:
    for i in range(k): # 가장 큰 수 k번 더하기
        if m == 0: # m = 0이라면 반복문 탈출
            break
        result += first
        m -= 1 #더할 때마다 1씩 빼기
    if m == 0:
        break
    result += second #두번째 큰 수를 한 번 더하기
    m -= 1 # 더할때마다 1씩 빼기
    
print(result)

M 크기가 100억 이상처럼 커져서 시간초과시 풀이법
1. 반복되는 수열에 대해 파악
2. 가장 큰 수가 더해지는 횟수와 두 번째로 큰 수가 더해지는 횟수를 구한다!
가장 큰 수가 더해지는 횟수 : int(M/(K+1))K + M%(K+!)

• 단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 k번을 초과해 더해질 수 없는 것이 이 법칙의 특징
  예) 2,4,5,4,6이 배열, m = 8, k = 3 가정시
  => 6+6+6+5+6+6+6+5 = 46 (6,6,6,5)가 반복됨.
  1)반복되는 수열의 길이 : 4 = (K+1)
  2)따라서 M을 (K+1)로 나눈 몫이 수열이 반복되는 횟수
  3)여기에 K를 곱해주면 가장 큰 수가 등장하는 횟수
  4)M이 K+1로 나눠떨어지지 않을 때, 나눈 나머지만큼 가장 큰 수가 추가로 더해짐

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

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

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

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

result = 0
result += (count)*first # 가장 큰 수 더하기 
result +=(m-count)*second # 두 번째로 큰 수 더하기

print(result)

#할당연산자
#c += a → c = c + a
#c -= a → c = c - a
#c *= a → c = c * a

실전문제 2. 숫자카드게임

1)의의
여러 개 숫자 카드 중 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임. 룰은 아래와 같음

• 숫자 쓰인 카드 N*M의 형태로 놓임(행, 열)
• 그 다음 선택된 행(가로)에 포함된 카드들 중 가장 숫자가 낮은 카드 뽑아야
• 따라서 처음 카드 골라낼 행 선태시 이후 해당 행에서 가장 숫자가 낮은 카드 뽑을 것을 고려해 최종적으로 가장 높은 숫자의 카드 뽑을 수 있도록 젼략 세워야

2)예시문제 파악
-입력조건

• 첫째 줄에 숫자카드들이 놓인 행의 갯수 N과 열의 개수 M이 공백을 기준으로 하여 각각 자연수로 주어짐(N은 1 이하, M은 100이하)
• 둘째 줄부터 N개의 줄에 걸쳐 각 카드에 적힌 숫자가 주어짐. 각 숫자는 1이상 10000이하의 자연수

-출력조건

• 첫째 줄에 게임의 룰에 맞게 선택한 카드에 적힌 숫자를 출력

3)풀이방법 2가지

#1. MIN()함수 이용

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)

#max(a,b)
#매개변수 : 반복이 가능한 자료형 '들'
#반환형 : 매개변수로 들어온 반복이 가능한 인자들 중에 가장 큰 데이터를 반환합니다.


print(result)

#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)

실전문제3. 1이 될 때까지

1)의미
어떠한 수 N이 1될 때까지 다음의 두 과정 중 하나를 반복적으로 수행. 단 두번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다.

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

이때, 전체 과정을 실행하는 최소 횟수를 구하는 프로그램을 작성하는 것.

2)문제해설

접근포인트
1. 최대한 많이 나누기
2. N이 K의 배수가 될 때까지 1씩 빼고, N을 K로 나눈다!
검증포인트
1. K가 2이상이기만 하면, K로 나누는 것이 1을 빼는 것보다 항상 빠르게 N의 값을 줄일 수 있다

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

while True:
    #(N==K로 나누어 떨어지는 수)가 될 때까지 1씩 빼기
    target = (n//k)*k # n이 k로 안 나누어떨어질 때 가장 가까운 나누어떨어지는 수. 1을 뺴는 과정을 몇번 반복해서 target이라는 값까지 만들 수 있고 target은 k로 나눠떨어지는 수
    result += (n-target) # (n-target):1을 빼는 연산 횟수
    n = target
    #N이 K보다 작을 때(더 이상 나눌 수 없을 때)반복문 탈출
    if n<k:
        break
        
    #K로 나누기
    result += 1
    n //=k
    
#마지막으로 남은 수에 대해 1씩 뺴기
result += (n-1)
print(result)

로그시간복잡도로 빠르게 해결 가능.