[Algorithm] Swift로 그리디 풀이해보기

[Algorithm] Swift로 그리디 풀이해보기

 

그리디는 가장 이해하기 쉬운 알고리즘 중 하나이다. 현재 가장 최적인 것 같은 해를 계속 선택해 나가는 것. 그래서 결과값을 찾는 로직이다. 매 순간 최적의 선택을 하여 전체 문제를 해결하는 것... 마치 인생과 비슷하달까...

 

그리디는 단순하지만, 이 문제가 그리디가 적용이 될 수 있는 것인지를 판단하는 것이 더 중요하다고 생각된다. 이번 포스팅에서는 그리디 인지를 판단하는 방법과 예시 문제를 풀어보면서 Swift로 어떻게 풀이할 수 있는지를 알아볼 것이다.

 

1. 그리디인지를 판단하는 방법

 

보통 질문이 "최소" 또는 "최대"를 요구할 때, 살짝쿵 의심해볼 수 있다.

예를 들어 "모든 일을 처리할 때, 최소 비용은?" / "최대한 많은 물건을 가방에 담을 때, 물건의 개수는?"

이럴 때, 의심을 해볼 수 있다.

 

그렇지만, 이것들을 모두 그리디로 판별하면 안 된다. 왜냐하면 DP로 풀이를 해야하는, 그리디가 불가능한 것일 수도 있기 때문이다.

애초에 DP로 풀면 간단한데, 그리디로 풀었다가 아래와 같은 과정을 거쳐 2) - 4) 무한루프를 거칠 수 있기 때문이다.

 

보통 그리디로 푸는 것 같은 문제 풀이 접근

1) 관찰을 통해서 탐색 범위를 줄여보는 방법을 생각한다. ->
2) 탐색 범위를 줄여도 올바른 결과를 낼 것이라는 알 수 없는 자신감을 가진다. ->
3) 자신감을 가지고 열심히 구현해서 문제를 제출한다.
4) 통과한 경우 속으로 내심 기뻐하고, 실패할 경우 2)로 돌아간다.

 

그래서 시간이 제한되어 있는 코테에서 이런 문제가 나온다면, 빠르게 짜고 틀리면 손절하거나, 마지막에 푸는 전략을 택하곤 한다.

이런 판단을 더 빨리 할 수 있는 방법은 뭘까?

 

 

(1) 단계적 결정에 따라 문제가 해결되는지 확인

 

그리디 알고리즘은 각 단계에서 가장 최선의 선택을 함으로써 전체 문제를 해결하는 방식. 각 단계의 선택이 문제 해결에 중요한 역할을 한다면, 그리디 알고리즘이 적합할 가능성이 높다.

 

두 가지 질문을 해봐야 한다.

"가장 먼저 선택해야 할 작업은 무엇인가?"를 선택해보고, 초기 상태에서 첫 번째로 최적의 선택이 필요한지를 판단한다. "다음 단계에서 최선의 선택은 무엇인가?"를 생각해보며 각 단계마다 연속적으로 최적의 선택을 필요한지를 판단한다.

 

만약 각 단계에서 최선의 선택이 다음 단계의 최선의 선택에 영향을 미친다면 그리디 알고리즘이 적합하다. 만약 각 단계의 최선의 선택이 전체 최적해를 보장하지 않는다면, 동적 프로그래밍 또는 백트래킹과 같은 다른 방법을 사용해야 한다.

 

예를 들어, 평범한 배낭(백준 12865) 문제는 그리디 방식으로 풀릴 것 같지만 절대 해결되지 않으며, DP로 풀어야 한다. 왜냐하면, 각 단계에서 최적의 선택을 하는 것(가치가 현재 최대인 물건을 선택)과 무게 제한은 다음 단계에서 가치적으로 최선의 선택을 하지 못하게 만들기 때문이다(무게를 맞춰야 함).

 

 

(2) 문제가 특정 순서에 의존하는지 확인

 

그리디는 문제를 해결하는 순서가 중요할 때 유용하다. 특정 순서대로 처리해야 할 때, 그리디가 적합하다.

 

"가장 먼저 처리해야 할 작업은?"을 떠올리면서 특정 순서로 작업을 처리해야 하는지를 생각해본다. "어떤 순서로 작업을 처리해야 하는가?"를 떠올리고, 차례대로 해야 되는 것일 경우, 최적해를 적용해야 할 가능성이 있기 때문에 그리디라는 것을 생각해볼 수 있다.

 

밑에 예시로 들 회의실 배정 문제는 각 회의를 종료 시간 기준으로 정렬한 후, 가능한 한 가장 많은 회의를 선택하는 방식으로 풀이를 떠올릴 수 있기 때문에 그리디가 적합할 것으로 추측할 수 있다. 순서가 중요하지 않거나, 최적해가 특정 순서에 의존하지 않는다면, 완전 탐색 또는 DP가 적합하다.

 

(3) 부분 최적화가 전체 최적화로 이어지는지 확인

