Tags

3 pages

이벤트 처리

[Algorithm] cpp 백준 11012번: Egg - 2D 직사각형 쿼리 스위핑+BIT

n개의 점과 m개의 직사각형 [l,r]×[b,t]가 주어질 때, 각 직사각형 안의 점 개수를 모두 합한 값을 구한다. x를 기준으로 오프라인 스위핑을 수행하고, y는 좌표 압축 후 펜윅 트리(Fenwick Tree)로 누적 빈도를 관리한다. 쿼리는 (r,+1),(l-1,−1) 이벤트로 분해해 포함-배제를 구현하여 총합을 O((n+m) log n)에 계산한다. 64비트 누적, 경계(b=0) 처리, 중복 좌표 대응을 주의한다.
[Algorithm] cpp 백준 11012번: Egg - 2D 직사각형 쿼리 스위핑+BIT

[Algorithm] cpp 백준 16670번: King Kog의 접견실 - 세그먼트 트리

기사들의 방문(도착 시각 t, 소요 d)이 실시간으로 추가/취소되는 상태에서 공주가 시각 t에 도착했을 때의 대기 시간을 즉시 구합니다. 누적 처리량 P(t)와 선형 시간 t를 결합한 백로그 공식 W(t) = (P(t) - t) - min_{u≤t}(P(u) - u) 를 활용하고, 좌표 압축 + 지연 전파 세그먼트 트리로 접수/취소는 suffix 가산, 질의는 점/구간 최소를 O(log N)에 처리해 q ≤ 3e5를 안정적으로 통과합니다.
[Algorithm] cpp 백준 16670번: King Kog의 접견실 - 세그먼트 트리

[Data Structure] C#에서의 Lock-Free 우선순위 큐 구현

동시성 프로그래밍에서 우선순위 큐는 중요한 자료구조로, 멀티스레드 환경에서 lock-free하고 thread-safe하게 구현하는 것이 필수적이다. 이 보고서는 C#에서 우선순위 큐를 구현하는 방법과 관련 개념, 문제 해결 기법을 다룬다. 우선순위 큐는 FIFO 큐와 달리 각 요소에 우선순위를 부여하여 처리 순서를 조정할 수 있는 장점이 있다.
[Data Structure] C#에서의 Lock-Free 우선순위 큐 구현