가장 긴 연속하는 올바른 괄호 부분 문자열의 길이 구하는 알고리즘

15926번: 현욱은 괄호왕이야!! 괄호로만 이루어진 문자열이 주어질때 연속하는 부분 문자열 중 가장 긴 올바른 괄호 문자열의 길이를 구하는 문제 ------------------------------------------------------------------------------------------------------------------------------------------------------- 올바른 괄호 문자열을 구하는 알고리즘은 스택을 이용해서  스택이 비어있는데 (이 들어오면 넣고 스택이 비어있지 않을때, (이 들어오는 경우, 스택의 마지막 문자가 (인 경우에는 (이 들어올 수 있고 )이 들어오는 경우, 스택의 마지막 문자가 (인 경우에는 제거하고 마지막에 스택이 비면 올바른 ..

• format_list_bulleted 자료구조(스택,큐,해시맵)
• · 2025. 2. 17.
• textsms

flood fill 핵심 트릭 - 사각형으로 둘러쌓인 연결요소의 둘레의 길이(연결요소 내부 영역을 찾는 방법)

5850번: Perimeter  100*100 들판에 1*1 건초를 n개 두는데 이 건초 n개는 연결되어있다. 즉 임의의 건초에서 상하좌우로 출발하면 다른 모든 건초로 도달할 수 있다 이 연결된 영역의 둘레를 구하고 싶다. 이때 건초 더미들이 감싸고 있는 내부 구멍이 있을 수 있는데 이 구멍들의 둘레는 계산하지 않는다 예를 들어 아래 그림은 둘레가 14이다. X부분의 둘레는 계산하지 않는다   --------------------------------------------------------------------------------------------------------------------------------- 건초더미 둘레를 구해야하는데 건초더미가 감싸는 내부 구멍을 어떻게 찾아야하느냐가 관..

• format_list_bulleted DFS BFS 정복기
• · 2025. 2. 16.
• textsms

구간을 잡아야하는 matrix chain multiplication 다이나믹 프로그래밍

11049번: 행렬 곱셈 순서  n*m인 행렬과 m*k인 행렬을 곱하면 n*k인 행렬이 나오고 연산량은 n*m*k이다 A의 크기가 5*3, B의 크기가 3*2, C의 크기가 2*6인 경우 ABC를 곱할때 (AB)C를 곱하면 AB를 곱해서 5*3*2번, AB는 5*2행렬이고, AB와 C를 곱해서 5*2*6 = 총 90번 A(BC)를 곱하면 BC를 곱해서 3*2*6번, BC는 3*6행렬이고 A와 BC를 곱해서 5*3*6 = 총 126번 행렬의 크기 r*c가 n개 주어진다. 이 n개의 행렬은 곱할 수 있다고 할때, 최소 연산량을 구한다면? ------------------------------------------------------------------------------------------------..

• format_list_bulleted 다이나믹 프로그래밍
• · 2025. 2. 13.
• textsms

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

안겹치게 구간을 나누는 다이나믹 프로그래밍 테크닉

문제1. 11985번: 오렌지 출하  n개의 오렌지가 1번부터 n번까지 순서대로 있는데, 순서대로 앞에서부터 상자에 나눠서 넣는다 이때 한 상자에 넣는 오렌지는 번호가 연속해야한다 한 상자당 최대 m개까지 오렌지를 넣을 수 있다 이때 상자를 포장하는 비용은 K + s*(a-b)로 s는 상자에 넣는 오렌지의 개수이고 a는 오렌지 크기의 최댓값, b는 최솟값이다 이때 모든 오렌지를 포함하는 비용의 최솟값은? ------------------------------------------------------------------------------------------------------------------------- dp[i] = i번째 오렌지까지 포장하는데 드는 비용의 최솟값 i = 0인 경우 dp[..

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