수학10 [기하] 스윕 라인 알고리즘(교차점, 가까운 점, 볼록껍질) | 모르면 절대 못 품 먼저 2차원 거리 측정 함수로 맨해튼거리(택시거리), 유클리드 거리 두 가지가 있다는 것을 알아두자. 교차점의 개수 세기선분이 N개 있을 때, 교차점의 개수를 세는 문제이다. 이때 각각의 선분은 수평 선분이거나 수직 선분이다. O(N^2)으로 쉽게 풀 수 있지만 스윕 라인 알고리즘과 구간 질의 자료 구조를 사용하면 O(NlogN) 시간에 풀 수 있다. 선분이 시작하는 점과 끝나는 점을 가지고 이벤트 처리하는 것이라고 생각하면 된다. 가장 가까운 점 쌍 찾기점 N개가 있을 때 유클리드 거리가 최소인 두 점을 찾는 문제이다. 이 문제도 스윕 라인 알고리즘으로 O(NlogN) 시간에 해결할 수 있다. 점들을 왼쪽에서 오른쪽 순서로 살펴보면서 d라는 값을 관리해 나간다.d는 현재까지 구한 두 점 사이의 최소 거.. 2023. 6. 2. [알고리즘] 고오급 알고리즘 키워드 *블로그 주인만 알아볼 수 있음 주의* 삼진탐색으로 최솟값 찾기 함수의 최솟값이 x구간 [a,d] 구간 안에 있다고 하자. 구간을 같은 길이 [a,b], [b,c], [c,d]로 나누고 f(b)>f(c)가 성립함을 보인다. (미분) 합 최소화 abs(a1-x)+abs(a2-x)+ ... +abs(an-x) 의 최솟값으로 만드는 x의 최적해는 중앙값이다. 배열 원소가 짝수개라면 두 중앙값 사이 모든 값이 최적해가 된다. 트리의 지름 임의의 노드 a 선택, a에서 가장 먼 노드 b, b에서 가장 먼 노드 c를 구하면 b-c가 트리의 지름 트리 k번째 조상 찾기 ancestor(n,k) : n번 노드의 k번째 부모 가장 쉬운 방법은 k번 거슬러 올라가는 것인데 비효율적이다. k가 2의 거듭제곱인 모든 경우에 .. 2023. 6. 1. [기하] C++의 복소수 클래스 complex 기하 문제를 풀 때 c++의 복소수 클래스 complex를 사용할 수 있다. 이 클래스를 이용하면 점과 벡터를 복소수 형태로 표현할 수 있고, 클래스의 기능을 이용하여 점과 벡터를 다룰 수도 있다. typedef long long C; // 정수 좌표를 써도 되는 경우 // typedef long double C; // 정수 좌표를 쓸 수 없는 경우 typedef complex P; #define X real() #define Y imag() 정수 계산이 정확하기 때문에 정수좌표를 사용하는 것을 권장한다. 함수 complex 클래스에는 기하 문제를 풀 때 활용할 수 있는 함수를 제공한다. long double 자료형임을 주의하자. abs(v) 벡터 v={x, y}의 길이를 계산하는 함수이다. sqrt(x.. 2023. 6. 1. [기하] 벡터와 외적의 활용 외적 기하문제에서 요긴하게 사용되는 외적을 이용해 알고리즘을 공부하자. 외적 배운 지 까마득 하지만.....🤣 우선 두 벡터의 외적 값 자체의 해석을 알아보자. 1. a x b > 0 : b는 왼쪽으로 회전한다. 2. a x b = 0 : b는 회전하지 않는다 또는 180도 회전한다 (a와 b가 평행하다.) 3. a x b < 0 : b는 오른쪽으로 회전한다. 점의 위치 판별하기 외적을 이용하면 어떤 점이 직선의 왼쪽 혹은 오른쪽 중 어느 곳에 있는지를 판별할 수 있다. 직선이 두 점 a, b를 지난다고 가정하자. 이때 방향이 a, b를 향하고 있고, 주어진 점은 p라고 하자. (p - a) X (p - b)를 구하면 p의 위치를 알 수 있다. 외적이 양수라면 p가 선분 왼쪽에 있는 것이고, 외적이 음수.. 2023. 5. 31. [알고리즘] 분할정복으로 거듭제곱 최적화하기 프로그래밍에서 거듭제곱을 구하는 방법은 크게 세 가지이다. pow 내장함수 사용하기 double 실수 자료형을 사용해 거듭제곱을 반환하는 방법이다. 하지만 지수가 매우 클 때 정확성의 문제가 발생한다. 그 문제는 아래 글에서 확인 가능하다. C++ 기준 pow에 관한 글이다. 2023.04.30 - [TIL] - [C++] pow함수 double 형의 정확성 문제 [C++] pow함수 double 형의 정확성 문제 https://www.acmicpc.net/problem/1740 1740번: 거듭제곱 3의 제곱수를 생각하자. 3의 0제곱, 3의 1제곱, 3의 2제곱, ... 은 순서대로 1, 3, 9, 27, ... 이 된다. 이를 바탕으로, 한 개 이상의 서로 다른 3의 제곱수의 oozoowos.tis.. 2023. 5. 30. [정수론] 모듈러 연산과 증명 주의) 나눗셈 연산에서는 성립하지 않는다. 2023. 5. 29. [기하] 다각형 넓이 구하는 공식 다각형 넓이 구하기: 15 단계 (이미지 포함) - wikiHow 다각형의 넓이를 계산하는 일은 정삼각형 넓이를 구하는 것처럼 간단하기도 하지만 각 변의 길이가 다른 11각형의 넓이를 구하는 것처럼 복잡하기도 합니다. 다양한 다각형의 넓이를 구하는 방 ko.wikihow.com 1. 정다각형 2. 다각형 import sys;input=sys.stdin.readline n=int(input()) pairs=[list(map(int,input().split())) for i in range(n)] pairs.append(pairs[0]) x=y=0 for i in range(1,n+1): x += pairs[i][1] * pairs[i-1][0] y += pairs[i][0] * pairs[i-1][1] p.. 2023. 5. 28. [정수론] 페르마의 소정리 (모듈러 연산) 2023. 5. 26. 이전 1 2 다음
