[Algorithm] Swift 로 푸는 탐욕(Greedy) 문제 (+ 나동빈책)

[Algorithm] Swift 로 푸는 탐욕(그리디) 알고리즘 문제 (+ 나동빈책)

안녕하세요 이웃님들~ 마늘맘이예요~ ㅎㅎ
오늘은 Swift로 탐욕(Greedy) 알고리즘 문제를 풀어보도록 하겠습니다!
문제는 나동빈의 이것이 취업을 위한 코딩테스트다에 출제된 문제를 참고하였습니다!
책을 보시면서 문제를 정확하게 이해하시고 풀이를 보는것이 좋겠습니다~

탐욕 알고리즘이란?

탐욕 알고리즘이란 말 그대로 탐욕적으로! 현재 가장 좋아보이는 것을 선택하는 알고리즘입니다.
현재의 선택이 이후에 선택에 미치는 영향에 대해서는 고려하지 않는 알고리즘이라고 하는데요.

문제 안에 "가장 큰, 가장 작은" 과 같은 기준이 제시되어 있다면 탐욕 알고리즘을 활용하라는 단서라고 합니다!
그럼 지금부터 나동빈님이 쓰신 이것이 코딩테스트다의 예제를 함께 풀어보도록 하겠습니다.

저는 참고로 나동빈님의 풀이를 그대로 사용하지는 않았어요!
제가 이해할 수 있는 해결방법 위주로 작성이 되어있으니 절대 답안은 아니라는 점 참고 부탁드립니다!

문제 1 ) 거스름돈

동전이 500원, 100원, 50원, 10원 단위로 무한히 많을 때
거슬러줘야 할 돈이 N원 일 때, N원을 거슬러 줄 수 있는 동전의 최소 개수를 구하는 문제입니다.
예를 들어서 5120원이라면 500원 10개, 100원 1개, 10원 2개로 13개를 거슬러 주는 것이 최소 개수 겠지요?
우리도 동전의 최소 개수를 구할 때, 거스름돈을 먼저 큰 단위 동전으로 줄 수 있는데까지 주고, 남은 금액을 또 그 다음 단위 동전으로 주는 식으로 알게 모르게 그렇게 계산을 했을거예요!

똑같은 방식으로 코드를 짜줍니다.

let input = Int(readLine()!)! //콘솔창에 입력받으시려면 이런식으로 받아오시면 됩니다. 


func solution(number: Int) -> Int {
    
    let coins : [Int] = [500, 100, 50, 10] //동전 단위를 미리 배열에 넣어줘서 사용할게요! 
    
    var count: Int = 0 //동전을 몇개 사용했는지 세는 카운트 변수를 미리 만들어주세요.
    var nextN: Int = number //나머지 금액은 연산을 함에 따라 계속 변하니까 초기값을 number로 하는 변수를 선언해줬어요.
    
    for coin in coins { //동전 종류마다 한번씩 연산을 해줘야겠죠? coins 배열에 인자들을 한번씩 다 돌아줍니다.
        count = count + nextN / coin //거스름돈을 현재 단위 동전 몇개로 나눌 수 있는지 몫을 더해줍니다. 
        nextN = nextN % coin // 거스름돈을 현재 단위로 나누고 나서 남은 금액만 다시 nextN값에 넣어줍니다. 
    }
    
    //coins 배열을 다 돌고 나면 이제 남은 금액은 무조건 0이 될겁니다 (문제에서 10원 단위가 최소단위라고 제시함)

    return count // 동전의 개수를 리턴해줍니다
    
}

1번 문제는 이렇게 해결이 가능합니다! 아마 더 간결하고 좋은 코드도 있을거예요.
근데 초보자인 사람 입장에서 요렇게 보면 이해가 잘 되지 않을까요? 하하

문제 2 ) 큰 수의 법칙

두 줄의 숫자를 입력받아요. N (2 <= N <= 1,000), M (1<= M <= 10,000) , K (1 <= K <= 10,000)
첫번째 줄 (N M K)
5 8 3
두번째 줄 (배열로 만들어줘야 하는 숫자)
2 4 5 4 6

