철로 문제는 우선순위 큐와 그리디 알고리즘을 활용하여 효율적으로 해결할 수 있는 문제이다. 수평선 상에 위치한 여러 사람들의 집과 사무실 위치가 주어질 때, 일정한 길이의 철로를 적절히 배치하여 최대한 많은 사람들이 철로를 이용할 수 있도록 하는 것이 목표이다. 이 글에서는 해당 문제를 해결하기 위한 접근 방법과 C++ 및 Python 코드 구현을 상세하게 설명한다.
#include<iostream>#include<vector>#include<algorithm>#include<queue>usingnamespacestd;// 집과 사무실 위치를 나타내는 구조체
structInterval{longlongstart;longlongend;};intmain(){intn;scanf("%d",&n);vector<Interval>intervals;// 입력 받기
for(inti=0;i<n;++i){longlongh,o;scanf("%lld %lld",&h,&o);longlonga=min(h,o);longlongb=max(h,o);intervals.push_back({a,b});}longlongd;scanf("%lld",&d);// 유효한 인터벌 필터링
vector<Interval>validIntervals;for(auto&interval:intervals){if(interval.end-interval.start<=d){validIntervals.push_back(interval);}}// 끝점을 기준으로 오름차순 정렬
sort(validIntervals.begin(),validIntervals.end(),[](constInterval&a,constInterval&b){returna.end<b.end;});// 최소 힙 선언
priority_queue<longlong,vector<longlong>,greater<longlong>>minHeap;intmaxCount=0;// 스위핑 수행
for(auto&interval:validIntervals){minHeap.push(interval.start);// 힙에서 유효하지 않은 시작점 제거
while(!minHeap.empty()&&minHeap.top()<interval.end-d){minHeap.pop();}// 현재 힙 크기가 해당 구간에 포함되는 사람 수
intcurrentCount=minHeap.size();if(currentCount>maxCount){maxCount=currentCount;}}printf("%d\n",maxCount);return0;}
코드 설명
입력 처리:
사람 수 n을 입력받는다.
각 사람의 집 h와 사무실 o 위치를 입력받아, 시작점과 끝점으로 구성된 Interval을 생성한다.
유효한 인터벌 필터링:
각 인터벌의 길이가 d 이하인 경우만 validIntervals에 추가한다.
인터벌 정렬:
validIntervals를 끝점을 기준으로 오름차순 정렬한다.
스위핑과 힙 사용:
최소 힙 minHeap을 사용하여 시작점을 관리한다.
현재 인터벌의 끝점에서 길이 d를 뺀 값보다 작은 시작점을 가진 인터벌들은 힙에서 제거한다.
힙의 크기는 현재 구간에 포함되는 사람들의 수이며, 이를 이용하여 maxCount를 갱신한다.
importsysimportheapq# 입력을 빠르게 받기 위해 readline 사용input=sys.stdin.readlinen=int(input())intervals=[]# 입력 받기for_inrange(n):h,o=map(int,input().split())a,b=min(h,o),max(h,o)intervals.append((a,b))d=int(input())# 유효한 인터벌 필터링valid_intervals=[(a,b)fora,binintervalsifb-a<=d]# 끝점을 기준으로 정렬valid_intervals.sort(key=lambdax:x[1])min_heap=[]max_count=0# 스위핑 수행forstart,endinvalid_intervals:heapq.heappush(min_heap,start)# 힙에서 유효하지 않은 시작점 제거whilemin_heapandmin_heap[0]<end-d:heapq.heappop(min_heap)current_count=len(min_heap)ifcurrent_count>max_count:max_count=current_countprint(max_count)
코드 설명
입력 처리:
sys.stdin.readline을 사용하여 입력을 빠르게 받는다.
각 사람의 집과 사무실 위치를 입력받아 (시작점, 끝점) 형태의 튜플로 저장한다.
유효한 인터벌 필터링:
리스트 컴프리헨션을 사용하여 길이가 d 이하인 인터벌만 선택한다.
인터벌 정렬:
sort 함수를 사용하여 끝점을 기준으로 인터벌을 정렬한다.
스위핑과 힙 사용:
heapq 모듈의 heappush와 heappop을 사용하여 최소 힙을 구현한다.
힙에 시작점을 추가하고, 필요에 따라 힙에서 제거하면서 최대 인원 수를 갱신한다.
결과 출력:
최대 인원 수를 출력한다.
결론
이 문제는 스위핑 기법과 우선순위 큐를 활용한 그리디 알고리즘의 전형적인 예시이다. 인터벌을 끝점을 기준으로 정렬하고, 최소 힙을 사용하여 시작점을 관리함으로써 효율적으로 최대 인원 수를 계산할 수 있었다. 이를 통해 시간 복잡도를 O(n log n)으로 유지하면서도 큰 입력에 대해 빠르게 동작하는 코드를 작성할 수 있었다.
이번 문제를 통해 인터벌 스케줄링과 우선순위 큐의 활용 방법을 더욱 깊이 있게 이해할 수 있었다. 또한, 라이브러리를 사용할 수 없는 환경에서도 기본적인 자료구조와 알고리즘을 직접 구현하는 연습이 되었으며, 이는 알고리즘 문제 해결 능력을 향상시키는 데 큰 도움이 되었다.