[Algorithm] 이코테 Greedy

그리디

---

특징

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

💡기준에 따라 좋은 것을 선택하는 알고리즘이기 때문에 문제에서 ‘가장 큰 순서대로’, ‘가장 작은 순서대로’와 같은 기준을 알게 모르게 제시 해준다.
대체로 이 기준은 정렬 알고리즘을 사용했을 때 만족 시킬 수 있으므로 자주 정렬 알고리즘과 짝을 이뤄 출제된다.

만약 코딩 테스트 문제를 만났을 때, 바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심하고 문제를 해결할 수 있는 탐욕적 해결법이 존재하는지 고민해보자.

👿 실전 문제 - 큰 수의 법칙

• 아이디어

  리스트를 정렬하고 가장 큰 수를 M번까지 더한다. 이때 더한 횟수가 K가 되었다면 종료. 만약 K보다 더한 횟수가 작다면 배열의 그 다음 인덱스의 요소를 한번 더하고 다시 가장 큰 수를 M 더한다.
  

• 나의 풀이

  def bigNumber(arr, M, k):
      kCnt, idx, ans = 0, 0, 0
      arr.sort(reverse=True)
  
      for i in range(0, M):
          if kCnt == k:
              ans += arr[idx+1]
              kCnt = 0
          else:
              ans += arr[idx]
              mCnt += 1
      return ans
  
  def main():
      N, M, k = map(int, input().split())
      arr = list(map(int, input().split()))
      print(bigNumber(arr, M, k))
  
  if __name__ == "__main__":
      main()

  배열을 내림차순으로 정렬하고 kCnt가 k와 같아지면 k번 더한 것이므로 다음 인덱스의 요소를 더해주고 다시 kCnt를 0으로 초기화하여 더한다.

  덧셈에는 사실상 리스트의 첫번째 요소와 두번째 요소만 필요하다.
  

• 교재 풀이

  교재에서는 아예 첫번째, 두번째 요소만을 변수로 따로 정의하여 사용한다.

  하지만 M이 10,000 이하가 아니라 100억 이상이라면? 시간 초과 판정을 받을 것이다.

  그렇다면 어떻게? 반복되는 수열을 이용하면 된다. 만약 위 문제 예제와 동일하게 2 4 5 4 6을 입력 받았다면 더해지는 수열은 6 6 6 5 가 된다.

  즉 K+1의 길이를 가지는 반복되는 수열이 되기 때문에 해당 수열의 합을 M의 몫만큼 해주고 나머지만큼 가장 큰 수를 곱해서 더해주면 된다.
  

• 개선된 풀이

  def bigNumber(arr, M, k):
      arr.sort(reverse=True)
      first = arr[0]
      second = arr[1]
  
      ans = (first * k + second) * int(M/(k + 1))
      ans += first * (M % (k + 1))
  
      return ans
  
  def main():
      N, M, k = map(int, input().split())
      arr = list(map(int, input().split()))
      print(bigNumber(arr, M, k))
  
  if __name__ == "__main__":
      main()

👿 실전 문제 - 숫자 카드 게임

• 아이디어

  가장 먼저 떠오른 방법은 그냥 각각의 행을 모두 오름차순 정렬한 후
  0번째 인덱스를 뽑은 뒤 거기서 제일 높은 수를 출력하는 것이다.
  이렇게 하면 행의 개수만큼 정렬 + 1번의 정렬이 필요하다.
  

• 나의 풀이

  def numberCard(arr, N):
      extractArr = []
      for i in range(len(arr)):
          extractArr.append(min(arr[i]))
      return max(extractArr)
  
  def main():
      N, M = map(int, input().split())
      arr = [list(map(int,input().split())) for _ in range(N)] # 2차원 배열 입력
      print(numberCard(arr, N))
  
  if __name__ == "__main__":
      main()

👿 실전 문제 - 1이 될 때까지

• 아이디어

  N이 K로 나누어질 때만 N을 K로 나눌 수 있다고 하는데 사실상 나누고 1을 빼는것과 같은 것으로 보여진다.

  다만 17, 4라면 17을 4로 나누었을 때 연산 횟수에 1 + 나머지 를 하면 될 것 같다.
  

• 나의 풀이

  def until(N, K):
      ans = 0
      while N != 1:
          if N < K:
              ans += 1
              N -= 1
          else:
              ans += N % K    
              ans += 1        
              N = N // K
      return ans
  
  def main():
      N, K = map(int, input().split())
      print(until(N, K))
  
  if __name__ == "__main__":
      main()

• 교재 풀이

  최대한 많이 나누기를 수행한다.
  K가 2 이상이기만 하면 K로 나누는 것이 1을 빼는 것보다 항상 빠르게 N의 값을 줄인다.