devmoon

선분 교차 판단 알고리즘은 2차원 평면 위에서 두 선분이 주어졌을 때, 두 선분이 서로 교차하는지 교차하지 않는지 판단하는 알고리즘이다. 이 알고리즘을 학습하기 위해서 선행되어야 하는 기하 알고리즘이 있는데, 그 개념은 CCW이다. CCW (Counter Clock Wise)는 2차원 평면 위에 놓인 3개의 점에 대해서 어떤 방향성이 있는지 알려주며 이 방향성 정보를 사용해 선분이 서로 교차하는지 판단하게 된다. CCW 먼저 3개의 점으로 나타낼 수 있는 방향성의 종류에는 무엇이 있는지 알아봐야 한다. 3개의 점을 임의의 순서대로 이어서 나온 방향성은 아래와 같이 1) 시계 방향 2) 반시계 방향 3) 일직선 3종류가 있을 수 있다. 그러면 이제 3개의 각 점에 대한 좌표정보가 주어지면 그 방향성을 어떻..

1. 관련 문제 https://www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 2. Meet in the middle 최대 길이 40의 수열이 주어졌을 때, 이 수열의 원소들 중 몇 개를 중복되지 않게 선택하여 모두 더한 값이 S가 되도록 하는 경우의 수가 몇 개나 있는지 찾는 문제이다. 시간, 공간 복잡도를 생각하지 않고 간단하게 접근했을 때, 모든 원소들을 순회하면서 [포함 / 미포함]으로 둘 수 있기 때문에 최대 ..

1. 문제 출처 https://codeforces.com/contest/1594 Dashboard - Codeforces Round #747 (Div. 2) - Codeforces codeforces.com 2. 문제 A. Consecutive Sum Riddle / solved 정수 $n \; (1 \leq n \leq 10^{18})$이 주어졌을 때, $l$부터 $r$까지의 합이 $n$이 되는 $l$과 $r$을 출력하는 문제. $-k + k + (k + 1) = k + 1$ 인 점을 이용해서 문제를 해결할 수 있다. #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(..

1. 문제 출처 https://www.acmicpc.net/problem/17071 17071번: 숨바꼭질 5 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 2. 문제 접근 도착점이 고정되어 있는 일반적인 BFS문제와는 달리, 도착점도 동시에 이동하는 BFS문제 수빈이가 이동할 수 있는 경우는 다음 3가지밖에 없다. 현재 위치 x에서 1칸 좌측(x - 1)으로 이동 현재 위치 x에서 1칸 우측(x + 1)으로 이동 현재 위치 x에서 순간이동하여 2배 떨어진 위치(x * 2)로 이동 특정 위치 x에 ..