Byeo

개요 Boj 17435 - 합성함수와 쿼리는 중첩함수를 미리 계산해놓은 테이블을 갖고 얼마나 빨리 찾도록 구현할 수 있냐의 문제입니다. $f_n(x) = f(f(f(f(...f(x)...))))$ 를 구하는데 최적화하기 위해서 어떻게 사전에 계산해놓을 수 있을까요? 그 비결은 $f_{(a+b)}(x) = f_a(f_b(x))$ 에 있습니다. 그리고 몇몇 포인트들만 사전에 계산해두는 것이지요. 설명 $f_{(a+b)}(x)$ 는 풀어쓰면 $f$가 $a$번 중첩된 $f(f(....(f_b(x))))$로 풀어쓸 수 있습니다. 즉, $f_b(x)$의 값 $B$을 미리 계산해놓는다면 그 값에 단순히 $f_a(B)$를 구하면 최종 함수 값을 알 수 있지요. 이 문제는 그래서 $f_n(x)$에서 $n$의 2의 거듭제..

목차 개요 설명 코드 풀이 과정 개요 삼각함수를 이용해서 겹쳐진 두 원의 넓이를 구하는 문제입니다. 두 원이 존재할 수 있는 방법은 다음과 같이 세 가지 경우가 있습니다. 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$와 $..

목차 개요 요약 설명 코드 개요 이 문제는 Segment Tree 자료구조와 Sweeping 알고리즘을 함께 활용하여 풀어야 하는 문제입니다. 추가로 좌표의 범위가 상당히 넓기 때문에 ($0$ ~ $1,000,000,000$) 좌표 압축까지 병행해야 합니다. 문제의 Key Idea는 Segment Tree에 어떤 정보를 저장할 것이냐 입니다. 예를 들어, x축으로 Sweeping을 진행한다고 할 때, 직사각형의 넓이를 구하기 위해서는 각 x좌표 별로 직사각형에 포함되는 y영역과 그렇지 않은 영역을 구분해야 합니다. 이를 구분하기 위해서 기존 방식의 Segment Tree보다는 구간 Update query를 통해 현재 활성화 된 직사각형의 개수가 몇 개인지 구간 별로 관리하고, 넓이를 단번에 파악할 수 있..

목차 개요 설명 요약 코드 개요 이 문제는 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에 도착한 후 태..

목차 개요 설명 코드 개요 이 문제는 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..