https://teferi.net/ 2026-04-16T19:13:25+00:00 https://teferi.net/ https://teferi.net/_media/wiki/dokuwiki.svg text/html 2023-04-25T06:23:25+00:00 Anonymous (anonymous@undisclosed.example.com) https://teferi.net/ps/%EC%9D%B4%EB%A1%A0/3%EC%B0%A8%EC%9B%90_%EA%B3%84%EC%82%B0_%EA%B8%B0%ED%95%98?rev=1682403805&do=diff 3차원 계산 기하 * 2차원에서 풀었던 계산기하 문제들은, 대부분 3차원이나 고차원으로 확장이 가능하고, 거기에 대응되는 알고리즘들도 무궁무진하다 * 하지만 다행히도 PS에 등장하는 기하 문제들은, 3차원 이상의 차원을 대상으로는 그렇게 고난이도의 지식까지 요구하는 경우는 드문것 같다$ {\mathbf {a}}\times {\mathbf {b}}={\hat {{\mathbf n}}}\left|{\mathbf {a}}\right|\left|{\mathbf {b}}\right|\sin \theta =[a_{2}b_{3}-a_{3}b_{2},a_{3}b_{1}-a_{1}b_{3},a_{1}b_{2}-a_{2}b_{1}] $$ {\displaystyle \mathbf {a} \cdot \mathbf {b} =a_{1}b_{1}+a_{2}b_{2}+\cdots +a_{n}b_{n}} $$ {\displaystyle \mathbf {a} \cdot \mathbf {b} =… text/html 2023-04-26T05:56:24+00:00 Anonymous (anonymous@undisclosed.example.com) https://teferi.net/ps/%EC%9D%B4%EB%A1%A0/%EA%B0%81%EB%8F%84_%EA%B8%B0%EC%A4%80_%EC%A0%95%EB%A0%AC?rev=1682488584&do=diff 점들을 각도를 기준으로 정렬 * 참고 * <https://mathsciforstudent.tistory.com/206#article-2-1-1--%EA%B7%B9-%EC%A0%95%EB%A0%AC> * 특정 좌표를 기준으로 했을 때의 각도 순으로 점들을 정렬한다. * 각도 순으로 정렬해 두면, 각도를 기준으로 스위핑, 이분 탐색, 투 포인터 등등의 테크닉을 그대로 사용할 수 있다. text/html 2026-04-01T09:02:48+00:00 Anonymous (anonymous@undisclosed.example.com) https://teferi.net/ps/%EC%9D%B4%EB%A1%A0/%EA%B5%AC%EA%B0%84_%EC%BF%BC%EB%A6%AC_%EB%AC%B8%EC%A0%9C?rev=1775034168&do=diff 구간 쿼리 문제 * 필요한 자료구조나 트릭에 대한 설명은 다른 페이지로 모아놓고, 여기에서는 쿼리 종류별로 어떻게 처리해야 할지에 대한 치트시트 비슷한 것을 만드려고 한다 * (X) 자료구조에 대한 설명 text/html 2024-09-13T09:16:26+00:00 Anonymous (anonymous@undisclosed.example.com) https://teferi.net/ps/%EC%9D%B4%EB%A1%A0/%EA%B8%B0%EC%B4%88_%EA%B3%84%EC%82%B0%EA%B8%B0%ED%95%98?rev=1726218986&do=diff 기초 계산기하 * 계산기하 기초 * 참고 * <https://zigui.tistory.com/34> * <https://mathsciforstudent.tistory.com/206> * 계산기하의 어려운 점 * 실수형을 반드시 사용해야 하는 경우가 많고, 그로 인해 실수 오차를 고려해야 한다 * 예외처리가 복잡하다. text/html 2023-04-09T14:07:12+00:00 Anonymous (anonymous@undisclosed.example.com) https://teferi.net/ps/%EC%9D%B4%EB%A1%A0/%EA%B8%B0%ED%95%98%ED%95%99?rev=1681049232&do=diff 기하학 * 잘 알고있는 대로 공간과 도형을 연구하는 분야가 기하학이다. * 그리고, 컴퓨터과학에서 기하학에 관한 알고리즘을 연구하는 분야는 계산기하라고 부른다. 기초 기하학 * 알고리즘과 관계 없는 순수 기하학적 지식.. text/html 2023-04-19T06:37:00+00:00 Anonymous (anonymous@undisclosed.example.com) https://teferi.net/ps/%EC%9D%B4%EB%A1%A0/%EB%8B%A4%EA%B0%81%ED%98%95?rev=1681886220&do=diff 다각형 (Polygon) * 놀랍게도 '다각형'의 정의는 한 평면 위에 있으면서 유한개의 선분들이 차례로 이어져 이루어진 경로이다. 변들끼리 교차하더라도 다각형이 될 수 있다. * 우리가 보통 생각하는 형태의 다각형, 즉 변들이 꼭짓점에서만 만나는 다각형은 '$ {\displaystyle A={\frac {1}{2}}\sum _{i=1}^{n}(x_{i}y_{i+1}-x_{i+1}y_{i})} $$ {\displaystyle A={\frac {1}{2}}\sum _{i=1}^{n}(y_{i}+y_{i+1})(x_{i}-x_{i+1})} $$ {\displaystyle A={\frac {1}{2}}\sum _{i=1}^{n}x_{i}(y_{i+1}-y_{i-1})} $$ S = I + B / 2 - 1 $… text/html 2023-06-05T06:01:36+00:00 Anonymous (anonymous@undisclosed.example.com) https://teferi.net/ps/%EC%9D%B4%EB%A1%A0/%EB%8B%A4%EB%A5%B8_%EC%96%B8%EC%96%B4%EB%93%A4%EA%B3%BC_%EA%B3%84%EC%82%B0%EA%B0%92%EC%9D%B4_%EB%8B%A4%EB%A5%B8_%EA%B2%BD%EC%9A%B0?rev=1685944896&do=diff 다른 언어들과 계산값이 다른 경우 반올림 * 한줄요약 * CPP의 cmath.h의 round 함수는 Half away from zero 방식으로 구현되어있고, 이게 우리가 보통 생각하는 것과 비슷한 방식이다. * Python의 round 함수는 Half to even 형식으로 구현되어있다. 결과값이 다를수 있다 text/html 2023-04-11T07:41:04+00:00 Anonymous (anonymous@undisclosed.example.com) https://teferi.net/ps/%EC%9D%B4%EB%A1%A0/%EB%A1%9C%ED%85%8C%EC%9D%B4%ED%8C%85_%EC%BA%98%EB%A6%AC%ED%8D%BC%EC%8A%A4?rev=1681198864&do=diff 로테이팅 캘리퍼스 (Rotating Calipers) * 참고 * rotating calipers * <https://lem0nad3.tistory.com/131> * <https://stonejjun.tistory.com/140> * 캘리퍼스는 학교에서 '버니어 캘리퍼스'라고 배웠던 그 도구가 맞다. 알고리즘 동작 과정이 다각형에 캘리퍼스를 돌리는것과 비슷하다고 해서 붙은 이름이다. text/html 2023-05-26T07:43:20+00:00 Anonymous (anonymous@undisclosed.example.com) https://teferi.net/ps/%EC%9D%B4%EB%A1%A0/%EB%B3%BC%EB%A1%9D_%EA%BB%8D%EC%A7%88?rev=1685087000&do=diff 볼록 껍질 (Convex Hull) * 난이도: 플래티넘 5 * 기본 문제: 1708 * 참고 자료 * <https://cp-algorithms.com/geometry/convex-hull.html> 개요 * 정의는 '모든 점을 포함하는 가장 작은 볼록다각형' 이다. * 작다는 것은, 면적을 기준으로 해도 되고, 둘레의 길이를 기준으로 해도 된다. text/html 2023-04-17T03:48:51+00:00 Anonymous (anonymous@undisclosed.example.com) https://teferi.net/ps/%EC%9D%B4%EB%A1%A0/%EB%B9%A0%EB%A5%B8_%EB%AA%A8%EB%93%88%EB%9F%AC_%EC%97%B0%EC%82%B0?rev=1681703331&do=diff 빠른 모듈로 연산 - 난이도: 다이아몬드 5 - 기본 문제: 17467 * 일반적인 CPU 구조에서 모듈로 연산을 처리하는 것은, 다른 연산들 (덧셈,뺄셈,곱셈,비트연산)에 비해서 매우 느리다. 그래서 모듈로 연산을 회피하는 것이 성능 향상에 중요하다. text/html 2023-04-10T08:45:08+00:00 Anonymous (anonymous@undisclosed.example.com) https://teferi.net/ps/%EC%9D%B4%EB%A1%A0/%EC%84%A0%EB%B6%84_%EA%B5%90%EC%B0%A8?rev=1681116308&do=diff 선분 교차 * 두개의 선분이 서로 교차하는지 여부를 찾는 문제이다. * 먼저 용어 정의를 깔끔하게 하자. * disjoint는 두 선분에 공통으로 포함되는 점이 존재하지 않는것으로, intersecting는 두 선분에 공통으로 포함되는 점이 존재하는 것으로 정의하자. 그러면 intersecting도 다시 여러가지 경우로 나눌수 있다. text/html 2023-04-17T01:40:20+00:00 Anonymous (anonymous@undisclosed.example.com) https://teferi.net/ps/%EC%9D%B4%EB%A1%A0/%EC%9A%A9%EC%96%B4_%EC%A0%95%EB%A6%AC?rev=1681695620&do=diff 용어 정리 * 나눗셈 연산은 division 이다. * a ÷ b 에서, a는 dividend, b는 divisor 이다 * 몫과 나머지를 같이 얻는 나눗셈을 division with remainders 또는 Euclidean division이라고 한다. * quotient는 일반 나눗셈에서의 결과, 또는 Euclidean division에서의 몫이 된다 text/html 2025-02-24T05:01:09+00:00 Anonymous (anonymous@undisclosed.example.com) https://teferi.net/ps/%EC%9D%B4%EB%A1%A0/%EC%9B%90?rev=1740373269&do=diff text/html 2024-07-22T07:18:31+00:00 Anonymous (anonymous@undisclosed.example.com) https://teferi.net/ps/%EC%9D%B4%EB%A1%A0/apsp?rev=1721632711&do=diff 전체쌍 최단 경로 문제 (All-pairs shortest paths; APSP) * 위키피디아 참고 * 그래프의 모든 정점쌍 사이의 최단 경로를 전부 구하는 문제이다. * Q개의 정점쌍에 대해서 최단 경로를 구해야 하는 문제나 (Q가 거의 n^2에 가깝게 크게 들어온다), 모든 정점쌍 사이의 거리중에서 최적값을 찾는 등의 문제가 있다.$ \max_{u,v}{dist(u,v)} $$ \min_u\max_v{dist(u,v)} $$ \text{argmin}_u\max_v{dist(u,v)} $$ \min_u \sum_v dist(s, t) $… text/html 2023-04-11T13:27:40+00:00 Anonymous (anonymous@undisclosed.example.com) https://teferi.net/ps/%EC%9D%B4%EB%A1%A0/boj%EC%9D%98_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98_%EB%B6%84%EB%A5%98?rev=1681219660&do=diff 알고리즘 분류 태그관련 문서기본 난이도기하학 (Geometry) 기하학 브5볼록 껍질 (Convex Hull) 볼록 껍질 (Convex Hull) 플5선분 교차 판정 (Line Segment Intersection Check) 선분 교차 골3피타고라스 정리 (Pythagoras Theorem) X 브4다각형의 넓이 (Area Of A Polygon) 다각형 골5 볼록 다각형 내부의 점 판정 (Point In Convex Polygon Check) 다각형 ?회전하는 캘리퍼스 (Rotating Calipers) 로테이팅 캘리퍼스 (Rotating Calipers) ?오목 다각형 내부의 점 판정 (Point In Non-convex Polygon Check) X ? 픽의 정리 (Pick's Theorem) 다각형 ?…