다양한 수로 이루어진 배열이 있을 때, 주어진 수 들을 M번 더하여 가장 큰 수를 만드는 것이 문제입니다.
단 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징입니다.

문제를 좀 이해하기 쉽게 써보자면 다음과 같습니다.

N은 2번째 줄에 주어지는 숫자들의 갯수
M은 덧셈을 할 횟수
K는 똑같은 숫자를 연속해서 쓸 수 있는 최대 횟수

예제처럼 [2, 4, 5, 4, 6]의 숫자들을 가지고 계산을 해보면
M 이 8이니까 덧셈을 8번 해주라는 거군요.
K는 3이니까 똑같은 숫자를 3번 초과해서 쓸 수가 없습니다. 아무리 6을 무한정 쓰고 싶어도 6을 세번 더하면 잠시 쉬어가야 하는거예요.
이때 그 다음으로 제일 큰 옵션은 뭔가요? 5겠죠.
그리고 6은 연속으로만 3번 넘게는 못쓰는거니까 5 한번으로 끊어주고 다시 최대수를 K번, 예제의 3번을 또 연속해서 써줄 수 있는거죠.
그러면 제일 큰 수를 만들 수 있는 식은 다음과 같을거예요.

6 + 6 + 6 + 5 + 6 + 6 + 6 + 5 (8번 더하기)

자 그럼 이것을 이제 코드로 바꿔봅시다.
저의 생각의 흐름은 다음과 같았어요.

1. 받은 배열의 숫자중에 제일큰 수와 그 다음 수만 있으면 무한히 연산을 할 수 있다.
가장 큰 수와 그다음 큰 수만 챙기고 나머지를 버리자!

2. M번의 연산을 하자

3. K번 반복하기 전에는 가장 큰 수를 더하고, K번 반복을 이미 한 상태에서는 그 다음 수를 더해주자.

라는 단순한 방식으로 접근을 했어요.

//options가 첫번째 줄 입력을 받은 숫자들의 배열
//numbers가 두번째 줄 입력을 받은 숫자들의 배열이라고 할게용

func solution02(options: [Int], numbers: [Int]) -> Int {
    
    let arr = numbers.sorted { lhs, rhs in
        lhs > rhs
    } // let arr = numbers.sorted(by: >) 이렇게 sorted 해주셔도 됩니다. 저는 
    
  //let n = options[0] 저는 n은 사용하지 않게 되어서 그냥 주석처리 했어요. 
    let m = options[1] // 연산 횟수인 m
    let k = options[2] // 최대 반복 가능 횟수인 k
    
    var repeatCount: Int = 0 //가장 큰 수를 반복해서 몇번 더했는지 체크할 카운트용 변수
    var result: Int = 0 //최종적으로 연산한 결과를 담을 변수
    let firstInt: Int = arr[0] // numbers 를 큰 순서로 sort한 배열에서 0번 인자 = 첫번째로 제일 큰 숫자
    let secondInt: Int = arr[1] // numbers 를 큰 순서로 sort한 배열에서 1번 인자 = 두번째로 큰 숫자
    
    for _ in 0..<m { //나는 m에 게속 접근해야 하는 방식인데, 0이 아닐때로 (불변값으로) 해주면 연산이 좀더 줄어든다.
        if repeatCount < k { //아직 K번 반복해서 더하지 않은 상태라면? 최대값을 더해주자
            result = result + firstInt 
            repeatCount += 1 //몇번 반복했는지 표시 
            
        } else { //repeatCount(반복횟수)가 k와 같거나 크면(클리는없겠지만) 더 이상 제일 큰 숫자를 쓸 수 없다. 이때 두번째로 큰 숫자를 더해준다.
            result = result + secondInt // 두번째로 큰 숫자 더해주기.
            repeatCount = 0 //이제 다시 제일 큰 수를 더해도 되니까 카운트를 0으로 초기화
            
        }
    }
    
    return result
    
}

문제 3 ) 숫자 카드 게임

숫자 카드가 N x M 형태로 제시 되어요.
배열의 배열의 모양으로 만들어 보면 아래와 같이 그릴 수 있겠죠?
숫자 카드 게임은 여러개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한장을 뽑는 게임입니다.

[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]

