Tags

32 pages

ICPC

[Algorithm] cpp 백준 4001번: 미노타우르스 미궁

좌·우수법(Left/Right-hand rule)으로 정의되는 두 개의 표준 경로를 계산하고, 2차원 누적합으로 직사각형 내부 경로/장애물 포함 여부를 O(1)에 판정합니다. 각 좌표별로 ‘막히는 최소 정사각형 크기’와 ‘설치 가능한 최대 정사각형 크기’를 각각 이분 탐색해 교집합이 존재하면 정답 후보로 갱신하여, 가장 작은 변의 길이와 위치를 찾습니다.
[Algorithm] cpp 백준 4001번: 미노타우르스 미궁

[Algorithm] cpp-python 백준 9244번: 핀볼 - 스위프 라인

선분이 서로 교차하지 않는 핀볼 보드에서 x=x0로 공을 떨어뜨릴 때, 선분을 만난 뒤에는 더 낮은 끝점으로 흘러 다시 수직 낙하합니다. 스위프 라인과 활성 집합으로 각 선분 하단에서 바로 아래 선분을 연결해 흐름 그래프를 만든 뒤, 시작 x에서 최상단 선분부터 따라 내려가 O(N log N)으로 최종 x좌표를 구합니다. 정수 기하 비교로 오차 없이 안전하게 구현합니다.
[Algorithm] cpp-python 백준 9244번: 핀볼 - 스위프 라인

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

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

[Algorithm] C++ 백준 14737번 Dev, Please Add This!

격자에서 공을 상하좌우로 굴려 벽이나 가장자리에 닿을 때까지 이동하는 퍼즐에서, 모든 별을 하나의 플레이 순서로 획득할 수 있는지 판정한다. 단순 커버리지가 아니라 이동 순서 제약이 존재하므로 셀 단위 이동을 단방향 그래프로 모델링하고, 강한 연결 요소(SCC)로 압축한 DAG에서 상호 비가역(서로 도달 불가)한 컴포넌트 쌍의 동시 방문을 금지하는 제약과 각 별이 있는 칸의 행/열 중 하나의 정지 컴포넌트를 반드시 방문해야 한다는 제약을 2-SAT으로 구성해 모순 여부로 YES/NO를 결정한다. Kosaraju로 SCC를 구하고 DAG 도달성은 비트셋 DP로 처리하여 50×50까지 빠르게 동작한다.
[Algorithm] C++ 백준 14737번 Dev, Please Add This!