1. 문제 18044번: Polygon (acmicpc.net) 18044번: Polygon You are given n segments of lengths ℓ1, ℓ2, . . . , ℓn, respectively. Determine the largest possible circumference of a convex polygon that can be constructed using these segments (in any order, and not neccessarily all of them). The polygon must be www.acmicpc.net 2. 풀이 convex polygon은 앞으로 배울것 같지만... 지금은 모든 내각이 180도보다 작거나 같은 도형이라고 이해하면 될 것 같다 ..
1. 문제 16931번: 겉넓이 구하기 (acmicpc.net) 16931번: 겉넓이 구하기 크기가 N×M인 종이가 있고, 종이는 1×1크기의 칸으로 나누어져 있다. 이 종이의 각 칸 위에 1×1×1 크기의 정육면체를 놓아 3차원 도형을 만들었다. 종이의 각 칸에 놓인 정육면체의 개수가 주어 www.acmicpc.net 2. 풀이 위,아래, 앞,뒤,왼쪽,오른쪽에서 보이는 면의 개수를 전부 더하면 될 것이며 면의 개수는 어떻게 구하지? n*m 크기의 바닥 아래에 정육면체를 쌓았을때, 위나 아래에서 봤을때는? 당연히 n*m개씩 보일 것이다. 왼쪽과 오른쪽에서 봤을때는? 위 그림이 1 3 4 2 2 3 1 2 4 와 같이 주어지는데, 왼쪽에서 본다면, 1 3 4 >>>>>> 2 2 3 1 2 4 처럼 상상해본..
1. 모든 점까지 맨해튼 거리의 합이 최소가 되는 점의 위치? m차원의 n개의 점들 $P_{1}(x_{11},x_{12},...,x_{1m}), ... P_{n}(x_{n1},x_{n2},...,x_{nm})$에 대하여, 이들까지 맨해튼 거리의 합이 최소가 되는 점 X의 좌표를 구하라고 한다면, 어떻게 구할 수 있을까? 정답은 n개의 점들을 1,2,...,m차원의 좌표 값에 대하여 정렬한 다음, 중앙값에 해당하는 점의 좌표 $P_{median}$이 된다. 직관적으로 쉽게 눈치챌 수 있기는 한데, 왜 그런지 생각해보자. 2. 증명 먼저 점들의 좌표가 합에 서로 영향을 주지 않는다는 점을 관찰하자. 예를 들어 (3,5), (4,2), (5,1)에 대하여 (x,y)까지 맨해튼 거리의 합은.. $|x-3| + ..
1. 문제 21203번: Distance (acmicpc.net) 21203번: Distance The City of Manhattan is organized as a grid of streets and avenues, with streets running in the North-South direction and avenues running in the East-West direction. Streets are numbered from East to West starting from 1, and avenues are numbered from N www.acmicpc.net 2. 풀이 n 제한이 20만이라 모든 좌표쌍 일일이 정해서 거리를 구해보는 방법으로는 어림도 없다 https://www.geeksf..
https://rebro.kr/10 CCW (Counter-ClockWise) - (1) CCW (Counter-ClockWise) - (1) CCW 알고리즘은 수 계산에서의 사칙연산처럼, '기하 알고리즘'에서 가장 기본적인 알고리즘이다. 즉, 기하 알고리즘에서 매우 자주 이용된다는 뜻이다. 우선 이 게시글에서 rebro.kr https://gaussian37.github.io/math-algorithm-ccw/ CCW(counter clockwise) gaussian37's blog gaussian37.github.io https://snowfleur.tistory.com/98 [알고리즘] CCW(Counter Clock Wise) 알고리즘 개요 및 소개 CCW( Counter Clock Wise) 알..
https://gaussian37.github.io/math-la-cross-product/ 벡터의 외적이란? gaussian37's blog gaussian37.github.io https://cp-algorithms.com/geometry/basic-geometry.html#definition_1 Basic Geometry - Algorithms for Competitive Programming Basic Geometry In this article we will consider basic operations on points in Euclidean space which maintains the foundation of the whole analytical geometry. We will consid..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
