임의의 직사각형에 포함된 정수 중 최대 최소의 차이를 빠르게 찾는 2차원 배열 누적합

1999번: 최대최소 n*n 배열이 주어질때, B*B 크기의 임의의 부분 행렬이 포함하는 정수 중 최댓값과 최솟값의 차이를 묻는 쿼리가 주어진다 이 쿼리에 답한다 --------------------------------------------------------------------------------------------------------------------------------------------------- https://deepdata.tistory.com/1457 임의의 직사각형에 포함된 서로 다른 정수의 개수를 찾는 2차원 배열 누적합14846번: 직사각형과 쿼리 n*n 배열에서 왼쪽 위가 (x1,y1), 오른쪽 아래가 (x2,y2)인 직사각형에 포함되는 서로 다른 정수의 개수를 찾..

• format_list_bulleted 누적 합 알고리즘
• · 2025. 2. 10.
• textsms

임의의 직사각형에 포함된 서로 다른 정수의 개수를 찾는 2차원 배열 누적합

14846번: 직사각형과 쿼리 n*n 배열에서 왼쪽 위가 (x1,y1), 오른쪽 아래가 (x2,y2)인 직사각형에 포함되는 서로 다른 정수의 개수를 찾는 쿼리가 많이 주어질 때 이 쿼리에 답한다 ------------------------------------------------------------------------------------------------------- n이 300인데 여기서 핵심은 행렬이 포함하고 있는 정수가 10까지라는 것이다 dp[y][x][i]를 왼쪽 위가 (0,0)이고 오른쪽 아래가 (x,y)인 직사각형에 포함된 정수 i의 개수로 정의한다 x,y가 300까지이고 i가 10까지니까 900000 정도로 메모리 적당 나머지는 여기서 배운 테크닉대로 하면 된다 https://d..

• format_list_bulleted 누적 합 알고리즘
• · 2025. 2. 7.
• 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

평면 위 두 직사각형이 서로 겹치는 직사각형의 좌표 구하는 놀라운 방법

두 직사각형의 왼쪽 하단 좌표, 오른쪽 상단 좌표 (x1,y1), (x2,y2), (x3,y3), (x4,y4)가 각각 주어질때, 이 두 직사각형이 서로 겹쳐서 생기는 영역의 좌표를 구해본다면?   E의 좌표가 (x5,y5), F의 좌표가 (x6,y6)라고 한다면... 놀랍게도 이를 구하는 공식이 있다 x5 = max(x1,x3)y5 = max(y1,y3) x6 = min(x2,x4)y6 = min(y2,y4) 만약 x5 > x6이거나 y5 > y6이면 두 직사각형이 겹치지 않는다 근데 몇개 해보니까 진짜 맞는듯? 왼쪽 하단은 max, 오른쪽 상단은 min     조건 하나하나 생각해서 할려고 하면 거의 무조건 틀리더라 그냥 공식 써버리는게 제일 편함 #직사각형1 (x1,y1), (x2,y2)#직사각형2..

• format_list_bulleted 기하학
• · 2024. 8. 29.
• textsms

분할 정복 중요 테크닉 - 히스토그램에서 가장 큰 직사각형 찾기

1. 문제 1725번: 히스토그램 (acmicpc.net) 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 자 www.acmicpc.net 2. 풀이 히스토그램이 주어질때, 찾을 수 있는 직사각형중 넓이가 가장 큰 직사각형을 찾는 문제 위와 같은 경우 다음과 같은 직사각형을 찾을 수 있을 것이다. 히스토그램이 높이 배열 A로 주어질 때, 어떤 구간 [i,j]까지 잡았을 경우, 만들 수 있는 직사각형은 높이가 가장 낮은 min(A)에 구간의 길이 j-i+1을 곱한 값이다. 따라서 가능한 모든 경우에 대해 min..

• format_list_bulleted 분할 정복
• · 2023. 9. 22.
• textsms

겹치는 직사각형의 넓이를 조건문 없이 구하기

1. 문제 3063번: 게시판 (acmicpc.net) 3063번: 게시판 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄에 8개의 정수 x1, y1, x2, y2, x3, y3, x4, y4가 주어진다. 상원이 처음 붙인 포스터의 두 꼭짓점의 좌표 (x1, y1), (x2, y2)와 www.acmicpc.net 2. 풀이 좌표간 경우를 나눠서 구하려는 순간... 너무 많은 경우가 생겨 틀릴 가능성이 높고 어디가 틀렸는지 찾기도 어렵다 실제로 오답 from sys import stdin t = int(stdin.readline()) for _ in range(t): x1,y1,x2,y2,x3,y3,x4,y4 = map(int,stdin.readline().split())..

• format_list_bulleted 기하학
• · 2023. 3. 6.
• textsms