Byeo

목차 개요 요약 개요 설명 코드 테스트 케이스 개요 요약 y좌표가 높은 별부터 시작해서 아래로 sweeping을 합니다. 특정 별 A를 기준으로 좌상단에 별의 개수 $N$, 우상단에 별의 개수 $M$을 각각 segment tree를 통해 구한 후, 곱합니다. $N*M$이 별 A를 기준으로 그릴 수 있는 별자리 개수입니다. $N*M$은 별 A만을 기준으로 삼았을 때입니다. 이를 모든 별에 대해 구해 누적하면 됩니다. 같은 y좌표를 지닌 별들 간에는 별자리를 그릴 수 없습니다. 따라서 같은 y좌표를 가진 별자리들을 batching해서 처리하여야 합니다. 개요 이 문제는 [boj 5419 - 북서풍]을 푸셨다면 쉽게 응용할 수 있습니다. 마찬가지로 이번에는 위에서 아래 방향으로 훑어가면서 등장하는 별들의 x좌..

목차 개요 요약 개요 설명 코드 개요 요약 문제를 풀기위한 key point는 크게 다음과 같습니다. 북서풍을 타고 이동할 수 있는 섬의 쌍을 구하기 위해서는 각 섬마다 자신보다 왼쪽이면서 위에 있는 섬의 개수를 구해서 더하면 됩니다. 섬의 개수가 방대해서 일일이 구하기에는 시간복잡도가 큽니다. 따라서 sweeping과 segment tree를 활용하여 한 방향으로 섬 하나하나 sweep해가야 합니다. 이 과정에서 조건을 만족하는 섬의 개수를 segment tree를 통해 빠르게 알아냄과 동시에 자신을 segment tree에 등록하면 됩니다. Segment tree에 좌표를 사용하기에는 범위가 너무 넓습니다. 따라서 좌표 압축을 한 번 수행해서 20억 개의 원소가 아닌 75,000개의 원소 만으로도 해..

목차 개요 개요 3줄 요약 설명 코드 개요 이 문제는 [boj 2170 - 선 긋기]의 응용입니다. 다만 이를 어떻게 응용해야 할지 생각이 필요한 문제지요. 힌트는 "1) 수상택시가 N명의 모든 인원을 수용할 수 있고, 2) 0에서 출발해서 M까지는 무조건 가야 한다"입니다. 이를 곰곰이 생각해보면 모든 인원을 수용할 수 있으므로, 정방향 승객은 마치 일상의 버스처럼 시점에서 출발하여 승객의 출발점에 도착하면 태워주고, 승객의 목적지에 도착하면 내려주기만 하면 됩니다. 그 이후 종점에서 운행을 종료하죠. 즉, 정방향 승객은 어차피 수상 택시가 가는길이므로 고려할 필요가 없습니다. 이제 역방향을 생각해봐야 합니다. 10 → 5로 가는 승객의 경우 어떻게 하면 좋을까요? 일단 불가피하게 10에 도착한 후 태..

목차 개요 설명 일반화 코드 개요 스위핑 (Sweeping)은 "쓸다" 를 의미합니다. 스위핑 알고리즘 이란 말 그대로 한 쪽 방향부터 시작해서 다른 방향으로 스캔해가면서 쓸어가는 것이라고 보시면 됩니다. 이 알고리즘은 특정한 자료구조나 구체적인 코드가 있는 것은 아닙니다. 단지, 한쪽 방향에서 시작해서 다른 방향으로 차근차근 해결해 나가는 기법입니다. 이러한 특성 때문에, 보통 좌표와 관련있는 문제가 많이 보이는 듯 합니다. boj 2170 - 선 긋기 이 문제는 일직선상에 여러 길이의 선을 그어, 최종적으로 마지막에 그려져 있는 선의 길이를 구하는 문제입니다. 이 선끼리는 겹칠 수 있기 때문에 그린 길이의 총 합보다 그려져 있는 길이가 작거나 같을 수 밖에 없습니다. 여기서, 그릴 수 있는 좌표의 범..