로고

[Swift] 그리드 알고리즘(Greedy algorithm) 정리

작성일 :

개요

알고리즘 학습을 안 한 지 오래되었습니다. 이직하면서 공부했을 법했지만 자의로 특정 회사를 지원해서 들어갔던 적은 거의 없었기 때문에 코딩테스트 준비를 할 일이 없어 아무래도 알고리즘 학습을 게을리해왔습다. 이번 이직을 준비하며 필자가 얼마나 기본기가 부족한지 깨닫게 되었고, 기초부터 학습하겠다고 마음먹고 알고리즘 공부를 시작하게 되었습니다. 오늘은 교재 1장에 나오는 그리드 알고리즘을 학습하여 해당 내용을 정리하는 글입니다.

그리드 알고리즘(Greedy algorithm은)

Greedy algorithm은 최적화 문제를 해결하는 알고리즘 중 하나로, 각 단계에서 지금 당장 최적인 선택을 계속해서 내려가면서 최종적으로 전체적으로 최적해를 찾아내는 방식입니다. 이 알고리즘은 지금 당장의 최적 선택이 반드시 최종적으로도 최적이 되는 것은 아니지만, 일반적으로는 그렇게 됩니다.

이 알고리즘은 간단하며 직관적인 방법으로, 다양한 최적화 문제에서 적용 가능합니다. 예를 들어, 최소 스패닝 트리, 최단 경로, 배낭 문제 등에서 적용할 수 있습니다. 이 알고리즘의 기본적인 구조는 다음과 같습니다.

  1. 해의 후보 중에서 하나를 선택합니다.
  2. 선택한 후보가 문제의 제약 조건에 부합하는지 확인합니다.
  3. 부합한다면, 선택한 후보를 정답에 추가하고, 문제의 제약 조건을 수정합니다.
  4. 제약 조건을 만족할 때까지 1-3 단계를 반복합니다.

이때, 각 단계에서 지금 당장 최적인 선택을 하기 때문에, 전체적인 최적해를 찾기 위해선 이러한 선택이 계속해서 이루어져야 합니다. 하지만, 이 알고리즘이 항상 최적해를 보장하지는 않습니다. 일부 문제에서는 지역 최적해에 빠지는 경우가 발생할 수 있으며, 이 경우엔 다른 알고리즘을 사용해야 합니다.

Greedy algorithm의 장점은 간단하며 직관적인 방법이라는 것입니다. 또한, 일반적으로 계산 시간이 짧아서 대용량 데이터에도 적용이 가능합니다. 하지만 이 알고리즘의 단점은 최적해가 보장되지 않는다는 것입니다. 따라서, Greedy algorithm을 적용할 때에는 문제의 특성을 잘 파악하고, 언제까지 선택을 이어나가야 할 지를 판단하는 것이 중요합니다.

그리드 알고리즘 예시

Greedy algorithm의 예시 문제로는 "거스름돈 문제(change-making problem)"가 있습니다. 이 문제는 가장 적은 개수의 동전으로 거스름돈을 주는 문제입니다. 예를 들어, 500원짜리, 100원짜리, 50원짜리, 10원짜리 동전이 있다면 800원을 거슬러 주기 위해서는 500원짜리 1개, 100원짜리 3개, 50원짜리 1개를 사용하면 최소 개수의 동전으로 거스름돈을 줄 수 있습니다.

이 문제를 Greedy algorithm으로 해결할 경우, 가장 큰 동전부터 가능한 많이 사용하는 방법을 선택하면 됩니다. 따라서, 위의 예시에서는 500원짜리 1개를 선택하고, 남은 300원을 다시 계산합니다. 이후에는 100원짜리 3개, 50원짜리 1개를 선택하면 최소 개수의 동전으로 거스름돈을 줄 수 있습니다.

하지만, 이 문제에서 Greedy algorithm을 사용할 경우 모든 경우에서 최적해를 보장할 수 있는 것은 아닙니다. 예를 들어, 1원, 2원, 5원, 10원 동전이 있을 때, 18원을 거슬러 주는 경우 Greedy algorithm을 사용하면 10원짜리 1개, 5원짜리 1개, 2원짜리 1개, 1원짜리 1개를 사용하게 됩니다. 하지만, 최적해는 10원짜리 1개, 5원짜리 1개, 2원짜리 4개를 사용하는 것입니다. 따라서, 이 경우 Greedy algorithm을 사용하면 최적해를 보장할 수 없습니다.

아래는 거스름돈 문제를 해결하기 위한 Swift 코드 예시입니다.

swift
func giveChange(amount: Int, coins: [Int]) -> [Int] {
    var remainingAmount = amount
    var result = [Int]()

    // coins를 큰 동전 순으로 정렬합니다.
    let sortedCoins = coins.sorted(by: { $0 > $1 })

    // 큰 동전부터 가능한 많이 사용하도록 선택합니다.
    for coin in sortedCoins {
        while remainingAmount >= coin {
            remainingAmount -= coin
            result.append(coin)
        }
    }

    return result
}

// 테스트
let coins = [500, 100, 50, 10]
let amount = 800
let result = giveChange(amount: amount, coins: coins)
print("거스름돈: \(result)")  // 출력: 거스름돈: [500, 100, 100, 100, 50]

위 코드에서는 giveChange 함수를 사용하여 거스름돈을 계산합니다. 이 함수는 amount 매개변수로 거슬러 줄 금액과 coins 매개변수로 동전의 종류가 포함된 배열을 받습니다. remainingAmount 변수를 사용하여 거슬러줘야 할 금액을 계속 추적하며, result 배열에는 선택된 동전의 종류와 개수를 담습니다.

sortedCoins 변수를 사용하여 큰 동전부터 선택하도록 정렬합니다. 이후에는 for 루프에서 선택한 동전으로 거슬러 줄 수 있는 만큼 계속해서 거슬러주며, 결과를 result 배열에 추가합니다. 마지막으로 result 배열을 반환합니다.

위 코드를 실행하면, giveChange 함수를 사용하여 800원을 거슬러 줄 때 가장 적은 개수의 동전을 사용하는 방법을 계산할 수 있습니다. 출력 결과는 [500, 100, 100, 100, 50]와 같이 500원 1개, 100원 3개, 50원 1개를 사용하여 거슬러준 결과입니다.

정리

일반적으로 외우지 않고 풀 수 있다는 장점이 있는 대신, 직감에 의해 특정 규칙을 발견하고 해당 규칙을 코드로 구현하는 과정에서 실수가 잦을 수 있습니다. 특히 알고리즘의 정당성을 검토하기 위해 다양한 Input sample을 마련해야 하는데, 문제를 풀기 전에 특정 사고에 갇혀 예외 케이스를 발견하지 못 해 문제를 해결하지 못하는 케이스가 많습니다. 따라서 문제를 풀기전에 sample을 미리 만들어 작성한 로직을 검토하는 방법이 유용할 수 있습니다.

기타 및 참고 자료

저작권 등 문제가 되는 부분이 있다면 삭제하겠습니다.