1. 그리디

https://zero0205.notion.site/1-cb3cda34f7ff404a9aa9cd6cf23becf7

1. 그리디

 

• 탐욕법
• 현재 상황에서 당장 가장 좋은 것만 고르는 방법
• 현재의 선택이 나중에 미칠 영향은 고려하지 않음
• 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형
• 다익스트라 알고리즘 같은 특이 케이스의 경우 암기 필요
• 정당성 분석이 중요
• ⇒ 단순히 지금 가장 좋아보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지
• 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많음
• 코테에서 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제됨.
• 보통 코딩테스트에서 출제되는 그리디 알고리즘 유형의 문제는 창의력, 즉 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구
• ⇒ 특정 문제를 만났을 때 단순히 현재 상황에서 가장 좋아보이는 것만을 선택해도 문제를 풀 수 있는지 파악하는 능력 필요

큰 수의 법칙

• 내가 작성한 답

# 그리디
# 1. 큰 수의 법칙

n,m,k = map(int, input().split())
lst = list(map(int, input().split()))
cnt=0
sum=0

max1 = max(lst)
lst.remove(max1)

max2 = max(lst)

for j in range(m):
  if cnt < k:
    sum += max1
    cnt+=1
  else:
    sum += max2
    cnt=0

print(sum)

• 책의 해답 1

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

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

result = 0

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

print(result)

• 나는 max와 remove 함수를 이용하여 최대값과 2번째로 큰 값을 구했는데 책에서는 리스트를 정렬하여 앞의 두 값을 뽑아냈다.
• 이 방법의 경우 m이 100억 이상으로 커진다면 시간 초과 판정날 수도 있음
• 책의 해답 2

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)

• 가장 큰 수가 k번 더해지고 두 번째로 큰 수가 1번 더해지는 패턴이 반복됨⇒ 그러므로 수열은 m // (k + 1)번 반복됨을 알 수 있음
• ⇒ 이때 m이 당연히 (k+1)로 안 나누어 떨어질 수 있음 → m % (k + 1) 더해주면 됨
• ⇒ (k+1)개의 숫자로 이루어진 수열이 반복되는 것

숫자 카드 게임

• 내가 작성한 답

# 그리디
# 2. 숫자 카드 게임

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

lst = [0 for i in range(n)]

for i in range(n):
    lst[i] = list(map(int, input().split()))

ans = -1

for i in lst:
  if min(i) > ans:
    ans = min(i)

print(ans)

• 책의 해답 1

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

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차원 배열에 우선 입력받은 값들을 저장해두었다가 반복문으로 돌며 각 행에서 가장 작은 값을 ans와 비교해보며 그 중 가장 큰 값을 구하게 하였다.
• 그런데 이 값들을 굳이 저장해놓을 필요가 없으니 책처럼 한 줄 입력받고 비교하는 방식으로 하는 것이 더 효율적일 것 같다.

1이 될 때까지

• 내가 작성한 답

# 그리디
# 3. 1이 될 때까지

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

while n != 1:
    if n % k == 0:
        n /= k
    else:
        n -= 1
    cnt += 1

print(cnt)

• 상식적으로 어떻게 해도 1을 빼기보다는 나누기가 숫자의 크기를 빠르게 줄여줄 것이라는 생각이 들었기에 이렇게 작성했다
• 책의 해답 1

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

# n이 k 이상이라면 k로 계속 나누기
while n >= k:
  # n이 k로 나누어 떨어지지 않는다면 n에서 1씩 빼기
  while n % k != 0:
    n -= 1
    result += 1
  # k로 나누기
  n //= k
  result += 1

# 마지막으로 남은 수에 대하여 1씩 빼기
while n > 1:
  n -= 1
  result += 1

print(result)

• 책의 해답 2

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

# n이 k 이상이라면 k로 계속 나누기
while True:
  # (n == k로 나누어 떨어지는 수)가 될 때까지 1씩 빼기
  target = (n // k) * k
	result += (n - target)
  n = target
  # n이 k보다 작을 때(더이상 나눌 수 없을 때) 반복문 탈출
  if n > k:
    break
	# k로 나누기
  result += 1
  n //= k

# 마지막으로 남은 수에 대하여 1씩 빼기
result += (n - 1)

print(result)

• n의 범위가 커졌을 때 빠르게 동작시키기 위해 이렇게 코드를 작성할 수도 있다
• target은 k로 나누어 떨어지는 수 중 n에 가장 가까운 수를 구한 것.
• target 값을 이용하여 1 빼기를 몇 번 수행할지 한 번에 구하여 result에 넣어줄 수 있음.
• 시간 복잡도 : logN

느낀점

• 저장할 필요가 없는건 저장하지 말자....
• 수학적으로 수식을 찾아서 시간 복잡도를 줄일 수 있는지 생각해보자
• 경우의 수를 좀 잘 생각해보자 그리디도 어렵게 내려면 어려워질 수 있다
• 시간 제한과 데이터 개수를 보고 대략 어느 정도의 시간 복잡도가 필요한 문제인지 미리 예상해보는 습관을 들이자