[MIT] 파이썬을 이용한 알고리즘의 이해 - 일정 예약과 이진 탐색 트리

 

 

BoostCourse의 "[MIT]파이썬을 이용한 알고리즘의 이해" 강의 내용을 정리한 글입니다.

 

 

 

✔ 활주로 예약 시스템

• 활주로가 매우 혼잡하고 단 하나뿐인 공항(보스턴 6→1)
• 향후 착륙을 위한 "예약"
• 비행기가 착륙하면 대기 중인 사건 집합에서 제거하기
• 각각의 착륙 요청에는 "요청 예약 시간" t가 명시되어 있음
• t로부터 k분 전이나 k분 후에 다른 착륙 예약이 없다면, t를 집합에 추가함. k값은 변할 수 있음
  → 그 외의 경우는 에러로 보고, 예약을 잡지 않음

⁉️ 예시

R은 예약된 착륙 시간을 나타냄: R = (41, 46, 49, 56)과 k=3

착륙 시간 요청 : 44는 허용되지 않음(46∈R)

                          53 허용

                          20 허용되지 않음(이미 지난 시간)

                          |R| = n

목표 : 본 시스템을 O(log n) 시간 안에 효율적으로 운영

 

⁉️ 더 나은 방법은?

• 정렬되지 않은 리스트/배열
  : k분 떨어져 있는지 확인하는 데에 O(n)만큼 시간이 소요됩니다.
• 정렬된 배열
  : 이진 탐색을 이용하여 O(log n) 시간 안에 삽입하려는 위치를 찾을 수 있습니다. 이진 탐색을 이용하여 R[i] ≥ t를 만족하는 최소의 i 값을 찾을 수 있습니다.(예를 들면, 다음으로 큰 요소) 그다음 t에 대해 R[i]와 R[i-1] 비교합니다. 실제 삽입 과정에는 Θ(n) 시간이 소요되는 자리 이동 필요합니다.
• 최소-힙
  : O(log n) 시간 안에 삽입 가능합니다. 그러나 k분 떨어져 있는지 확인하는 데에는 O(n)시간만큼 소요됩니다.
• 정렬된 리스트
  : 추가 및 정렬에는 Θ(n log n) 시간이 소요됩니다. 추가와 정렬 과정을 하지 않고 새로운 시간/비행기를 삽입할 수 있습니다. 그러나 삽입에는 Θ(n)만큼 시간이 소요됩니다. 삽입 위치가 파악되기만 하면 k분 떨어져 있는지 확인하는 작업은 O(1) 안에 가능합니다.
• Dictionary 또는 Set
  : 삽입은 O(1)만큼 시간이 소요됩니다. k분 떨어져 있는지 확인하는 데에는 Ω(n)만큼 시간이 소요됩니다.

 

⁉️ 전체 분들을 다 저장하면 어떨까?

 이 트릭은 시간에 대해 인덱스된 큰 배열을 이용해 구현할 수 있습니다. 하지만 이 트릭은 임의의 정밀도 시간이나 착륙을 위해 너비 슬롯 확인에 대해서는 작동하지 않습니다.

⭐ 정렬된 리스트에 빠르게 삽입하는 것이 필요합니다.

 

 

 

✔ 이진 탐색 트리

⁉️ 특성

 이진 트리의 각 노드 x에는 키인 key(x)가 있습니다. 루트가 아닌 다른 노드는 부모인 p(x)가 있습니다. 노드에는 왼쪽 자식인 left(x)와 오른쪽 자식인 right(x)이 있습니다. 이것들은 힙과는 달리 포인터입니다.

⭐ 불변성 : 모든 노드 x와 x의 왼쪽 하위 트리에 있는 모든 노드 y에 대해서 key(y)≤key(x)입니다. 또한 x의 오른쪽 하위 트리에 있는 모든 노드 y에 대해 key(y)≥key(x)입니다.

 

⁉️ 삽입: insert(val)

 위의 그림과 같이 알맞은 위치를 찾을 때까지 왼쪽 및 오른쪽 포인터를 따라 내려갑니다. 삽입을 하는 도중에 활주로 예약 시스템에서 “k=3 내”에 다른 예약이 있는지 확인이 가능합니다. 루트에서부터 보았을 때, 삽입을 원하는 값의 k=3 이내에 있는 다른 요소를 발견하게 되면, 과정을 중단하고 삽입하지 않습니다.

 

⁉️ 이진 탐색 트리에 값이 존재하는 경우, 그 값 찾기 : find(val)

 값을 찾거나 NIL에 도달할 때까지 왼쪽과 오른쪽 포인터들을 따라갑니다.

 

⁉️ 이진 탐색 트리에서 최소 요소 찾기 : findmin()

 더 이상 왼쪽으로 갈 수 없을 때까지 왼쪽으로 가는 것이 중요합니다. 최댓값을 찾을 때에는 오른쪽으로 갑니다.

⭐ 복잡성 :  이진 탐색 트리의 높이가 h일 때, 모든 연산 과정에는 O(h)가 소요됩니다.

 

⁉️ 새로운 요구 조건

Rank(t): 시간≤t에 착륙 예정인 비행기는 몇 대일까? 새로운 요구 조건은 설계도의 수정을 필요로 합니다. 현재 우리가 가진 것으로는 효율적으로 해결할 수 없습니다. 하지만 전체적인 이진 탐색 트리 구조를 보완하면 가능합니다.

1. 원하는 시간을 찾기 위해 트리를 따라 내려오기
2. 노드의 값이 찾는 값보다 작다면 1 더하기
3. 왼쪽 서브 트리의 크기만큼 더하기

→ 전체적으로 이것은 O(h)만큼의 시간이 소요됩니다.