(알고리즘) Greedy, 탐욕법

요즘 부쩍 알고리즘에 관심이 생겼습니다.

그래서 책을 한권 사서 보고 있는데요,

이것이 취업을 위한 코딩 테스트다 with 파이썬

나동빈님이 출간하신 이것이 취업을 위한 코딩 테스트다 라는 책을 보고 있습니다.

고르는데 딱히 뭔가 기준이 있었던건 아니고, 저는 ebook을 좋아해서, yes24를 가장 많이 사용하는데요.
yes24에서 알고리즘으로 검색하면 코딩 알고리즘 관련 도서중 가장 위에 나옵니다.


네.. 별생각 안하고 샀어요..
(뭐든지 일단 해보는게 중요하죠 ㅠ)


그래서 1장에 소개되어 있는 그리디 알고리즘을 조금 풀어 보았습니다.
물론 iOS개발을 하고 있으니 Swift로 풀어 보았습니다.
온라인채점이 불가능해서 효율이 어떤지는 잘 모르겠지만.. 그래도 일단 푼게 아까워서 공유합니다 ㅎㅎ
https://github.com/HEROHJK/Algorithm


문제는 네가지를 풀어 보았습니다.


그리디 알고리즘은 문제 해결을 판단할 때 마다 가장 효율적이라고 생각하는 방법으로 풀어나가는 알고리즘이다


이렇게 그리디 알고리즘 소개가 되어 있는데요.. 솔직히 몇번을 읽어 봐도 잘 모르겠습니다.
특정패턴의 집합되어있지 않은 다양한 문제들을 빠르게 해결하기 위한 알고리즘..?
깊게 생각 안하고 일단 문제를 풀어 보았습니다.

거스름돈

첫번째 문제는 거스름돈 문제입니다.

500원, 100원, 50원, 10원짜리 동전이 준비되어 있을 때, 최소한으로 거스름돈을 주는 방법을 구하라 입니다.

입력: 10의 배수의 숫자

출력: 각 동전의 개수

func greedy1(price: Int) {
    let coinTable = [500, 100, 50, 10]

    var resultText = ""

    var price = price

    for coin in coinTable {
        let count = price/coin

        resultText += "\(coin)원 \(count)개\n"

        price %= coin
    }

    print(resultText)
}

너무 간단한 문제네요..

뭐 print가 아닌 return으로 output을 줘야겠지만.. 딱히 채점할곳이 없어서 대충 했습니다.

당연한거지만, print같은 함수 호출 연산은 적을수록 효율이 좋아집니다.

큰 수의 법칙

두번째 문제는 큰 수의 법칙

숫자 배열이 주어졌을 때, 숫자를 골라 N번 더하여 가장 큰 수를 구하는 알고리즘입니다.

다만 N이라는 매개가 하나 더 들어가는데, 한 수를 M번이상 더하지 못하게 합니다.

[1, 3, 5, 7]이 주어지고, N이 5, M이 3이라는 조건에서 가장 큰 수를 구하는건데요.

7 + 7+ 7+ 5+ 7 = 33 이라는 결과가 나오겠죠.

입력: N M K (숫자들 배열의 카운트, 더할 횟수, 연속할 횟수), 숫자 배열

func greedy2_1(input: String, numberString: String) {
    let split = input.components(separatedBy: " ")
    guard split.count > 2 else { return }
    guard var count = Int(split[1]) else { fatalError("count의 유형이 올바르지 않습니다.") }
    guard let consecutive = Int(split[2]) else { fatalError("consecutive의 유형이 올바르지 않습니다.") }

    let numbers: [Int] = numberString.split(separator: " ").compactMap{ Int($0) }.sorted(by: >)

    var result = 0
    var i = 0

    while count > 0 {
        result += numbers[0]
        count -= 1
        i += 1

        if consecutive <= i {
            result += numbers[1]
            count -= 1
            i = 0
        }
    }

    print(result)
}

func greedy2_2(input: String, numberString: String) {
    let split = input.components(separatedBy: " ")
    guard split.count > 2 else { return }
    guard let count = Int(split[1]) else { fatalError("count의 유형이 올바르지 않습니다.") }
    guard let consecutive = Int(split[2]) else { fatalError("consecutive의 유형이 올바르지 않습니다.") }

    let numbers: [Int] = numberString.split(separator: " ").compactMap{ Int($0) }.sorted(by: >)

    let firstNumber = numbers[0]
    let secondNumber = numbers[1]

    let sum = firstNumber * consecutive + secondNumber // 가장큰수의 연속값 + 가장 작은수의 합

    /*
     위에서 계산한 합을 더해준 후,
     나머지 횟수만큼 가장 큰수를 더해준다.
     */

    let result = (sum * (count / (consecutive + 1))) + ((count % (consecutive + 1)) * firstNumber)

    print(result)
}

이렇게 두개를 짜 보았습니다.

