탐욕법을 이용한 알고리즘, 혹은 '탐욕적인 알고리즘'은 우리가 원하는 답을 재귀 호출과 똑같이 여러 개의 조각으로 쪼개고, 각 단계마다 답의 한 부분을 만들어 간다는 점에서 완탐이나, 동적 계획법 알고리즘과 다를 것이 없다.
그러나 모든 선택지를 고려해 보고 그중 전체 답이 가장 좋은 것을 찾는 두 방법과는 달리, 탐욕법은 각 단계마다 지금 당장 가장 좋은 방법만을 선택.
여행하는 외판원 문제를 예를 들어 봤을때, DP는 다음에 도착할 수 있는 도시들을 하나하나 검사해보고, 남은 도시들을 모두 순회하는 데 필요한 거리의 합을 최소화하는 답을 찾았다. 반면 탐욕법은 당장 다음 도시까지의 거리만을 최소화한다. 따라서 아직 방문하지 않은 도시 중 가장 가까운 도시로 움직이는 것을 모든 도시를 방문할 때까지 반복하게 된다. 탐욕법은 지금의 선택이 앞으로 남은 선택들에 어떤 영향을 끼칠지는 고려하지 않는다.
탐욕법(Greedy Method)는 많은 경우 최적해를 찾지 못한다. 따라서 탐욕법이 사용되는 경우는 크게 다음 두 가지로 제한된다.
- 탐욕법을 사용해도 항상 최적해를 구할 수 있는 문제를 만난 경우. 탐욕법은 DP보다 수행 시간이 훨씬 빠르기 때문에 유용하다.
- 시간이나 공간적 제약으로 인해 다른 방법으로 최적해를 찾기 너무 어렵다면 최적해 대신 적당히 괜찮은 답(근사해)을 찾는 것으로 타협할 수 있다. 탐욕법은 최적은 아니지만 임의의 답보다는 좋은 답을 구하는 용도로 유용하게 쓰인다.
탐욕법은 주로 프로그래밍 대회에서는 첫 번째 용도로만 사용된다. 근사해를 찾는 문제는 대개 출제가 되지 않을 뿐더러, 가끔 근사해를 구하는 문제가 주어졋다 해도 탐욕법보다는 메타휴리스틱 알고리즘들이 더 좋은 답을 주는 경우가 많다.
한 문제를 탐욕법으로 해결하는 방법이 한 가지만 있는 것이 아닌 경우도 많은데, 이 중 어느 방법을 선택해야 최적해를 구할 수 있을지를 알아내기가 어렵기 때문, 실제로 최적해를 얻을 수 있는 접근이 직관적이지 않은 경우도 많기 때문에 실수에 더 유의 해야 한다.
❗️ Greedy Method
탐욕적 알고리즘 연습 문제를 풀 때는 알고리즘의 정당성을 증명하는 과정을 빼먹지 않고 연습하는 것이 좋다.
❓ Metaheuristic
최적화 알고리즘의 한 종류로, 좋은 답을 빠르게 찾아낼 수 없는 문제의 근사해를 구하기 위해 주로 사용된다. 일반적으로 사용되는 최적화 알고리즘은 목적 함수를 미분할 수 있다는 가정을 사용하는 반면, 메타휴리스틱은 이런 가정을 하지 않기 때문에 프로그래밍 대회에서도 종종 사용된다. 굉장히 많은 휴리스틱 기법이 있지만 그중 국소 탐색(local search)이나 시뮬레이티드 어닐링(simulated annealing)이 구현과 튜닝이 가장 간단해 자주 쓰인다.
활동 선택 문제(activity selection problem) 회사에 회의실이 하나밖에 없는데, n(<=100)개 의 팀이 각각 회의하고 싶은 시간을 아래 그림과 같이 제출했다. 두 팀 이 회의실을 같이 쓸 수는 없기 때문에 이 중 서로 겹치지 않는 회의들만을 골라내서 진행해야 한다. 최대 몇 개나 선택 가능할까 ?
이 문제에는 답이 여러 가지 있을 수 있다. 서로 겹치지 않는 회의들의 집합은 모두 이 문제의 답이다.
이때 우리가 원하는 가장 좋은 답, 곧 최적해는 크기가 가장 큰 부분 집합.
이 문제를 무식하게 푸는 방법은 모든 부분 집합을 하나하나 만들어 보며 그중 회의들이 겹치지 않는 답들을 걸러내고 그중 가장 큰 부분 집합을 찾아낸다. 그러나 집합의 크기가 n일 때 부분 집합의 수는 2ⁿ이기 때문에 n이 30만 되어도 시간 안에 문제를 풀기는 힘들다.
탐욕법으로 해결하는 방법을 몇 가지 떠올릴 수 있지만, 길이가 짧은 회의부터 하나하나 순회하면서 앞의 것들과 겹치지 않는 것들을 추가하는 방법도 그 중의 하나. 이 방법은 회의실이 사용 가능한 시간을 최대화 하려고 노력하기 때문에 비교적 그럴듯해 보이지만 사실 아니다.
위와 같은 입력이 주어진다면 긴 회의 두개를 개최하는 대신 짧은 회의 하나만을 개최하게 된다. 이와 같이 탐욕법을 사용하는 알고리즘들은 꼭 그럴듯 하다고 해서 정답을 내는 것이 아니다. 정당성을 증명해야 하기 때문에 어렵다.
이 문제를 해결하는 탐욕적인 방법은 길이와 상관없이 가장 먼저 끝나는 회의부터 선택하는 것. 가장 먼저 끝나는 회의를 선택하고, 이 회의와 겹치는 것들을 모두 지운 뒤 다시 이 중에서 가장 먼저 끝나는 회의를 선택하기를 반복.
- 목록 S에 남은 회의 중 가장 일찍 끝나는 회의
S(min)을 선택한다. S(min)과 겹치는 회의를 S에서 모두 지운다.- S가 텅 빌 때까지 반복한다.
탐욕법의 정당성 증명은 많은 경우 일정한 패턴을 가진다. 이 증명 패턴은 탐욕법이 항상 최적해를 찾아낼 수 있다는 것을 두 가지의 속성을 증명함으로써 보인다.
우리가 처음으로 증명해야 할 속성은 동적 계획법처럼 답의 모든 부분을 고려하지 않고 탐욕적으로만 선택하더라도 최적해를 구할 수 있다.
이 속성은 매우 중요하기 때문에 따로 이름을 붙여 탐욕적 선택 속성(Greedy Choice Property)이라고 부른다. 어떤 알고리즘에 이 속성이 성립할 경우, 우리가 각 단계에서 탐욕적으로 내리는 선택은 항상 최적해로 가는 길 중 하나다. 따라서 탐욕적인 선택을 해서 '손해'를 볼 일이 없다는 것을 알 수 있다. 우리가 앞에서 제안한 알고리즘의 경우, 탐욕적 속성이 성립한다는 말은 다음 조건이 성립한다는 의미이다.
가장 종료 시간이 빠른 회의
S(min)를 포함하는 최적해가 반드시 존재한다.
S의 최적해 중 S(min)을 포함하지 않는 답이 있을때, 이 답은 서로 겹치지 않는 회의의 목록이다. 이 목록의 첫 번째로 개최되는 회의를 지우고 S(min)을 대신 추가해서 새로운 목록을 만든다. S(min)은 S에서 가장 일찍 끝나는 회의이기 때문에 (혹은 가장 일찍 끝나는 회의 중 하나이기 때문에) 지워진 회의는 S(min)보다 일찍 끝날 수는 없다. 따라서 두 번째 회의와 S(min)이 겹치는 일은 없으며, 새로 만든 목록도 최적해 중 하나가 됩니다. 따라서 항상 S(min)을 포함하는 최적해는 존재한다. 이와 같은 증명은 우리가 가장 일찍 끝나는 회의를 선택해서 최적해를 얻는 것이 불가능해지는 경우는 없음을 보여준다.
이렇게 탐욕적인 방법으로 선택하는 것이 항상 최적의 답을 줄 수 있다고 해서 증명이 끝난 것은 아니다.
항상 최적의 선택만을 내려서 전체 문제의 최적해를 얻을 수 있음을 보여야 한다.
이것은 너무 당연해 보이지만, 경우에 따라 성립하지 않을 수 있다. 첫 번째 선택을 하고 나서 남는 부분 문제는 최적이 아닌 방법으로 풀어야 하는 경우. 탐욕법의 정당성을 위해 증명해야할 두 번째 속성은 최적 부분 구조(Optimal Substructure)이다. DP를 다룰 때 했듯이, 부분 문제의 최적해에서 전체 문제의 최적해를 만들 수 있음을 보여야 한다.
다행히 이 속성은 대개 매우 자명해서 따로 증명할 필요가 없는 경우가 대부분. 첫 번째 회의를 잘 선택하고 겹치는 회의를 모두 걸러냈다면, 남은 회의 중에 당연히 최대한 많은 회의를 선택해야 한다.
우리가 설명한 알고리즘은 모든 회의의 목록을 저장해 두고, 한 회의를 선택할 때마다 겹치는 회의들을 모두 제거한다. 설명은 이해하기 쉽지만 구현은 약간 번거롭다. 이미 목록을 배열에 저장한다면 전체 시간 복잡도는 O(n²)이 되어 시간도 오래 걸리는 편이다.
이 알고리즘을 쉽고 빠르게 구현하는 한 방법은 처음에 모든 회의를 종료 시간의 오름차순으로 정렬해 두는 것. 이때 정렬된 배열의 첫 번째 회의는 우리가 무조건 선택해도 된다. 그 후 겹치는 회의를 지울 필요 없이, 정렬된 배열을 순회하면서 첫 번째 회의와 겹치지 않는 회의를 찾는다. 회의들은 오름 차순으로 정렬되어 있기 때문에, 겹치지 않는 회의를 찾자마자 나머지를 보지 않고 선택해도 된다.
각 회의가 겹치는지의 여부를 파악할 때 다음 회의가 시작할 수 있는 가장 이른 시간만을 알고 있으면 된다는 것을 유의하자. 이와 같이 특정 조건으로 객체들을 정렬해 두면 탐욕법의 구현이 쉬워지는 경우가 많다.
// 각 회의는 [begin, end) 구간 동안 회의실을 사용
// 그림 10.1 입력
var begin = [2, 2, 1, 3, 2, 1, 5, 6, 8, 8, 9]
var end = [4, 7, 4, 5, 4, 7, 9, 9, 10, 9, 10]
var n = begin.count
func schedule() -> Int {
// 일찍 끝나는 순서대로 정렬
var order : [(Int, Int)] = []
for i in 0..<n {
order.append((end[i], begin[i]))
}
order.sort(by:){$0.0 < $1.0}
// earliest: 다음 회의가 시작할 수 있는 가장 빠른 시간
// selected: 지금까지 선택한 회의의 수
var earliest = 0, selected = 0
for i in 0..<order.count {
var meetingBegin = order[i].1
var meetingEnd = order[i].0
if (earliest <= meetingBegin) {
earliest = meetingEnd
selected += 1
}
}
return selected
}
print(schedule())sort(by:)
Sorts the collection in place, using the given predicate as the comparison between elements.
Complexity
O(n log n), where n is the length of the collection.
스위프트에서의 sort의 시간 복잡도는 nlogn이다.
이 알고리즘은 O(nlgn)시간이 걸리는 정렬 후에 선형 시간만이 걸리는 선택과정을 통해 최적해를 찾아낸다. 이 알고리즘은 각 단계에서 회의를 선택할 때 남은 다른 회의들은 전혀 신경 쓰지 않는다. 지금 당장 가장 일찍 끝나는 회의만 선택한다.
각 팀은 n명씩의 프로 코더들로 구성되어 있으며, 결승전에서는 각 선수가 한 번씩 출전해 1:1 경기를 벌여 더 많은 승리를 가져가는 팀이 최종적으로 우승하게 됩니다. 각 팀의 감독은 대회 전날, 주최측에 각 선수를 출전시킬 순 서를 알려 주어야 합니다.
결승전 이틀 전, 한국팀의 유감독은 첩보를 통해 상대 러시아팀의 출전 순서를 알아냈습니다. 이 대회에서는 각 선수의 실력을 레이팅(rating)으로 표현합 니다. 문제를 간단히 하기 위해 1:1 승부에서는 항상 레이팅이 더 높은 선수가 승리하고, 레이팅이 같을 경우 우리 선수가 승리한다고 가정합시다.
| 경기 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 러시아팀 | 3,000 | 2,700 | 2,800 | 2,200 | 2,500 | 1,900 |
| 한국팀 | 2,800 | 2,750 | 2,995 | 1,800 | 2,600 | 2,000 |
표와 같이 출전 순서를 정했다고 하면 한국팀은 2, 3, 5, 6에서 승리해 전체 4경기를 이기게 된다. 그러나 대신 4번 경기와 1번 경기에 나갈 선수를 바꾸면 1번 경기만을 제외하고 모든 경기에 승리할 수 있다. 상대방 팀 선수들의 순서를 알고 있을 때, 어느 순서대로 선수들을 내보내야 승수를 최대할 수 있을까 ?
n명의 선수가 있으니 이 문제에는 n!개의 답이 있다. n!개의 순열을 모두 만드는 것은 완전 탐색으로 쉽게 할 수 있는 작업입니다만, n이 조금만 커져도 답의 개수가 너무 많기 때문에 시간 안에 다 셀 수 없다.
n!개의 답을 모두 생성하는 완전 탐색 알고리즘에 메모이제이션을 적용하는 것은 이미 해 본 적이 있다. 한국팀의 출전 순서를 맨 앞에서부터 한 명씩 정해 가기로 하면, 각 선수를 지금까지 순서에 추가했는지를 나타내는 불린 값 배열 만을 받는 부분 문제를 만들 수 있다.
order(taken) = 각 한국팀 선수를 이미 순서에 추가했는지의 여부가 taken에 주어질 때, 남은 선수들을 적절히 배치해서 얻을 수 있는 최대 승수
taken에 포함된 true의 수를 세면 이번에 선택할 선수가 러시아팀의 어떤 선수와 경기하게 되는지도 알 수 있으니, taken 외에 다른 인자는 필요없다. 그렇다면 O(n2ⁿ)시간의 동적 계획법 알고리즘을 얻을 수 있다.
탐욕적 알고리즘을 설계하는 좋은 방법은 간단한 입력을 몇 개 손으로 풀어 보면서 패턴을 찾는 것이다. 이 문제를 풀 수 있는 탐욕적 알고리즘에는 몇 가지가 있지만, 이 중 직관적인 것으로 다음과 같은 알고리즘이 있다.
맨 앞 경기부터 한 명씩 출전할 한국 선수를 정하도록 한다. 상대방 선수를 이길 수 있는 (레이팅이 같거나 높은) 한국 선수가 있는 경우 그중 레이팅이 가장 낮은 선수를 상대방 선수와 경기시킨다. 만약 상대방 선수가 한국팀의 모든 선수보다 레이팅이 높다면 남은 선수 중 가장 레이팅이 낮은 선수와 경기시킨다. 이 과정을 예제 입력에 적용. 1번 경기의 상대 선수는 한국팀의 모든 선수보다 레이팅이 높기 때문에 레이팅이 1800인 선수를 내보내야 한다. 그 후로는 각각 상대 선수를 이길 수 있는 선수 중 레이팅이 가장 낮은 선수를 선택하면 다섯 경기를 이길 수 잇다.
위와 같은 방법의 정당성을 증명하기 위해, 항상 우리가 하는 선택을 포함하는 최적해가 존재함을 증명하자. 각 경기에 대해 이 경기를 질 수 밖에 없는 경우, 그리고 이 경기를 이길 수 있는 경우로 나눠 우리의 선택이 옳다는 것을 보인다.
질 수 밖에 없는 경우 상대팀 선수가 모든 우리팀 선수보다 레이팅이 높을 경우
| 러시아 | ... | 999,999,999 | ... | x | ... | 1,900 |
| 한국 | ... | B | ... | A | ... | 2,000 |
B, A의 순서를 바꾼다면 이번 경기는 어차피 질테지만, A를 상대했던 선수 x는 레이팅이 더 높은 선수를 상대하게 된다. 따라서 승수가 더 줄어들 일은 없다. 이 경기에 A를 내보내는 최적해가 존재함을 알게 된다.
다음으로는 이 경기를 이길 수 있는 경우를 고려하자. 상대팀 선수보다 레이팅이 높거나 같은 우리 선수가 있다면 이 경기를 승리할 수 있다. 승리할 수 있는 선수 중 레이팅이 가장 낮은 A 대신 레이팅이 더 높은 B를 내보내는 최적해가 있다고 아래와 같이 가정.
| 러시아 | ... | 2,000 | ... | x | ... | 1,900 |
| 한국 | ... | B | ... | A | ... | 2,000 |
이 최적해에서 A와 B의 위치를 바꿨을 때, 어차피 승리할 테고 A를 상대했던 x는 레이팅이 더 높은 선수를 상대하게 된다. 같은 전개로 이 순서 또한 최적해임을 알 수 있다. 반대로 선수 A보다 레이팅이 더 낮은 선수를 내보내야 할 경우가 있을까 ? A대신 레이팅이 더 낮은 C를 내보내는 최적해가 있다고 가정 할때, 그러면 이 경기는 이길 수 있지만 지게 됩니다. 이 최적해에서 A와 C의 위치를 바꾸면 이 경기는 승리로 바뀝니다. A가 했던 경기는 C가 대신 해서 질 수도 있겠지만, 승수가 1 늘고 1 줄었으니 결과적으로는 여전히 최적해다.
이렇게 두 경우 모두 우리의 선택은 최다승을 보장한다는 사실을 알 수 있 습니다.
탐욕적 선택 속성을 증명하는 패턴이 있다. 이 패턴은 항상 우리가 선 택한 방법을 포함하는 최적해가 있음을 증명하기 위해, 우선 우리가 선택한 방법을 포함하지 않는 최적해의 존재를 가정한다. 그리고 이것을 적절히 조작해 우리가 선택한 방법을 포함하는 최적해를 만들어 낸다. 이와 같은 패턴은 탐욕법의 정당성을 증명할 때 자주 사용되니 주의깊게 봐두면 좋다.
첫 번째 경기에 나갈 선수를 선택하고 나면 남은 선수들을 경기에 배정하는 부분 문제를 얻을 수 있다. 이때 남은 경기에서도 당연히 최다승을 얻는 것이 좋으니 최적 부분구조도 자명하게 성립한다.
아직 출전하지 않은 선수들의 레이팅을 이진 검색 트리인 multiset에 저장하는 부분을 눈여겨 보면, 이로 인해 이길 수 있는 가장 레이팅이 낮은 선수를 찾는 작업과 선택한 선수의 레이팅을 삭제하는 작업 등을 모두 O(lgn)에 수행할 수 있다. 따라서 전체 시간복잡도는 O(nlgn)이 된다.
이진 검색트리를 사용하지 않았다. O(n²)
func order(russian: [Int], korean: [Int]) -> Int {
let n = russian.count
var wins = 0
// 아직 남아 있는 선수들의 레이팅
var rating = korean.sorted()
for rus in 0..<n {
// 가장 레이팅이 높은 한국 선수가 이길 수 없는 경우
// 가장 레이팅이 낮은 선수와 경기시킨다.
if rating.last! < russian[rus] {
rating.removeFirst()
} else {
for (i,v) in rating.enumerated() {
if v >= russian[rus] {
rating.remove(at: i)
break
}
}
wins += 1
}
}
return wins
}
print(order(russian: [1,2,3,4,5], korean: [1,2,3,4,2]))- 문제의 답을 만드는 과정을 여러 조각으로 나눈다.
- 각 조각마다 어떤 우선순위로 선택을 내려야 할지 결정한다. 이에 대한 직관을 얻기 위해서는 예제 입력이나 그외 작은 입력을 몇 개 손으로 풀어 보는 것이 효율적.
- 어떤 방식이 동작할 것 같으면 두가지 속성을 증명해 본다.
-
탐욕적 선택 속성: 항상 각 단계에서 우리가 선택한 답을 포함하는 최적해가 존재함을 보이면 된다. 이 증명은 대개 우리가 선택한 답과 다른 최적해가 존재함을 가정하고, 이것을 조작해서 우리가 선택한 답을 포함하는 최적해로 바꿀 수 있음을 보이는 형태로 이루어진다.
-
최적 부분 구조: 각 단계에서 항상 최적의 선택만을 했을 때 전체 최적해를 구할 수 있는지 여부를 증명한다. 다행히도 대개의 경우 이 속성이 성립하는지 아닌지는 자명하게 알 수 있다.
-
n개의 도시락을 주문했다. 전자레인지는 출력이 작기 때문에 한 번에 한 개의 도시락밖에 데울 수 없다.
i번째 도시락을 데우는 데는 mᵢ초가 걸리고, 먹는 데는 eᵢ초가 걸립니다.
도시락은 전자레인지 밖에 나오면 빠르게 식기 때문에, 도시락을 두 번에 나누어 데울 수는 없다. 예를 들어 데우는 데 20초 걸리는 도시락을 10초씩 나누어 데우기는 불가능합니다. 도시락은 식으면 맛이 없기 때문에, 각 사람은 자기 도시락을 다 데우는 대로 다른 사람들을 기다리지 않고 곧장 먹기 시작한다.
원석이는 점심을 먹는 데 걸리는 시간을 최소화하는 계획을 짜고 싶습니다. 점심을 먹는 데 걸리는 시간이란 첫 번째 도시락을 데우기 시작할 때부터 모든 사람이 도시락을 다 먹을 때까지 걸리는 시간을 의미합니다. 어느 순서로 도시락을 데워야 가장 빨리 점심시간을 마칠 수 있을지 결정하는 프로그램을 작성하세요.
프로그램은 10초 안에 실행되어야 하며, 64MB 이하의 메모리를 사용해야 합니다.
입력의 첫 줄에는 테스트 케이스의 수 C（C<=300）가 주어집니다. 각 테스트 케이스는 세 줄로 구성됩니다. 첫 줄에는 도시락의 수 n（l<=n<=10000）이 주어집니다. 두 번째 줄에는 n개의 정수로 각 도시락을 데우는 데 걸리는 시간이 주어지며, 세 번째 줄에는 역시 n개의 정수로 각 도시락을 먹는 데 걸리는 시간이 주어집니다.
각 테스트 케이스마다 한줄에 점심을 먹는 데 걸리는 최소 시간을 출력합니다. 이 값은 항상 2^31보다작습니다.
예제 입력
2
3
2 2 2
2 2 2
3
1 2 3
1 2 1
예제 출력
8
7
이런 형태의 스케쥴링 문제는 탐욕법의 문제에 자주 등장한다.
한 도시락을 먹을 때까지 걸리는 시간은 지금까지 데운 모든 도시락을 데우는 시간의 합에 이 도시락을 먹는데 걸리는 시간을 더한 것.
우리는 그중 가장 큰값(제일 늦게 다 먹는 도시락)을 최소화해야한다. 아래는 그에 대한 정의이다.
이때 P는 [0, 1, 2, ..., n-1]의 순열로, 각 도시락을 데우는 순서를 나타낸다.
좀더 단순한 형태의 문제를 고려해 보면 답의 구조를 짐작할 수있다. 모든 도시락을 먹는데 같은 시간 C가 걸린다고 먼저 가정해보면, 어떤 순서로 도시락을 데우건 점심 시간의 길이는 모든 도시락을 데우는 시간과 도시락 하나를 먹는 시간의 합 C + Σmᵢ 이란것을 알 수 있다. 마지막에 데우는 도시락을 결국 마지막에 먹게 된다.
그렇다면 n - 1개의 돈까스 도시락 사이에 먹는데 오래 걸리는 샤브샤브 도시락이 딱 하나 있다고 했을때, 먼저 데우는 것이 낫다. 마지막에 데우면 점심시간이 먹는 시간의 차이 만큼 길어지지만, 처음에 데우면 다른 도시락을 데우는 사이에 샤브샤브를 먹을 수 있으니 말이다. 이와 같은 전개에서 생각해보면 웬지 데우는 시간과는 관련 없이 먹는 데 오래 걸리는 도시락부터 데우는 것이 정답일 것 같다. 과연 그런지 증명해보자.
도시락의 목록이 주어질 때, 먹는 데 가장 오래 걸리는 샤브샤브 도시락을 제일 먼저 데우는 최적해가 반드시 하나는 있음을 보여 주면 된다. 이를 위해 다른 도시락, 예를 들어 돈까스 도시락을 제일 먼저 데우는 최적해가 존재한다고 가정하자.
| 번호 | 0 | ... | x | x+1 | ... | n-1 |
| 도시락 | 돈까스 | ... | 샤브샤브 | ... | ... | ... |
이 최적해에서 둘의 위치를 바꾼 뒤 이것도 최적해가 된다는 것을 보이도록 하자. 유의할 부분은 돈까스와 샤브샤브의 순서를 바꾼다 해도, x+1번 이후의 도시락들 입장에선 다를 것이 없다는 점이다. 어느 순서로 데우건 이 도시락이 기다려야하는 시간은 같다. 따라서 먹는 데 까지 걸리는 시간이 달라지는 도시락들은 샤브샤브까지, 그러니까 0번 부터 x번 까지의 도시락들이다. 따라서 나머지를 무시하고 이들만 고려하기로 한다.
| 번호 | 0 | ... | x |
| 도시락 | 돈까스 | ... | 샤브샤브 |
이때 이들 중 가장 마지막에 식사가 끝나는 도시락은 항상 샤브샤브라는 것을 주목하자. 그도 그럴 것이, 이 중 가장 늦게 데우는 데다 먹는 데 오래 걸리기 까지 한다. 샤브샤브를 먹는 사람이 식사가 끝나는 시간은 0번부터 x번 까지의 도시락을 데우는 시간과 샤브샤브를 먹는데 걸리는 시간의 합이다.
남은 도시락들의 순서를 자유롭게 바꾼다고 가정했을때, 어떤 도시락도 다 먹는 데 걸리는 시간이 앞에서 설명한 max값을 초과할 수 없다. 이 순서에서 y번째 도시락을 먹는 데 걸리는 시간은 다음과 같이 쓸 수 있다.
y번째 도시락은 샤브샤브보다 먹는 데 오래 걸리지 않을 테고, 더 오래 기다려야 하는 것도 아니기 때문에
위의 식이 max보다 클 수는 없다. 따라서 샤브샤브와 돈가스의 순서를 서로 바꾼 답이 최적해보다 나빠질 수는 없고, 따라서 이 답도 최적해라는 것을 알 수 있다.
첫 번째 도시락을 정하고 나면 나머지 도시락들을 배치해야 한다. 이때 각 도시락을 다 먹기까지 걸리는 시간은 첫 번째 도시락을 데우는 시간만큼 지연되지만, 남은 도시락들에 대해서도 가장 늦게 다 먹는 시간을 최소화해서 손해 볼것은 없다. 따라서 매 단계마다 최적의 선택을 해도 상관없다는 사실을 알 수 있다.
tuple이용과 e[i]의 부호를 뒤집어 넣어 역순 정렬을 좀더 간단하게 구현. 스위프트에서는 클로져에 부호표시로 간단하게 역순 정렬 가능. 그 이후에는 O(n)시간이 걸리는 간단한 시뮬레이션으로 답을 구한다. 전체 시간 복잡도는 O(nlgn)이 된다.
var n = 3
var e = [1, 2, 3]
var m = [1, 2, 1]
func heat() -> Int {
var order: [(Int, Int)] = []
for i in 0..<n {
order.append((e[i], i))
}
order.sort() {$0.0 < $1.0}
var ret = 0, beginEat = 0
for i in 0..<n {
let box = order[i].1
beginEat += m[box]
ret = max(ret, beginEat + e[box])
}
return ret
}
print(heat())프로그래밍 언어 c의 큰 문제점 중 하나는 언어 차원에서 문자열 변수형을 지원하지 않는다는 것. C에서는 문자 배열로 문자열을 표현하되 \0 (NULL)으로 문자열의 끝을 지정하는데, 문자열의 길이를 쉽게 알 수 있는 방법이 없기 때문에 여러 가지 문제가 발생하게 된다.
이런 문제 중 하나로 문자열을 조작하는 함수들의 동작 시간이 불필요하게 커진다는 것이 있다. 다음에 주어진 함수 strcat()은 문자열 dest 뒤에 src를 붙이는 함수인데, 실행 과정에서 반복문을 두 문자열의 길이를 합한 만큼 수행해야 한다. 이 함수를 사용해 두 문자열을 합치는 비용이 두 문자열의 길이의 합이라고 하자.
void strcat(char* dest, const char* src) {
// dest의 마지막 위치를 찾는다.
while(*dest) ++dest;
// src를 한 글자씩 dest에 옮겨 붙인다.
while(*src) *(dest++) = *(src++);
// 문자열의 끝을 알리는 \0을 추가한다.
*dest = 0;
}
이 함수를 이용해 n개의 문자열을 순서와 상관없이 합쳐서 한 개의 문자열로 만들고 싶다. 순서가 상관 없다는 말은 {al, go, spot}을 spotalgo로 합치든 alspotgo로 합치든 상관 없다는 의미. 그러나 문자열을 합치는 순서에 따라 전체 비용이 달라질 수 있습니다. 예를 들어 먼저 al과 go를 합치고 (2 + 2 = 4), 이것을 spot과 합치 면 (4 + 4 = 8) 총 12의 비용이 들지만 al과 spot을 합치고 (2 + 4 = 6) 이 것을 다시 go에 합치면 (6 + 2 = 8) 총 14의 비용이 필요.
n개의 문자열들의 길이가 주어질 때 필요한 최소 비용을 찾는 프로그램을 작성하세요.
프로그램은 1초 안에 실행되어야 하며, 64MB 이하의 메모리를 사용해야 합니다.
입력의 첫 줄에는 테스트 케이스의 수 C(C<=50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 문자열의 수 n(1 <= n <= 100)이 주어지며, 다음 줄에는 n개의 정수로 각 문자열의 길이가 주어집니다. 각문자열의 길이는 1,000 이하의 자연수입니다.
각 테스트 케이스마다 한 줄에 모든 문자열을 합칠 때 필요한 최소 반복문 수행 횟수를 출력한다.
3
3
2 2 4
5
3 1 3 4 1
8
1 1 1 1 1 1 1 2
12
26
27
위와 같이 트리 형태로 문자열들을 합치는 과정을 표현할 수 있다.
이 그림에서 맨 아래 원들은 입력에 주어진 문자열을 나타내고, 사각형들은 두 문자열을 합친 결과를 나타낸다. 각 사각형 안에 적힌 숫자는 합쳐진 문자열의 길이. 문자열을 합치는 데 드는 비용은 결과 문자열의 길이와 같기 때문에, 이 트리가 나타내는 병합 과정에 필요한 총 비용은 7 + 8 + 4 + 12 = 31이 된다.
이와 같은 그림에서 한 문자열이 전체 비용에 미치는 영향을 살펴보자. 문자열을 병합할 때마다 병합되는 문자열들의 총 길이가 전체 비용에 더해진다.
이때 합쳐진 결과 문자열의 길이를 원래 입력에 주어졌던 문자열별로 나눌 수 있다. 이렇게 각 비용을 분해해 보면 한 문자열로 인해 발생하는 총 비용은 이 문자열이 병합되는 횟수에 문자열의 길이를 곱한 것이라는 사실을 알 수 있다. 따라서 문자열이 길면 길수록 트리의 윗부분에 가깝고, 짧으면 짧을 수록 아래 쪽으로 내려가야 한다는 직관을 얻을 수 있다.
탐욕적 알고리즘은 문제의 답을 여러 조각으로 나눠 한 조각마다 한 가지의 선택을 한다. 이 문제에서는 한 조각마다 두 문자열을 서로 합치는 것. 문자열 목록에서 두 개를 골라내고, 이들을 합친 뒤 다시 문자열 목록에 추가하는 과정을 반복. 위의 트리로 이야기하자면 이것은 트리를 밑에서부터 만들어 나가는 접근이다. 이런 접근 방법을 아래서 위로 올라간다는 의미로 바텀업(Bottom-up)이라고 흔히 부른다.
- 거리가 같을 경우: x와 b의 위치를 서로 바꿔도 답은 변하지 않는다.
- 거리가 다를 경우: a, b 중 x에 더 가까운 쪽이 더 먼 쪽과 합쳐지도록 옮겨간다. 아래와같이 a가 b보다 먼 경우, b와 x의 위치를 바꾼다. x가 병합되는 횟수는 더 줄어들고,b가 병합되는 횟수는 그만큼 늘어난다. 그러나 x의 길이는 항상 b. 결과적으로는 항상 이득이거나 같은 비용이든다.
//문자열들의 길이가 주어질 때 하나로 합치는 최소 비용을 반환한다.
func concat(lengths: [Int]) -> Int {
var pq = [Int]()
for i in 0..<lengths.count {
pq.append(lengths[i])
}
var ret = 0
while (pq.count > 1) {
pq.sort(by: >) // 큐로 써야한다.
//가장 짧은 문자열 두 개를 찾아서 합치고 큐에 넣는다.
let min1 = pq.popLast()!
let min2 = pq.popLast()!
print(min1, min2)
pq.append(min1 + min2)
ret += (min1 + min2)
}
return ret
}
print(concat(lengths: [3, 1, 1, 3, 4]))이 문제는 사실 탐욕법의 유명한 예인 허프만 코드(Huffman code) 알고리즘을 각색한 것이다. 허프만 코드는 가변 길이 인코딩(variable-length encoding)테이블을 만드는 방법으로 여러 압축 알고리즘에 사용된다.
가변 길이 인코딩이란 원문의 각 글자를 서로 길이가 다를 수 있는 비트 패턴으로 바꿈으로써 원문의 길이를 줄이는 방법. 예를 들어 H → 01₂, E → 001₂, L → 1₂ , O → 000₂ 으로 각각 코드를 정했다면 HELLO는 0100111000₂로 압축되는 것. 따라서 자주 출현하는 글자는 더 짧은 패턴으로, 가끔만 출현하는 글자는 더 긴 패턴으로 배당할 필요가 있다. 허프만 코드는 원문에 출현하는 글자들의 출현 빈도가 주어질 때 예상 길이를 최소화하는 비트 패턴을 만들어 준다.
각 글자를 나타내는 인코딩은 내려가면서 만나는 간선들의 번호를 붙인 것. 이때 우리는 각 글자에 대해 출현 확률과 코드의 길이를 곱한 것의 합을 최소화 해야한다. 출현 확률이 문자열 길이로 바뀌었을 뿐 사실 우리가 푼 문제와 똑같다.
단 한 번도 함락된 적이 없다는 성채도시 미나스 아노르에는 반지름이 8킬로미터나 되는 거대한 원형 성벽, 람마스 에코르가 있습니다. 도시 전체를 감싸는 이 거대한 성벽에는 n개의 초소가 배치되어 있습니다. 각 초소들은 해당 위치를 중심으로 반지름 rᵢ의 원 내부를 감시할 수 있는데, 성벽의 구조 때문에 초소는 불규칙하게 배치되어 있고 초소마다 감시할 수 있는 범위도 모두 다릅니다. 위 그림에서 굵은 실선은 성벽, 별은 초소의 위치, 그리고 점선은 각 초소가 감시할 수 있는 영역을 나타냅니다. 최소의 인원으로 성벽의 모든 부분을 감시 하기 위해, 일부 초소에만 병사를 배치하려고 합니다. 각 초소의 위치와 감시 범위가 주어질 때, 성벽의 모든 부분을 감시하기 위해 필요한 최소한의 병사수를 계산하는 프로그램을 작성하세요.문제를 간단하게 하기 위해 성벽은 두께가 없는 원이고 초소는 점이라고 가정합니다.
프로그램은 2초 안에 실행되어야 하며, 64MB 이하의 메모리를 사용해야 합니다.
입력의 첫 줄에는 테스트 케이스의 수 C（C<=50）가 주어집니다. 각 테스트 케이스의 첫 줄에는 초소의 개수 n（l<=n<= 100）이 주어지며, 그 후 n줄에 각각 3개의 실수로 초소의 위치 yᵢ, xᵢ, 그리고 감시 범위 rᵢ（0 <= rᵢ <= 16.001）가 주어집니다. 성벽은 （0, 0）을 중심으로 하는 반지름 8인 원으로, 모든 초소는 이 성벽 위에 위치합니다.
각 테스트 케이스마다 한 줄에 필요한 병사의 최소 수를 출력합니다. 만약 어떻게 하더라도 성벽의 모든 부분을 감시할수 없다면 IMPOSSIBLE을 대신 출력합니다. 입력에 주어지는 초소의 좌표, 혹은 감시 범위가 최대 0.0000001만큼 변 하더 라도 답은 변하지 않는다고 가정 해도 좋습니다.
3
10
7.02066050 -3.83540431 4.0
-7.23257714 -3.41903904 2.0
0.00000000 -8.00000000 8.0
-8.00000000 -0.00000000 4.8
-6.47213595 4.70228202 3.2
-4.70228202 6.47213595 4.8
7.60845213 -2.47213595 1.6
-2.47213595 -7.60845213 8.8
6.47213595 4.70228202 7.6
-0.00000000 8.00000000 4.8
4
8.00000000 0.00000000 8.00
0.00000000 -8.00000000 8.00
-8.00000000 —0.00000000 8.00
1.25147572 7.90150672 5.40
1
8 0 15.99
5
4
IMPOSSIBLE
기하 문제에는 항상 수많은 예외들이 도사리고 있는데다, 실수 연산은 수많은 사람들의 발목을 잡는 주제이기 때문이다.
다행히 이 문제에서는 입력이 주어지는 실수가 아주 조금씩 늘어나거나 줄어들어도 답이 변하지 않는다고 명시하고 있다.
이것은 최적해의 두 초소의 감시 범위 끝이 정확하게 일치하는 경우가 없다는 뜻으로 해석할 수 있다.
수치적으로 안정적인 입력들만 주어지기 때문에 실수 연산에서 발생하는 오차에 대해서 크게 고민하지 않아도 된다.(알고리즘에만 정신차리고 하라는 뜻)
이 문제를 해결하는 과정은 원래 복잡한 문제를 가능한 한 풀기 쉬운 형태로 만드는 여러가지 변환으로 구성
이 문제를 풀 때 처음 해야 할 일은 2차원 평면의 도형들로 구성된 문제를 우리가 다루기 쉬운 꼴로 변형하는 것. 지금 이대로면 초소를 선택하지 못할 뿐더러 주어진 목록들이 성벽 전체를 감시할 수 잇는지 확인하기도 쉽지 않다. (IMPOSSIBLE)
각 초소에서 감시할 수 있는 성벽은 전체 중 연속된 일부분이란 사실에 주목해야 이 문제를 쉽게 재정의 할 수 있다. 위 그림을 봤을 때 굵은 점선으로 표시된 원의 호(arc)는 초소가 감시할 수 있는 성벽의 일부다. 원의 호를 표현할 수 있는 방법은 여러가지겠지만 여기서는 각 초소가 감시할 수 있는 구간을 호로 갖는 부채꼴의 중심각 [begin, end] 형태의 폐구간으로 표현하도록 하자. 이때 begin, end는 x축의 양의 방향으로부터 반시계 방향으로 잰다.
begin과 end를 계산하기 위해서는 (a)에 표시된 두 가지 값을 더 계산해야한다. loc는 x축의 양의 방향과 초소의 방향 사이의 각도이고, range는 초소에서 감시할 수 있는 범위가 loc 좌우로 얼마나 되는가를 나타낸다. 따라서 begin과 end는 각각 loc ± range로 구할 수 있다. 다행히 loc는 표준 삼각 함수인 atan2로부터 쉽게 구할 수 있다. atan2는 점 P=(y, x)를 입력받아, x축의 양의 방향과 선 OP 사이 의 각도를 [-𝝅, 𝝅] 구간 내 의 값으로 반환한다. 그러므로 loc를 다음과 같이 얻을 수 있다.
loc = atan2(y, x)
우리가 구해야 할 두 번째 값인 range도 간단히 구할 수 있다. 그림 (b)의 굵은 점선 삼각형은 초소의 위치, 감시 범위의 한쪽 끝, 그리고 원점을 잇고 있다. 이 삼각형은 두 변의 길이가 8인 이등변 삼각형으로, 다른 한 변의 길이는 초소의 감시 범위 r이다, r인 변을 이등분한 점에서 원점까지 선을 그으면 두 개의 직각 삼각형을 얻을 수 있다. 이때 각도 𝜽는 asin(r/2 * 1/8)로 구할 수 있다. 따라서
range = 2 * asin(r/16)
이렇게 표현하면 우리는 2차원 평면에 존재하는 원과 호 대신 중심각의 구간들을 다룰 수 있게 된다. 우리가 전체 원을 감시할 수 있는지 여부는 우리가 선택한 초소의 감시 영역의 합집합이 [0, 2𝝅]를 완전히 덮는지를 판단하면 된다.
아래는 초소의 위치 (y, x)와 감시 범위 r이 주어졌을 때 두 값을 구하는 코드를 보여준다. 각 구간이 덮는 범위는 tuple에 저장한다. 각 atan2() 반환 값은 [-𝝅, 𝝅] 범위 안에 있으므로 fmod()를 이용해 강제로 [0, 2𝝅] 범위로 바꾸지만, ranges에 들어가는 값은 [0, 2𝝅] 범위를 벗어날 수 있다는 점을 유의해라. 왜 이 값들을 [0, 2𝝅] 범위로 정규화하지 않는지는 다음에 다시 설명한다.
// 미나스 아노르 문제의 원들을 중심각의 구간으로 바꾸기
// math 쓰려고 사용
import Foundation
var pi: Double = 2.0 * acos(0)
var n : Int
var y = Array(repeating: Double(), count: 100)
var x = Array(repeating: Double(), count: 100)
var r = Array(repeating: Double(), count: 100)
var ranges = Array(repeating: (Double(), Double()), count: 100)
func convertToRange() {
for i in 0..<n {
let loc: Double = fmod(2*pi + atan2(y[i], x[i]), 2*pi)
let range: Double = 2.0 * asin(r[i] / 2.0 / 8.0)
ranges[i] = (loc - range, loc + range)
}
// 각 구간을 시작 위치가 작은 것부터 오게끔 정렬
ranges.sort(by:){$0.0 < $1.0}
}
print(ranges)
이렇게 각 초소들이 감시할 수 있는 범위를 중심각의 구간으로 만들고 나면, 이 문제는 이 구간들로 원 전체를 덮는 문제로 바뀝니다. 문제의 첫 번째 예제 입력을 이와 같이 변환한 결과를 위의 그림에서 확인할 수 있다. 우리는 점선들로 표시된 중심각 구간들을 이용해 굵은 실선으로 그려진 원을 덮어야 한다. 이처럼 원을 다루는 문제들을 풀 때 유용하게 쓸 수 있는 방법은 원을 적절한 위치에서 끊어서 선분 형태로 펴는 것이다. 많은 문제들이 끝과 끝이 이어져 있다는 제약을 제외하면 훨씬 풀기 쉬워지기 때문입니다. 예를 들어 원을 중심각 0인 지점에서 끊어서 선분 형태로 펴면 아래 그림을 얻을 수 있다. 이렇게 선형으로 변환된 문제를 푸는 것은 훨씬 간단하다.
물론 그렇다고 아무 데서나 무작정 원을 끊고 선형으로 변환된 문제를 풀 수 는 없다. 예를 들면 위의 그림에서는 주어진 구간들만으로 선분 전체를 덮기가 불가능. 선분의 오른쪽 끝 점을 덮는 구간이 하나도 없기 때문이다. 이 문제를 제대로 풀기 위해서는 선분의 왼쪽 끝을 넘어간 부분이 선분의 오른쪽 끝을 덮고 있음을 고려하는 알고리즘을 설계해야 한다. 이 문제를 푸는 방법은 문제가 되는 지점인 선분의 끝점, 즉 0을 따로 처리하는 것. 0을 덮는 구간을 하나 선택하면 이 구간이 덮지 못하는 나머지 부분은 이제 끝과 끝이 이어지지 않은 선분으로 펼 수 있다. 이 선분을 나머지 구간들로 덮는 문제를 해결하는 것이죠. 0을 포함하는 구간이 여러 개일 때는 이들을 하나하나 시도해 보고 그중 최소의 답을 반환하면 된다. 이 알고리즘의 정당성 증명은 여러 경우의 수를 복잡하게 따져야 하기 때문에, 간략히 개요만 설명한다.
이 알고리즘의 정당성을 이해하는 첫 번째 단서는 최적해가 0을 덮는 구간을 두 개 넘게 포함할 수 없다는 것입니다. 이것은 귀류법으로 쉽게 증명할 수 있다. 예를 들어 아래 그림같이 0을 덮는 구간이 최적해에 두 개 넘게 포함되어 있다고 가정할때, 이때 0에서 왼쪽으로 가장 멀리 가는 구간 하나, 오른쪽으로 가장 멀리 가는 구간을 하나씩 고른다. 그림에서라면 구간 A와 C가 되겠죠. 이 두 구간은 모든 구간의 합집합을 덮는다는 사실을 쉽게 알 수 있다. 따라서 남는 구간들은 삭제해도 되고, 우리의 답이 최적해라는 가정은 모순이 된다.
최적해에 0을 덮는 구간이 하나만 포함되어 있다면, 우리 알고리즘으로 최적해를 찾을 수 있음은 자명합니다. 0을 덮는 구간이 두 개 포함되어 있는 경우는 어떨까요? 이때는 두 구간의 중심（초소의 위치）이 0을 사이에 두는 경우와 아닌 경우를 나눠 봅시다. 0이 두 구간의 중심 사이에 있을 때는 둘 중 어느 구간을 선택하더라도 나머지 부분을 선분으로 펴서 풀면 최적해를 얻을 수 있습니다. 두 구간의 중심이 0을 사이에 두고 있지 않은 경우에는 그 중심이 0에 더 가까운 구간을 선택했을 때 최적해를 얻을 수 있다는 것을 증명할 수 있다.
아래는 이와 같은 알고리즘을 구현한 함수 solveCircular()를 보여줍니다. solveCircular()는 i번째 구간을 선택하고, 덮이지 않은 선분의 나머지 부분을 solveLinear()를 통해 덮는다. 아까 convertToRanges（）에서 정규화하지 않았던 범위를 이제는 정규화하는 것을 유의해 보세요. 만약 여기서도 정규화를 하지 않는다면 덮어야 할 중심각의 범위에서 시작 위치가 끝 위치보다 큰 등의 문제가 발생하게 된다. 또 하나 눈여겨볼 부분은 각 구간을 시작 위치의 오름차순으로 정렬해 두는 것입니다. 이들을 정렬해 두면 solveLinear()를 더 효율적으로 구현할 수 있기 때문.
let INF = 987654321
func solveCircular() -> Int {
var ret = INF
ranges.sort(by:){$0.0 < $1.0}
// 0을 덮을 구간을 선택
for i in 0..<n {
if ranges[i].0 <= 0 || ranges[i].1 >= 2*pi {
// 이 구간이 덮는 부분을 빼고 남는 중심각의 범위는 다음과 같다.
let begin: Double = fmod(ranges[i].1, 2*pi)
let end: Double = fmod(ranges[i].0 + 2*pi, 2*pi)
// [begin, end] 선분을 주어진 구간을 사용해 덮는다.
ret = min(ret, 1 + solveLinear(begin, end))
}
}
return ret
}이제야 비로소 문제가 충분히 간단해졌다. solveLinear()는 우리가 덮어야 할 선분 [begin, end]가 주어질 때, 구간 중 최소 몇 개를 선택해야 이를 전부 덮을 수 있는지를 반환한다. 그림 10.8과 같은 형태가 된다. 이 그림은 문제의 성질은 다르지만 회의실 예약 문제에서 그렸던 그림과 비슷하다. 회의실 예약 문제는 서로 겹치지 않도록 구간들을 가능한 한 많이 선택하는 문제였고, 이 문제는 구간들의 일부를 선택해 그 합집합이 선분을 모두 덮을 수 있도록 하는 것이므로. 그래서 비슷한 방법을 이용해 이 문제도 해결할 수 있다.
문제를 해결하는 단서는 선분의 왼쪽 끝 점을 어떤 구간으로 덮는 방법이 가장 좋을지 생각해 보는 것이다. 물론 이런 구간은 그림에서 보듯이 여러 개가 있을 수 있다. 이 중 어느 것을 사용하는 게 가장 이득일까? 선분의 왼쪽 끝을 넘어가는 부분은 의미가 없으므로, 가장 오른쪽으로 멀리 가는 구간을 택하는 방법이 가장 좋다는 사실을 어렵지 않게 알 수 있다. 그 후 덮인 부분을 선분에서 잘라내고 계속하면 된다.
탐욕적 선택 속성을 증명해 볼까요? 선분의 맨 왼쪽 점을 포함하는 구간 중 가장 오른쪽으로 멀리 가는 구간 a 대신 다른 구간 b를 선택해 최적해를 얻었다고 하자. 최적해에서 b를 빼고 a를 넣으면 크기가 같은 또 다른 답을 얻었음 을 알 수 있지요. 따라서 a를 포함하는 최적해는 반드시 존재합니다. 아래 코드는 앞에서 설명한 탐욕적 알고리즘의 구현을 보여줍니다. 이 알고리즘은 begin 전에 시작하는 구간 중 가장 오른쪽에서 끝나는 구간을 찾아내 이것으로 선분을 덮고, 덮인 부분을 잘라내는 일을 반복합니다. 각 구간이 시작 위치가 빠른 순서대로 정렬되어 있다고 가정하는 데 유의해라. 시작 위치 순서대로 정렬했기 때문에 각 구간을 한 번씩만 방문하면서 문제를 해결할 수 있다.
let INF = 987654321
// [begin, end] 구간을 덮기 위해 선택할 최소한의 구간 수를 반환한다.
// ranges는 시작 위치의 오름차순으로 정렬되어 있다고 가정
func solveLinear(_ begin: Double, _ end: Double) -> Int {
var begin = begin
var used = 0, idx = 0
// 덮지 못한 선분이 남아 있는 동안 계속
while (begin < end) {
//begin보다 이전에 시작하는 구간 중 가장 늦게 끝나는 구간을 찾는다
var maxCover: Double = -1
while (idx < n && ranges[idx].0 <= begin) {
maxCover = max(maxCover, ranges[idx].1)
idx += 1
}
//덮을 구간을 찾지 못한 경우
if maxCover <= begin { return INF }
// 선분의 덮인 부분을 잘라낸다
begin = maxCover
used += 1
}
return used
}이 알고리즘 전체의 시간복잡도는 얼마일까? 전처리와 정렬을 거친 후 호출하는 solveCircular() 함수는 solveLinear()를 최대 n번 호출한다. solveLinear() 함수는 2중 반복문을 가지고 있지만, 내부에 있는 while문은 n개의 구간에 대해 최대 한 번씩만 실행되기 때문에 내부 while문이 총 실행되는 횟수는 O（n）이다. 따라서 solveCircular()를 실행하는 데 드는 전체 시간 복 잡도는 0（n²）이 된다. 이것은 전처리에 드는 시간 O（n）과 정렬에 드는 시간 O（nlgn）보다 크기 때문에 전체 수행 시간을 지배하게 된다.