1.Greedy 알고리즘

1. 그리디 알고리즘**

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

• 즉, 매 순간 가장 좋아 보이는 것 혹은 최선이라고 여겨지는 것을 선택하는 방법이다

• 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

Greedy 알고리즘의 정당성

문제 해결을 위한 최소한의 아이디어를 떠올리고, 이것이 정당한지 검토할 수 있어야한다.

2. 예제

1) 큰 수의 법칙

# 다양한수로 이루어진 배열이 있을 때 주어진 수들을 M번더하여 가장 큰 수 만듬
# 특정 인덱스 수가 연속으로 k번 초과하여 더해질 수 없음

# 나의 해결방법 : 가장 큰 수 k번 더하고, 그 다음 큰수를 한 번 더하는 것을 반복하면 가장 큰 수가 나올 것이다.
# 따라서 가장 큰 수와 그 다음 큰 수를 추출하고, 위의 과정을 수행하는 코드를 작성


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

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

# 가장 큰 수가 더해지는 횟수 계산
# 가장 큰 수 k번 더하고 그 다음 큰 수 한번 더하는 수열이 반복되기 때문에 k+1
count = (m//(k+1))*k + m % (k+1)
result = count * first + (m-count)*second

print(result)

# 나의 풀이

answer = (m//k)*first + (m % k)*second
print(answer)

• m이 k의 배수인 경우, 나머지가 존재하지 않기 때문에, second * 0이 된다. 따라서 나의 풀이는 틀렸다.

2) 숫자 카드 게임

# 각행마다 가장 작은 수를 찾고, 그 수 중에서 가장 큰 수 찾는 문제

n, m = map(int, input().split())
minValue = []
result = 0

# 책의 풀이
for i in range(n):
    data = list(map(int, input().split()))
    min_value = min(data)
    result = max(result, min_value)

print(result)


# 나의 풀이
for i in range(n):
    data = list(map(int, input().split()))
    minValue.append(min(data))

result = max(minValue)
print(result)

• 책의 방식이 훨씬 효율적이다. 나의 방식대로 풀면, 리스트에 min값들을 저장하기 때문에, 입력값이 많아질 수록 더 많은 메모리를 차지할 것이고, max비교할 때 연산 속도가 느려질 것이다.

• 배열에 꼭 저장해야 하는지 다시 한번 생각해보자

3) 1이 될 때 까지

# N이 1이 될때까지 1을 빼거나 k로 나눠준다.
# n이 k로 나눠떨어질때 나눌 수 있음

# if문 활용해서 나눠떨어질 때, 아닐 때 구분하여 처리
# n이 1이 될때까지 위의 과정 반복

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)


# 나의 풀이
while n > 1:
    if n % k == 0:
        n = n // k
        result += 1
    else:
        n -= 1
        result += 1

print(result)

• n이 작다면 나의 풀이도 상관이 없다.
• 하지만 문제 크기가 매우 커진다면, 책의 방식이 훨씬 빨리 실행될 것이다.(log시간 복잡도)
• n을 k로 나눌때 마다 n이 크게 줄어든다.
• 한번 반복할때마다 n을 k로 나눠줄 수 있도록 만들고 나눠주는 책의 방식이 더 효율적임!

3. 느낀 점

• Greedy 알고리즘은 정형화된 알고리즘이 아니라서, 기존에 내가 문제를 해결하는 방식대로 예제를 풀었는데, 다시 생각해보니 그게 그거였다. ㅋㅋ

• 알고리즘에서 뭔가를 배우기 보다는, 예제를 풀면서 느낀 바가 많다. 그동안 내가 메모리나 연산속도 같은 것들을 아예 배제한 채 마구잡이로 문제를 풀었던 것 같다. 쓸데 없이 값들을 배열에 저장한다던지, 반복문을 무작정 사용한 것 처럼 말이다.

더 효율적인 코드를 짤 수 있을 지 항상 고려하면서 풀자