Byeo

설명은 나중에... #include #include #include #include using namespace std; class Pos; int ccw(const Pos& a, const Pos& b, const Pos& c); bool straight_check(const Pos& a, const Pos& b, const Pos& c, const Pos& d); class Pos { public: int x, y; Pos(){}; Pos(int x_, int y_): x(x_), y(y_){}; bool operator

목차 개요 설명 코드 풀이 과정 개요 삼각함수를 이용해서 겹쳐진 두 원의 넓이를 구하는 문제입니다. 두 원이 존재할 수 있는 방법은 다음과 같이 세 가지 경우가 있습니다. 1) 두 원이 완전히 겹쳐지지 않은 경우 2) 일부가 겹친 경우 3) 한 원이 다른 원에 완전히 속한 경우 설명 먼저, 두 원의 원점 사이의 거리는 $d = \sqrt{(x_1-x_2)^2 + (y_1-y_2)^2}$ 입니다. 1) 두 원이 완전히 겹쳐지지 않은 경우 두 원이 겹쳐지지 않기 위한 조건은 $d > r1 + r2$ 입니다. 이 때, 겹치는 넓이는 $0$ 입니다. 2) 일부가 겹친 경우 두 원이 일부만 겹치기 위한 조건은 $|r1 - r2| < d < r1 + r2$ 입니다. 이 때, 부채꼴을 이루는 각 $\alpha$와 $..

목차 개요 설명 요약 코드 개요 이 문제는 2차원 좌표계에서 어느 직선상의 출발점에서 도착점까지 걸어서 혹은 점프로 가장 빠르게 도착하는 방법을 찾는 문제입니다. 가장 주의해야 할 점은 2차원 상에서 아무렇게 움직일 수 있다는 점입니다. 따라서 점프가 직선상에서만 국한된 것이 아닌, 직선에서 외부로 잠시 나갔다가 다시 도착점으로 점프하는게 최소 비용일 수 있습니다. 그래서 이 문제는 다음과 같이 케이스를 나눠서 풀면 됩니다. 1) 전부 걸어서 가는 경우 2) 처음부터 끝까지 점프해서 도착점에 딱 도착하는 경우 3) 도착점에서 가장 가까운 지점까지 점프한 뒤, 남은 거리는 걸어서 가는 경우 4) 도착점을 넘어서까지 점프를 한 뒤, 남은 거리는 걸어서 가는 경우 위 4가지를 모두 고려해서 계산한 뒤, 최솟값..

목차 개요 요약 개요 설명 코드 테스트 케이스 개요 요약 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 - 선 긋기 이 문제는 일직선상에 여러 길이의 선을 그어, 최종적으로 마지막에 그려져 있는 선의 길이를 구하는 문제입니다. 이 선끼리는 겹칠 수 있기 때문에 그린 길이의 총 합보다 그려져 있는 길이가 작거나 같을 수 밖에 없습니다. 여기서, 그릴 수 있는 좌표의 범..

목차 개요 설명 코드 개요 이 문제는 k 번째 원소를 효율적으로 찾는 문제입니다. 이는 segment tree를 사용하여 구할 수 있습니다. 이 문제는 [boj 12899-데이터 구조]와 굉장히 유사하므로 이를 참고하시면 됩니다. k 번째 원소를 segment tree를 이용해 효율적으로 찾는 방법은 [boj 12899-데이터 구조]를 참고하세요. 이 포스트에서는 k를 어떻게 계산해야 할 지에 대해서만 다루겠습니다. 설명 요세푸스 문제는 수열에서 일정한 간격으로 점프해 가면서 숫자들을 하나씩 빼낸 수열입니다. 백준의 예제 N = 7, K = 3의 경우에는 아래 그림을 보면 이해 하실 수 있으리라 생각합니다. 원소를 지우고 나면, 그 원소부터 다시 k개 만큼 뒤로 이동한 뒤에 또 그 원소를 지웁니다. 만약..

목차 개요 설명 코드 개요 해당 문제는 Segment Tree를 변형하여 사용하는 문제입니다. 이 문제에서 Segment Tree는 기존에 알던 부분 합, 부분 곱, 최소값, 최대값 등을 사용하는 것이 아니라 현재까지 어떤 query들이 어떤 구간에 영향을 주는 지를 저장하기 위해 사용합니다. 즉, 1 a b c 의 query가 들어오면, a ~ b 구간에 c라는 값을 더해야 합니다. 그런데 일일이 a, a+1, a+2, ..., b-1, b 까지 더하는 과정은 시간 소요가 크므로, a ~ b 구간을 담당하는 segment tree node에 일단 저장을 해놓습니다. 다음 2 a 의 query가 들어오면, root node부터 leaf node까지 내려가면서 그 동안 저장되어 있던 segment node..

목차 개요 설명 한계 코드 개요 해당 문제는 배열이 주어져 있을 때, 특정 부분의 구간 합을 구하는 문제입니다. 눈여겨 볼 것은 배열이 주어지고 난 뒤, 배열 값이 변하지 않는다는 사실입니다. 이 문제는 첫 index부터 마지막 index까지 부분합을 모두 계산한 뒤, 결과를 저장해서 빼기 연산으로 쉽게 풀 수 있습니다. 즉, DP 문제입니다. 설명 5 3 5 4 3 2 1 1 3 2 4 5 5 백준 예제로 방법을 간단하게 보겠습니다. 배열의 원소 5, 4, 3, 2, 1로 들어온 값을 arr에 저장해 둡시다. 그리고 0번 ~ i번 까지의 배열 합을 sum[i]에 저장해 놓도록 하죠. 처음 sum[0] 은 단순히 arr[0]이 되겠죠. 이제 다음부터 sum[1]은 arr[1] + sum[0], ... s..