Juneer Blog

그리디

 
  • Mar 10, 2022

Greedy: 탐욕스러운, 욕심 많은
여러 경우 중 하나를 선택해야 할 때마다 그 순간에 최적이라고 생각되는것을 선택하는 것

큰 수의 법칙

P92쪽

  • 내 코드
N, M, K = map(int, input().split())

arr = list(map(int, input().split()))
print(arr)

max_val = max(arr)

arr.remove(max_val)
sec_max_val = max(arr)

quan = M // (K+1)
rest = M % (K+1)

final_val = (max_val * K + sec_max_val)*quan + max_val * rest
print(final_val)
  • 피드백
    • input() 쪽 입력 처리가 익숙치 않아서 오래걸렸음. input().split()은 리스트를 반환하며 각 요소는 공백으로 구분된 String 타입임을 기억하자
    • if else로 max 값이 2개 이상 같을경우, 그렇지 않을경우로 나눠서 접근하려 했으나 list의 remove 이용하면 if else로 나눌 필요 없이 진행해도 된다는 것을 깨닫는데 오래걸림.
    • 연산자 우선순위를 고려하지 못해서 M // K + 1 의 문제점을 발견하지 못했음
    • max() 도 있지만 arr.sort() 이후 arr[-1], arr[-2] 이런식으로 접근해도 가장 큰 숫자, 두번째로 큰 숫자를 구할 수 있다.

1이 될 때까지

P99쪽

  • 내 코드

    N, K = map(int, input().split())

result = N
count = 0

while(True):
  if (result == 1):
    break

  if (result % K == 0):
    result = result // K
    count += 1
  else:
    result -= 1
    count +=1

print(count)

  • 정답은 맞췄지만 N > 100억 인 것 처럼 Testcase의 크기가 커질경우 위 풀이방법으로는 시간 초과가 난다고 함

    • 최상의 경우 시간복잡도 구하기

    • 최악의 경우 시간복잡도

      • N번만큼 -1 연산만 하는 것이므로 BigO(N)이며 N이 10억 이상일 경우 1초 이상 걸려 시간 초과 에러가 발생할 것이다

위 최악의 경우에도 만족하는 코드 작성을 위해 다음과 같은 아이디어를 책에서는 제시한다.

  • N이 K의 배수가 되도록 효율적으로 한 번에 빼는 방식으로 소스코드를 작성할 것
    • 아..! 최악의 경우를 시간복잡도로 구하니까 이제 보임. 최악의 경우에는 -1 연산만 잔뜩 있는것인데, 아래 코드대로 작성하면 -1에 대한 연산은 한번에 해치워버림..! Wonderful..!
    n, k = map(int, input().split())
result = 0
count = 0
target = k + 1

while True:
  if target < k:
    break
  target = n // k
  count += 1
    
  rest = n % k
  count += rest

    

  n = target

count += rest - 1
print(count)

위 코드의 시간복잡도를 계산하기 위해서는 어떤 변수가 탈출 조건에 해당하는지를 일단 유의한다. while 문에서 break로 탈출하기 위해서는 if문에서 n 변수가 어떻게 감소되는지를 확인하면 된다.

Search