Tags

14 pages

빠른입출력

[Algorithm] cpp 백준 3311번: Traffic - SCC 압축과 DAG 구간 전파

섬 내부 도로망은 선분 도로가 교차하지 않는 평면 그래프이므로, SCC 압축 DAG에서 각 컴포넌트가 도달할 수 있는 동쪽 경계 정점 집합은 y좌표 기준 연속 구간이 됩니다. 이를 이용해 동쪽 경계 정점(서쪽에서 실제로 도달 가능한 것만)을 y 오름차순으로 인덱싱하고, 자식 구간을 부모로 병합하는 역위상 전파로 각 서쪽 정점의 답(서쪽 정점에서 도달 가능한 동쪽 정점 수)을 O(n+m)에 계산합니다. 구현은 반복형 Kosaraju + 압축 그래프 위상정렬 기반입니다.
[Algorithm] cpp 백준 3311번: Traffic - SCC 압축과 DAG 구간 전파

[Algorithm] C++ 백준 12898번 :Selling RNA Strands

백준 12898 Selling RNA Strands 문제를 접두사·접미사 조건을 각각 트라이 서브트리 구간으로 변환하고, 오일러 투어와 펜윅 트리(Fenwick/BIT)를 이용한 2D 직사각형 카운팅으로 M개의 질의를 빠르고 안정적으로 처리하는 C++ 풀이를 정리합니다. 대용량 입력을 위한 Fast I/O와 메모리 사용 최적화 포인트, 시간·공간 복잡도 분석까지 한 번에 확인할 수 있습니다.
[Algorithm] C++ 백준 12898번 :Selling RNA Strands