규칙은 다음과 같습니다!
N이 행의 개수, M이 열의 개수입니다.
뽑고자 하는 카드가 포함되어 있는 행을 선택합니다.
그런데 각 배열에서 숫자 카드를 뽑을때는 선택된 행에 포함된 카드들 중 가장 낮은 숫자의 카드를 뽑아야 합니다.

그러니까 위의 예시같은 경우에는 1번 행에서 카드를 뽑으면 1, 2번 행에서 카드를 뽑으면 4, 3번 행에서 카드를 뽑으면 7이 나오겠죠?
그렇다면 그중에 제일 큰 카드를 뽑는 경우는 3번 행에서 규칙에 맞게 카드를 뽑는 경우가 되겠습니다.

그 말인 즉,

각 배열들 내에 최소값을 뽑은 뒤에
최소값들 중에 최댓값을 뽑는 게임입니다.

func solution3(metrics: [[Int]]) -> Int {
    
    var array: [Int] = [] // 빈 배열에다가
    
    for met in metrics { // 배열안의 배열의 개수, 즉 N행 만큼 돌면서
        array.append(met.min()!) //각 배열의 최솟값을 빈 배열에 넣어줍니다. 
    }
    
    return array.max()! // 그 후 array 배열에 들어있는 최솟값들 중 최댓값을 리턴해줍니다. 
    
}
//위 풀이는 배열에 넣어서 확인을 해주는 경우, 순서가 필요할 때 사용

//아래 풀이는 더 간결
func solution3_1(metrics: [[Int]]) -> Int {
    
    var result: Int = 0 //최댓값만 구하면 되기때문에 최댓값을 담아줄 변수 선언
    
    for met in metrics { 
        result = max(result, met.min()!) // 지금 가지고 있는 최댓값 vs 돌고있는 배열 내의 최솟값 중에 더 큰값을 result에 저장
    }
    
    return result
    
}

풀이는 생각보다 간단할 것입니다. 문제가 어떻게 변형이 될 지 모르니 두가지 풀이 모두 익숙하게 할 수 있도록 해봅시다!

문제 4 ) 1이 될 때까지

숫자 N과 K가 제시됩니다.
숫자 N이 1이 될때까지 아래의 법칙에 맞춰 반복하시면 됩니다.
(실제 문제랑 법칙이 조금 다르게 써있긴 한데 아래랑 똑같은 내용이예요. )

1. N이 K로 나누어 떨어지면 N을 K로 나눈다.
2. 1번에 해당이 안되면 N에서 1을 뺀다.

N이 17, K가 4 라면
법칙을 1번 실행하고나면 16(2번법칙), 2번 실행하고 나면 4(1번 법칙), 3번 실행(1번 법칙)하고나면 1이 되겠죠.
와우! 1만들기가 성공했습니다. 1을 만드는데까지 법칙을 몇번 실행했는지 구하는 프로그램을 작성하는 것이니
이 경우에는 3을 출력하면 되겠죠.

func solution4(number: Int, divide: Int) -> Int { //N은 number에 K는 divide에 넣어줬어요
    var count = 0 //법칙이 실행된 횟수
    var object = number
    
    while object != 1 {
        if object % divide == 0 { //N이 K로 나누어 떨어지면
            object = object / divide //N을 K로 나눈값을 N으로 지정
        } else {
            object -= 1 //N이 K로 나누어 떨어지지 않으면 N-1
        }
        
        count += 1 // if문 내에서 연산을 1번 마치도록 되어있으므로 무조건 카운트는 1번 올려줌
        
        if object == 1 { // 다음 if문 돌기 전에 N이 1상태이면 멈춤
            break
        }
    }
    
    return count
}

저의 풀이는 위와 같은데요, 사실 나동빈님 풀이가 더 간결해보이는데 제가 이해를 할 수가 없어서 이건 제 방식대로 푼 예제밖에 없네요..


오늘은 탐욕 알고리즘에 대해서 알아봤는데요!
다음에는 4강 구현 문제를 함께 풀어보도록 하겠습니다!

문제를 푼 코드는 제 깃헙에도 올라가 있으니
참고해주세요.

그럼 안녕~~~