그리디 알고리즘

그리디 알고리즘은 동적 프로그래밍 사용 시 지나치게 많은 일을 한다는 것에서 착안하여 고안된 알고리즘이다.
동적 프로그래밍을 대체하는 것은 아니고 같이 쓰이며 서로 보완하는 개념이라고 한다.

그리디 알고리즘은 탐욕 알고리즘 또는 욕심쟁이 알고리즘이라고도 불리, 미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법이다. 이렇게 각 단계에서 최선의 선택을 한 것이 전체적으로도 최선이길 바라는 알고리즘이다.

탐욕 알고리즘 문제를 해결하는 방법

선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택한다.
적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사한다.
해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다.

탐욕 알고리즘을 적용하려면 문제가 다음 2가지 조건을 성립하여야 한다.

탐욕스런 선택 조건은 앞의 선택이 이후의 선택에 영향을 주지 않는다는 것이며, 최적 부분 구조 조건은 문제에 대한 최적해가 부분문제에 대해서도 역시 최적해라는 것이다.

• 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다.
• 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

예제) 거스름돈

거스름돈이 N이고 항상 10의 배수일 조건이 있다.
그런데 사용가능한 동전들이 500, 100, 50, 10원으로 모두 10의 배수로 이루어져있다.

그렇다면 최소의 동전으로 N을 구성하려면 총 금액 N원을 가능한 가장 큰 동전으로 구성하면 된다.
=> 가장 큰 단위의 동전부터 동전을 거슬러 주자.

import Foundation

func giveCoins(_ change: Int) -> Int {
  var tempChange = change
  let coins = [500, 100, 50, 10]
  var coinCount = 0
  
  for coin in coins {
    if tempChange == 0 {
      break
    }

    if change / coin != 0 {
      coinCount += tempChange / coin
      tempChange = tempChange % coin
    }
  }
  
  return coinCount
}

print(giveCoins(1260))

실전문제) 큰 수의 법칙

N개의 배열이 있을 때 각 수들을 M번 더해서 가장 큰 수를 만드는 문제이다. 여기서 같은 수는 연속해서 K번까지 더할 수 있고, 다른 인덱스의 같은 수는 서로 다른 수라고 인정한다.

이 문제는 가능한 큰 수들을 더하면 좋을테니까, N개의 배열을 내림차순으로 나열하여 맨 앞에 수를 K번까지 더하다가 두번째 수를 중간에 한번씩 더해주고 다시 맨 앞 수를 더해주면 될 것 같다.

import Foundation

func solution(_ array: [Int], _ N: Int, _ M: Int, _ K: Int) -> Int {
  var tempArray = array
  var answer = 0
  var kCount = 0
  tempArray = tempArray.sorted(by: { $0 > $1 })
  
  for _ in 0..<M {
    let first = tempArray[0]
    let second = tempArray[1]
    
    if kCount == K {
      answer += second
      kCount = 0
    } else {
      answer += first
      kCount += 1
    }
  }
  
  return answer
}

print(solution([2, 4, 5, 4, 6], 5, 8, 3))

처음에 위와 같이 풀었는데 책 답지를 보니 이렇게 하면 시간 초과에 걸릴수 있다고 한다... 도르륵

엥 그럼 어떻게 풀어야되지 하고 답지를 봤는데 왠걸 아예 생각지도 못한 수열로 접근해야하는 거였씀 ;;;

6, 5, 4, 4, 2 라는 배열이 있을 때
어쨌든 두개만 계속 더할 것이기 때문에 6 6 6 5 이런 식으로 같은 수열이 계속 반복될 것이다.
그럼 가장 큰수 더할 횟수와 두번째 큰수 더할 횟수 구하면 되는데 결론적으로 큰 수 더할 횟수만 구하면 된다.
구하기 위해서는 전체 더할 횟수 M을 K+1 횟수로 나눈 몫 만큼에다가 K를 곱하고, 또 그 수열에 들어가지 않는 나머지 만큼의 가장 큰 수가 존재할테니까 M을 K+1로 나눈 나머지도 구해야한다.
흑흑
글고 M에서 빼면 그게 두번째 큰수가 되는 것!

내가 과연 다음번에 나와도 생각할 수 있을지.. ㅜㅜㅜ

다시 푼 답안)

import Foundation

func solution(_ array: [Int], _ N: Int, _ M: Int, _ K: Int) -> Int {
  var tempArray = array
  var firstCount = 0
  var answer = 0
  tempArray = tempArray.sorted(by: { $0 > $1 })
  
  firstCount += (M / (K+1)) * K
  firstCount += M % (K+1)
  
  answer += firstCount * tempArray[0]
  answer += (M-firstCount) * tempArray[1]

  return answer
}

print(solution([2, 4, 5, 4, 6], 5, 8, 3))

실전문제) 숫자 카드 게임

이 문제는 행열 개념이 너무 헷갈려서 행열 공부를 다시했따 ㅋㅋ;;

왠지 row column이 더 익숙해서 행은 row 열은 column으로 읽는게 더 편한듯하다.
3열 5행이면 3종류 컬럼이 5줄 있는것,,

암튼 그래서 이 문제는 각 열에서 가장 작은 값이 모든 행의 열에서 가장 작은 값이되게하는 문제이다.
그러려면 먼저 열에서 가장 작은 값찾고 (min), max 사용해서 작은 값들 중 가장 큰 값 찾으면 된다.

import Foundation

func solution(_ array: [[Int]]) -> Int {
  var minValue = 0
  
  for array in array {
    if array.min()! > minValue {
      minValue = array.min()!
    }
  }
  
  return minValue
}

print(solution([[3, 1, 2], [4, 1, 4], [2, 2, 2], [3, 3, 4]]))

실전문제) 1이 될 때까지

import Foundation

func solution(_ N: Int, _ K: Int) -> Int {
  var temp = N
  var count = 0
  
  while temp != 1 {
    if temp % K != 0 {
      temp -= 1
      count += 1
    } else {
      count += 1
      temp /= K
    }
  }
  return count
}

print(solution(25, 5))

이렇게 간단하게 풀었는데, 책 답안에서 또 이렇게 풀면 시간이 많이 걸린다고 하였다,,
일일이 1씩 빼주는 작업이 시간이 많이 소요된다고 한다. 답안에서는 나눠지는 수를 구해주고 나머지 안나눠지는 것은 다 더해버리는 방법을 사용한다.

import Foundation

func solution(_ N: Int, _ K: Int) -> Int {
  var count = 0
  var temp = N
  
  while temp != 1 {
    if temp < K {
      count += (temp-1)
      break
    }
    if temp % K != 0 {
      count += temp % K
    }
    temp = temp / K
    count += 1
  }
  return count
}

print(solution(45, 5))