그리디 알고리즘은 부분 문제의 최적해가 전체 문제의 최적해로 이어질 때 적합하다. 이 부분은 DP와 유사하기 때문에, 앞의 (1), (2)를 보고 그리디를 판별해도 무방할 것 같다.

 

 

(4) 소결론

 

이정도만 두고 판단하는 것도 시간이 꽤 오래걸릴 수 있다. 하지만, 그리디로 푸는 것을 정확히 캐치하는 경우, 패스 || 풀이의 과정을 선택할 수 있다. 조금의 시간을 두고, 위의 세 가지를 판별해보고 넘어가는 것이 필요할 것 같다. 그래야 DP 또는 백트래킹을 써야하는 문제와 정확히 구분을 할 수 있기 때문이다.

 

 

2. 예시 문제

 

1) ATM(백준 11399)

func solution_11399() {
    _ = Int(readLine()!)!
    let times = readLine()!.split(separator: " ").compactMap { Int($0) }.sorted(by: <)
    var answer = 0

    for i in 0..<times.count {
        answer += times[0...i].reduce(0, +)
    }

    print(answer)
}

 

문제에서 주어진 상황을 잘 살펴보면, 최소 시간을 구하라고 했기 때문에, 처음에 주어진 인덱스고 다 필요없고, 오래 걸리는 사람을 뒤로 배치해주면 최대한 일찍 끝난다는 것만 코드에 반영해주면 된다.

 

"오래 걸리는 사람을 뒤로 배치해야 한다"는 사실을 빠르게 알아차리면 그리디로 풀어야 한다는 것을 알 수 있는 문제였다.

 

2) 회의실 배정(백준 1931)

func solution_1931() {
    let n = Int(readLine()!)!
    var arr = [(time: [Int], timeCount: Int)]()
    for _ in 1...n {
        let input = readLine()!.split(separator: " ").compactMap { Int($0) }
        arr.append(([input[0], input[1]], input[1] - input[0]))
    }

    arr.sort {
        ($0.time[1], $0.time[0], $0.timeCount) < ($1.time[1], $1.time[0], $1.timeCount)
    }

    var temp = [arr[0]]
    for i in 1..<arr.count {
        let element = arr[i]
        let tempLast = temp.last!

        if element.time[0] >= tempLast.time[1] {
            temp.append(element)
        }
    }

    print(temp.count)
}

 

겹치지 않게 하면서, 가장 최대의 개수를 구하고 있으며, 회의 시간이라는 순서에 따라 답이 달라진다. 그리디를 떠올려 볼 수 있는 것이다.

그리디를 잘 적용할 수 있도록, 입력 받은 배열을 세 가지 기준으로 정렬을 해주고, 차례로 반복을 돌아주면 된다.

 

회의 시간이 짧을 수록 회의의 개수는 최대가 되니, 선택하는 조건은

-> 회의 시작 시간이 이른 순 / 회의 시간이 짧은 순 으로 선택을 하면 될 것이라는 가정을 해본다.

arr[0]에는 가장 최적인 해의 시작점이 들어있을 것이라는 확신을 할 수 있다.

 

++ swift의 sort, sorted 함수는 기본적으로 안정 정렬이기 때문에, 세 가지 모두의 기준으로 정렬하면, 마지막 count를 기준으로는 확실히 정렬될 것임이 보장된다.

 

그러면 반복문을 돌면서 stack 상단의 원소의 종료시간보다 늦은 회의 중 회의 시간이 가장 짧은 것이 temp에 담기게 될 것이다. 이렇게 반복을 하다보면 가장 최적의 해(최대 회의 개수)가 temp에 들어 갈 것이고, temp의 원소 개수만 세어 주면 정답을 출력할 수 있는 것이다.

 

 

3) 동전 0(백준 11047)

func solution_11047() {
    let input = readLine()!.split(separator: " ").compactMap { Int($0) }
    var (n, k) = (input[0], input[1])
    var coins = [Int]()
    var count = 0
    for _ in 1...n {
        coins.append(Int(readLine()!)!)
    }
    coins.sort(by: >)

    var idx = 0
    while k != 0 {

        if k / coins[idx] == 0 {
            idx += 1
            continue
        } else {
            count += k / coins[idx]
            k %= coins[idx]
        }
    }

    print(count)
}

 

전형적인 동전 문제.

다만, 큰 단위가 작은 단위의 배수이기 때문에 쉬운 편이지, 배수가 아니라 예를 들어 2, 3, 5원짜리 등으로 주어진다면 조금 골치아픈 문제이기도 하다. 어쨌든 작은 단위로 큰 단위가 다 커버를 치지 못해도, 모두 채울 수 있기 때문에, 큰 동전부터 /, % 연산을 하면서 개수를 세어주면 될 것이다.

 

 

3. 마치며

그리디는 탐욕스러워서 언제나 시간에 쫒기는 것 중 하나이다. 판별만 해두고, 미리 풀이를 생각한 후 1시간의 전사, 40분의 전사를 표방하며 마지막에 몰아치면서 제출해보는 전략으로 나는 갈 것 같다.

 

구현은 쉬운 편이라, 판별이 어려운 측면이 있지...