어차피 온라인 채점을 하게 되면, 최상단의 유효성 검사는 따로 신경 안써도 됩니다. 틀린값은 안오니깐요..

첫번째는 단순한 반복 알고리즘입니다.

조금 더 효율적인 방법이 없을까 하고 생각한 후에 두번째처럼 풀었습니다.

가장 큰 수의 연속값(위 예제로 치면 7*3) + 두번째로 큰 수(5) <- 이걸 한 세트로 묶습니다.

1. M + 1, 즉 연속 횟수 + 1입니다.

2. 그럼 N, 더해야하는 횟수에서 연속횟수 + 1을 나눠줍니다.

3. 그리고 위에서 구한 세트합 만큼 곱해줍니다.

4. 그러면, 2에서 나눠준 나머지 횟수가 있죠? 그 횟수는 연속 횟수를 넘어가지 않기 때문에, 나머지만큼 가장 큰 수를 곱한 후 더해줍니다.

(아래는 조금 쉽게 풀어 쓰겠습니다)

var result = sum * (count / consecutive + 1) // +1이 붙은 이유는, 연속 + 두번째로 큰 수 까지 포함되어있기 때문.

result += (count  % consecutive + 1) * firstNumber

이렇게 결론에 도달하고,

이걸 줄이면

let result = (sum * (count / (consecutive + 1))) + ((count % (consecutive + 1)) * firstNumber)

이렇게 됩니다.

숫자 카드 게임

여러개의 숫자 카드 덱 중에서, 가장 낮은 숫자가 가장 높은 덱을 뽑는 게임입니다.

Rule

• 숫자가 쓰인 카드들이 N * M 형태로 놓여있다.
• 뽑고자 하는 카드가 포함되어 있는 행을 선택한다
• 그 다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다.
• 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다.

Input

• 행 열의 count (4 5 -> 4행 5열)
• 열의 카운트만큼의 카드 덱들 (5열이라면 5개의 카드 덱)

Output

• 가장 낮은 숫자가 가장 높은 카드덱의 가장 낮은 숫자 (?!)

Exam

Input

3 3
3 1 2 
4 1 4
2 2 2

Output

2

func greedy3(inputSize: String, cardsString: String...) -> Int {
    var numbers: [Int] = [0]
    cardsString.forEach { numbers.append($0.split(separator: " ").compactMap { Int($0) }.sorted()[0]) }
    return numbers.sorted()[0]
}

따로 복잡하게 생각하지 않고, Swift에서 제공하는 콜렉션 함수들을 이용해서 풀었습니다.

• cardsString <- 이건 문자열(카드 덱) 배열입니다. 가변인자죠.

• 배열을 순회합니다 (cardString.forEach)

  • numbers라는 새로 만든 배열에 아래 조건과 일치하는 값을 집어 넣습니다.
    • String이기 때문에, split으로 쪼갠 후, Int로 변환을 해줍니다. (String -> Int 변환을 위해 compactMap을 이용)
    • 그 후, 정렬(sorted는 디폴트가 내림차순입니다)을 한 후, 맨 앞에(=가장 큰)값 하나만 집어 넣습니다.

• 순회가 끝나면, 또 다시한번 정렬하여, 가장 큰 값을 출력합니다.

1이 될때 까지

수를 하나 입력받고, 그게 1이 될때까지 반복 수행을 해서, 그 횟수를 출력하는 문제입니다.

Rule

• N과 K가 주어진다.
• N이 1이 될때까지 다음 두 과정중 하나를 반복한다.
  • N에서 1을 뺀다
  • N을 K로 나눈다 (나머지가 없을 때만 가능)
• 1이 될동안 첫번째, 혹은 두번째 과정의 연산 횟수를 구하라.

Input

• N -> 1로 만들어야 하는 수
• K -> 나눌 값 (N보다 작거나 같다)

Output

• 연산 횟수

Exam

Input

17 4

Output

// 1) 17-1 = 16
// 2) 16/4 = 4
// 3) 4/4 = 1
3

func greedy4(_ n: Int, _ k: Int) -> Int {
    var n = n

    var count = 0

    while n >= k {
        if n % k != 0 {
            count += n % k
            n -= n % k
        }
        if n / k > 0 {
            count += 1
            n /= k
        }
    }

    count += n - 1

    return count
}

• Swift에서 입력받은 매개변수는 기본적으로 static입니다. 따라서 var로 변환해줍니다.
• n이 k보다 클동안 반복합니다
  *n을 k로 나눴을때 나머지가 0이 아니면, 1씩 뺍니다.
  • 이걸 간소화 해서, 나머지만큼 한번에 빼버립니다. (반복 회수 줄이기)
    • n을 k로 나눴을때, 나머지가 0이면 그대로 나눠줍니다.
• 반복이 끝나면, N이 1보다 크고, k보다 작을수 있습니다.
  • 그럴땐 남은 값을 빼주고, 뺀만큼 count에 횟수를 넣어줍니다.