임의의 직사각형에 포함된 정수 중 최대 최소의 차이를 빠르게 찾는 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

높이가 작은 인접한 성냥으로 불을 옮길 때 가장 많은 성냥에 불을 태우는 방법

8685번: Zapałki (acmicpc.net) n개의 성냥이 일렬로 있을때, 어떤 성냥에 불을 붙이면 인접한 성냥으로 불이 옮겨간다 이때, 불이 옮겨가는 조건은 해당 성냥보다 작거나 같은 높이를 가진 인접한 성냥으로 옮겨간다 최대한 많은 성냥을 태우기 위해 어떤 성냥에 불을 붙여야하는가? 예를 들어 [2,3,1,2]이면 1번 원소 3에 불을 붙이면 0번, 1번, 2번에 불이 붙으므로 3개 불을 붙일 수 있다  각 원소마다 불을 붙였다고 했을때 왼쪽 방향으로 불을 옮길 수 있는 개수, 오른쪽 방향으로 불을 옮길 수 있는 개수를 구할 수 있다 왼쪽 방향으로 불을 옮길 수 있는 개수를 left = [1,1,1,1]이라고 초기화하고 [2,3,1,2]에 대해서 생각해보면 1번 원소 3은 0번 원소보다 크므로..

• format_list_bulleted 알고리즘/누적 합 알고리즘
• · 2024. 8. 21.
• textsms

누적 합으로 i < j < k < l을 돌아버리는 미친 다이나믹 프로그래밍 테크닉

25427번: DKSH를 찾아라 (acmicpc.net) 문자열 S가 주어질때, 인덱스 a  N이 10만이라 4중 for문으로 찾으면 당연히 시간초과 문자열이 'DDDDKKK'로 이루어질때, 만들 수 있는 'DK'의 개수는? 인덱스를 기준으로 세볼 때 (0,4), (0,5), (0,6) (1,4), (1,5), (1,6) (2,4), (2,5), (2,6) (3,4), (3,5), (3,6) K를 기준으로 본다면,  (0,4), (1,4), (2,4), (3,4) (0,5), (1,5), (2,5), (3,5) (0,6), (1,6), (2,6), (3,6) 처음에 D의 개수를 하나씩 세다가, K를 만나면 그 동안 만난 D의 개수를 누적해서 더해주면 된다  어떤 문자열이 주어지면, D의 위치 인덱스를 (..

• format_list_bulleted 알고리즘/누적 합 알고리즘
• · 2024. 7. 16.
• textsms

코딩테스트 복기 - 구간합이 전부 똑같도록 3구간으로 나누는 방법(잘 모를때는 조건식을 써봐라)

1. 문제 구간 A를 1번부터 x번까지, 구간 B를 x+1번부터 y번까지, 구간 C를 y+1번부터 n번까지 나눈다. 각 구간의 모든 원소의 합을 각각 a,b,c라고 하자. a,b,c가 전부 같도록 x,y를 정하자. 여기서 1  그러한 방법의 수가 몇가지일까? n은 최대 50만 배열의 각 원소는 -100만부터 100만까지로 음수일수도 있다. 예를 들어 [1,2,3,0,3]이면.. A가 1번 2번 = 3 B가 3번 = 3 C가 4번 5번 = 3 --------------------------- A가 1번 2번  = 3 B가 3번 4번 = 3 C가 5번 = 3 2가지 있다.  2. 풀이 구간합이니까, prefix sum으로 누적합을 만들어야하는 것은 명확하다 [1,3,6,6,9] n = int(input())..

• format_list_bulleted 알고리즘/누적 합 알고리즘
• · 2024. 4. 27.
• textsms

prefix sum만이 누적합이 아니다1 - value 누적합

1. 문제 28449번: 누가 이길까 (acmicpc.net) 28449번: 누가 이길까 HI-ARC는 종강을 맞아 HI팀과 ARC팀으로 나누어 친선대회를 열려고 한다. HI팀엔 $N$명 ARC팀엔 $M$명이 속해있다. 대회는 다른 팀끼리 모든 사람들끼리 한번씩 대결을 하는 것으로, 대회는 $N \times M$개 www.acmicpc.net 2. 풀이 n명의 리스트 A를 오름차순 정렬, m명의 리스트 B를 오름차순 정렬하고 A의 모든 원소 A[i]에 대하여, 리스트 B에서 lower bound와 upper bound를 찾아서 lower bound 밑으로는 A[i]보다 작은 수들이니까 A의 승리이고, upper bound 위로는 A[i]보다 큰 수니까 B의 승리 lower bound와 upper boun..

• format_list_bulleted 알고리즘/누적 합 알고리즘
• · 2024. 4. 10.
• textsms