[SWIFT 알고리즘] Car fueling 알고리즘

Car fueling 알고리즘은 그리디 알고리즘을 사용한다. 그리디 알고리즘을 간단히 설명하고자 하면 다음과 같다.

• 현재 상황에서 가장 최적의 해를 찾는다.
• 현재 문제를 더 작은 문제로 바꾼다.
• 문제 해결때까지 이 두 행위를 반복한다.

그리디 해결법으로 문제를 풀때는, 문제 해결을 할 때 여러 단계로 한다고 가정할떄, 각각의 결정을 그 상황의 가장 최고의 결정을 선택하는 것이다. 그리고 그 결정이 정해지면, 다음에는 그 결정을 생각하지 않고 나아간다. 결국은 해결까지의 과정에서 하나의 과정이 줄어든 것과 동일하다. 

그리디 알고리즘의 일반적인 접근

1. Selection Procedure : 현상황에서 가장 optimal한 옵션을 선택하고, 그것을 정답 집합에 넣는 행위
2. Feasibility check(가능성 check): 1번 step에서 고른 옵션이 정답의 가능성이 있는지 체크
3. Solution check : 그 정답 집합이 최적의 정답 집합인지 확인 

그렇다면 Car fueling  문제를 살펴보자면, 연료를 풀로 장착하고 갈수 있는 길이를 400KM 라고 할때, 가장 적게 주유소를 들리면서 도착점까지 가는 방법을 찾는 문제이다. 우리는 여기서 2가지 경우를 생각할 수 있다.

1. 가장 가까운 주유소를 들린다.
2. 갈수 있는 최대로 멀리 있는 주유소를 들린다.

그리디 알고리즘으로 문제를 해결할 경우에는

A를 시작점으로 하고, 가장 멀리 갈 수 있는 주유소 G를 고른다. 그리고 G를 A로 변경한다.(G에서 다시 출발하는 것이다.) 그리고 도착지점 B까지 가장 적게 갈수 있는 방법을 찾는다.

증명

지금 초록색 Route가 최적이라고 가정한다. 그렇다면 G1이 처음에 가는 주유소이고 G2가 2번째로 가는 주유소이다. 하지만, G가 자동차가 A에서부터 갈수 있는 최고의 먼거리의 주유소라고 하자.

• 만약에 G가 G1이랑 G2 사이에 있다면 G 다음에 G2를 들리던, 그 뒤에 있는 주유소를 들리던, G1 들리고 G2 들리는 것과 도착지점까지 가는데 들리는 주유소 수는 같거나 작다. G2를 들리면 같게 되는것이고, 그 뒤에 주유소를 들리면 더 적어지는 것이다.
• 만약에 G가 G2보다 먼거리에 있다면 그 거리까지 가는데 G1, G2를 모두 안들리기에 무조건 주유소 들리는 숫자는 적어지게 된다.

결국 초록색 route로 가는 방법은 최적이 아니다.

var start = 0
let limit = 400
var arrive = 950
let refills = [200, 375, 550, 750]
var choices = [Int]()
var result = [Int]()

while(start+limit < arrive){
    for refill in refills{
        if(refill >=  start && refill <= limit+start){
            choices.append(refill)
        }
    }
    var choice = choices.max() ?? 0
    result.append(choice)
    start = choice
}
print(result)

 

1. 현재 상황에에서 최적의 값을 찾는다.

위의 코드를 보면, start가 arrive 보다 작을때까지 반복하면서, refills 중에서 start보다 크고 start에서 최대한 갈수 있는 거리 안에 있는 것 중에 주유소 들을 골라서 그것의 가장 큰 값을 찾는다. 

2. 작은 문제로 변경한다.

고른 값을 start = choice를 해주면서 start 포인트를 갱신해준다. 결국 이미 온 길은 생각하지 않는다는 뜻이다.