재배열 부등식(rearrangement inequality)을 이용한 내적의 최대 최소

1. 재배열 부등식(rearrangement inequality) 실수 $x_{1}  1,2,..,n의 임의의 순열$\sigma_{1}, \sigma_{2}, ... , \sigma_{n}$으로부터$$x_{1}y_{n} + x_{2}y_{n-1} + ... + x_{n}y_{1}   2. 증명$S1 = x_{1}y_{1} + x_{2}y_{2} + .... + x_{a}y_{a} + .... + x_{b}y_{b} + ... + x_{n}y_{n}$에서$y_{a}  $S2 = x_{1}y_{1} + x_{2}y_{2} + ... + x_{a}y_{b} + ... + x_{b}y_{a} + ... + x_{n}y_{n}$ 둘을 뺴면 $S1 - S2 = x_{a}(y_{a} - y_{b}) + x_{..

• format_list_bulleted 그리디 알고리즘
• · 2024. 11. 22.
• textsms

가로 세로 선 3개만 그어서 모든 점을 덮을 수 있는가?

5884번: 감시 카메라 n개의 점이 있는데 수직선이나 수평선으로 3개만 그어서 모든 점을 덮을 수 있는지 체크하는 문제 점의 좌표 범위가 10^9이다 보니 하나하나 다 그어보면 당연히 시간초과 날것이고 X좌표를 기준으로 그룹을 묶고, Y좌표를 기준으로 그룹을 묶는다 그러면 어떤 X = x좌표를 기준으로 수직선을 그어보면, 해당하는 y좌표들을 알 수 있다 그러면 그러한 y좌표가 여러개 있다면?  Y = y로 수평선을 또 그어야할 것이다   근데 해당하는 Y = y2가 하나만 존재한다면 Y = y2로 수평선을 그을 필요가 없다   그러므로 모든 X = x에 대해 순회해봐서 x에 대응하는 y들을 다시 하나씩 순회해본 다음 해당하는 y좌표값들 개수가 2개 이상인 경우가 존재하면 그 쪽으로 수평선을 그어야하므로..

• format_list_bulleted 브루트포스
• · 2024. 11. 18.
• textsms

수천개의 점들 중에서 가장 넓이가 큰 정사각형을 찾는 방법

9015번: 정사각형 점이 n개  그냥 한다면 O(N^4)이겠지만 당연히 안될거고 O(N^3)인 방법도 있긴한데 N  정사각형 성질을 이용하면.. 임의의 두 점 A(x1,y1), B(x2,y2)을 먼저 잡고 벡터 AB를 구한다 벡터 AB = OB - OA = (x2-x1, y2-y1)으로 구할 수 있다   다음 벡터 AB를 시계방향으로 90도 회전하면 벡터 AD를 구할 수 있다 90도 회전하는 방법은? (x,y) >> (-y,x)로 되므로 벡터 AD = (-y2+y1, x2-x1)이 된다 https://deepdata.tistory.com/1388 벡터 (x,y)를 90도 회전하는 방법1. 회전 행렬 벡터 (x,y)는 극좌표계를 이용하면 $(rcos \theta , rsin \theta)$   이 상황에..

• format_list_bulleted 브루트포스
• · 2024. 11. 17.
• textsms

탐색 범위를 줄여야하는 브루트포스 연습4 - 평면 위에 직사각형 쳐서 점 고르기

2187번: 점 고르기 평면 위 n개의 점이 있는데, 세로로 A, 가로로 B인 직사각형을 쳐서 이 안에 있는 점의 크기의 최댓값과 최솟값의 차이가  가장 크게 직사각형을 만들고 싶다 보면 N  그러다보니 직사각형의 크기를 1부터 2*10^6까지 돌리고 직사각형 위치를 2*10^6*2*10^6... 해보면.. 당연히 시간초과 그런데 구하고자 하는 것이 직사각형 크기 이런건 아니고 아무 직사각형이나 쳐서 그 안에 점 크기의 최댓값 - 최솟값의 차이를 최대로 만드는거 어떤 점들이 들어오느냐 이게 중요 그래서 점 i를 기준으로 잡아서 점 j를 순회해서 크기가 A*B인 직사각형을 만들 수 있는지 고려해보고  가능하다면 두 점 i,j는 직사각형 내부에 있기 때문에 두 점 i,j의 크기를 최댓값, 최솟값으로 갱신해서..

• format_list_bulleted 브루트포스
• · 2024. 11. 15.
• textsms

탐색 범위를 줄여야하는 브루트포스 연습3 - 해밍 수열의 i번째 수 찾기

7868번: 해밍 수열 3개의 소인수 p1,p2,p3이 주어질 때 p1,p2,p3만으로 소인수를 가지는 자연수의 오름차순 배열에서 i번째 수를 찾는 문제 H(2,3,5)는 2,3,4,5,6,8,9,10,12,...  p1,p2,p3,i가 10^18보다 작다고 하니까 단순하게 다 돌려보는건 어려울것 같고 p1,p2,p3만을 소인수로 가지니까 H(p1,p2,p3)는 $p1^{n1} * p2^{n2} * p3^{n3}$ 여기서 출력하는 수가 10^18보다 작다고 하니까 결국 $p1^{n1} * p2^{n2} * p3^{n3}$도 10^18보다 작아야함 따라서 n1,n2,n3  따라서 p1,p2,p3가 주어질때 0~59 * 0~59 * 0~59로 3중 for문 돌아보면서  p1**n1 * p2 ** n2 * p..

• format_list_bulleted 브루트포스
• · 2024. 11. 11.
• textsms

숨어있는 기준을 찾는 브루트포스1 - 수많은 좌표들을 얼마나 평행이동해야 일치하는가

5588번: 별자리 찾기 좌표 집합 A와 B가 주어질때 A를 얼마나 평행이동 시켜야 B의 부분집합이 될 수 있는가? 아래의 경우 2,-3 이동시키면 B의 빨간 부분과 일치시킬 수 있다   A의 별 개수 m이 최대 200개이고 B의 별 개수 n이 최대 1000개 x,y값은 최대 10^6까지...  그러면 200개 * 1000개 돌아보면서... 평행이동 시킬 수 있는 양 10^6까지 하나하나 돌아봐야하나?? 그런데 A의 모든 점은 서로 동일하게 (dx,dy)만큼 이동한다는 점 +  B의 점들 집합의 일부가 되어야하므로, A의 한 점이 B의 모든 점 각각에 대하여 얼마만큼 이동해야 가능한지  (dx,dy)를 모두 구해놓는다면?    가능한 (dx,dy) 후보는 최대 1000개이고 각각에 대해서 A의 모든 점에..

• format_list_bulleted 브루트포스
• · 2024. 11. 9.
• textsms