Collections

242 pages

Algorithm

백준 알고리즘 문제 풀이를 다루며, Python과 C++ 언어로 작성된 코드와 문제 해결 과정을 공유하는 공간이다. '삶, 우주, 그리고 모든 것'에 대한 해답을 찾아가는 마음으로, 알고리즘의 매력을 느끼고 싶은 모든 이를 위해 다양한 풀이를 준비하고 있다. 초심자부터 고급 개발자까지 누구나 문제 해결을 통해 깊이 있는 사고를 키워나갈 수 있도록 꾸준히 업데이트하고 있다

[Algorithm] cpp 백준 10076번: 휴가 - 최적 풀이

IOI 2014 Holiday(휴가) 최적 풀이. 선형 도시에서 하루에 이동 또는 방문만 가능한 제약에서 방문 관광지 수를 최대화한다. 이동은 한 번의 방향 전환만 해도 충분하다는 관찰 아래 [l,r] 구간을 잡고 체류 가능일 g(l,r)을 계산한다. 분할정복+세그먼트 트리로 상위 k 합을 빠르게 질의하여 O(N log^2 N)로 해결한다. 경계·중복·음수 k 처리와 좌우 반전까지 구현 체크리스트 포함.
[Algorithm] cpp 백준 10076번: 휴가 - 최적 풀이

[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