이번에는 greedy algorithm의 대표적인 예시중 selecting break points에 대해서 알아보고자 한다. 먼저 알고리즘을 생각하기 이전에 상황에 대해서 설명부터 하겠다. 이 문제는 일종의 scheduling 문제로 greedy algorithm의 대표적인 문제이다.
당신은 차를 타고 여행을 떠나는 사람이다. 대한민국에서 서울과 포항을 이동해야하는 상황이고, 차를 타고 지나가야 하는 경로는 정해져 있다. 이때 당신의 차는 기름을 필요로 하는 상황이고, 여기서 기름의 양(fuel capactity)을 C로 설정해 보겠다. 길을 따라서 정해진 곳에서 주유를 해야하고, 당신의 최종 목표는 가능한 적은 수의 주유소를 들러야 한다.
Input으로는 n개의 주유소 위치가 포함 된 set을, output으로는 이 중에서 선택이 된 주유소가 포함 된 subset이다. 이때, 우리가 필요로 하는 것은 거리에 따른 주유소의 위치이기 때문에 한개의 축만을 사용해서 나열할 필요가 있다. 그래서 가장 먼저 시작 지점부터 도착 지점을 포함하여 주유소의 위치를 거리에 따라서 정렬해준다. 그러면 B라는 set에서 n+1개의 원소들이 정렬이 될 것이다. 다음으로는 output S를 초기화 해준다. 시작 지점을 지정해주면 되고, 이제부터 주유소를 들려야 하는지에 대하여 판단할 것이다.
첫번째 주유소에 도착했다고 가정하자. 만약 이 상황에서 이전 도착 지점까지의 거리, 지금으로는 0일 것이고 이 거리와 현재 주유량으로 인하여 달릴 수 있는 거리가 현재 도착한 주유소의 거리보다 큰데, 만약 다음 주유소에는 닿지 못할 것 같은 기름의 양이라면, 현재의 주유소의 위치를 output S에 포함시켜 준다. 이를 계속해서 매 주유소마다 판단을 해서 output S에 포함시켜주면 된다. 이 알고리즘이 왜 greedy한 것인지 생각해 보았을 때, 도착한 현재 지점에 대해서 다음 지점을 갈 수 있을지 없을지에 대한 판단으로 최대한의 이익을 뽑아내기 때문에 greedy한 것이다. 매 순간순간에 판단을 해야하는 것이 중요한 핵심이다. 그래서 이렇게 우리는 최대한의 거리를 달릴 수 있도록 기름의 양을 아슬아슬하게 최대한으로 사용해서 최소한의 들러야 하는 주유소의 지점을 찾아낸 것이다.
Running Time은 O(nlogn)으로 처음 정렬에 사용되는 알고리즘은 거의 O(nlogn)이며, 초기화하는 과정은 1번만 진행이 되기에 O(1)이 된다. 그리고 반복문에서 별다른 복잡한 계산 등이 없이 n개의 원소에 따라서 판단만 진행하기 때문에 O(n)이 되어 최종적으로는 O(nlogn)이 되는 것이다.
