배열을 뒤집어서 다른 배열과 대응하는 원소끼리 곱의 합의 특징

8973번: 수학 공책 길이가 n인 두 수열이 존재하는데 두 수열 사이 흐릿함은 두번째 수열을 뒤집어서, 같은 위치에 있는 두 수의 곱의 합이다 예를 들어 3 -4 -3 -3 0 5는 -3 0 5를 뒤집어서 5 0 -3으로 하고 같은 위치에 있는 원소끼리 5*3 + 0*-4 + -3*-3 = 9 + 15 = 24 앞에서부터 b개 뒤에서부터 e개를 지워서 두 수열의 흐릿함을 되도록 크게 만들고자 한다면, 최댓값을 구하고 b,e를 구한다 --------------------------------------------------------------------------------------------------------------- 쉽게 생각할 수 있는건 앞에서부터 b개를 지우고 뒤에서부터 e개를 지웠을때..

• format_list_bulleted 다이나믹 프로그래밍
• · 2025. 4. 3.
• textsms

가장 많은 점을 포함하는 사각형 찾기 놀라운 방법

14658번: 하늘에서 별똥별이 빗발친다 최대 50만*50만의 2차원 평면 위에 k개  최대 10만*10만의 L*L 정사각형으로 가장 많은 점을 포함시키려고 할때, 이 정사각형에 포함되지 않는 점의 개수를 구한다 정사각형의 모서리에 포함되어도 포함된 것으로 인정한다 ---------------------------------------------------------------------------------------------------------------------------------------------- 문제의 조건을 만족하는, 평면 위에 가장 많은 점을 포함하는 정사각형의 배치는 반드시 존재할 수 밖에 없다. 그러한 최적 배치에 들어가있는 모든 별을 포함할 수만 있다면, 정사각형의 배치는 ..

• format_list_bulleted 브루트포스
• · 2025. 3. 30.
• textsms

(두 위치의 거리 * 두 위치의 원소 중 최솟값)의 최댓값을 투포인터로 찾는 방법

22945번: 팀 빌딩  n명이 한줄로 서있을 때 2명을 골라 그 2명 사이의 사람 수 * min(첫번째 사람의 능력치, 두번째 사람의 능력치)의 최댓값을 찾는 문제 [1,4,2,5]이면 A[1] = 4, A[3] = 5이고 두 사람 사이에는 1명 있고 둘 중 최솟값은 4니까 4가 최댓값이다 투 포인터로 해결할 수 있다해서 연습삼아 풀어볼려했는데 기존에 알던 투 포인터 풀이는 안먹히니 답이 없다 인덱스랑 같이 넣어서 정렬해야하나 일단 정렬이 안되어있고 포인터 움직여도... min값이 커졌다 작아졌다 하는데 근데 0번과 n-1번에 포인터를 두고 서로 간격을 좁혀가면 된다는데 그래도 어떻게 해야하는지 고민되더라고 A[i], A[i+1], A[i+2], A[i+3], ...., A[j] i번과 j번을 가리키고..

• format_list_bulleted 투 포인터 알고리즘
• · 2025. 1. 7.
• 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