Processing math: 100%

본문 바로가기

알고리즘7

누적합 응용(feat. 2차원 배열) 2차원 배열에 대한 구간합 문제가 나왔는데 내용이 기록하기 좋은 것 같아서 작성해보려고 한다.누적합에 대한 내용보다는 문제를 살펴보면서 어떻게 누적합을 사용해서 풀었는지에 대해서 얘기하려고 한다.누적합(Prefix Sum)에 관한 내용은 아래를 참고해 주세요.누적합(Prefix Sum)백준 11660번 구간 합 구하기 5문제 내용을 간단히 얘기하자면

$N \cdot N$ 크기의 표가 주어지고

$(x1, y2)$ 부터

$(x2, y2)$ 까지 합을 구하는 것이다.ex)

$N = 4$ 이고, 표가 아래와 같이 채워져 있는 경우. (2, 2)부터 (3, 4)까지 합을 구하면

$3+4+5+4+5+6 = 27$ 이다.1234234534564567 이때 누적합을 어떻게 사용하는지 알아보려고 한다.먼저 .. 2025. 2. 23.

분배법칙(Distributive Property) 알고리즘 문제를 풀다가 분배법칙에 관한 수학적인 문제가 나와 기억하기 위해 작성한다.분배법칙(Distributive Property)집합 S와 S에 대해 닫혀있는 두 이항 연산 *, +가 정의되어 있을 때, S의 임의의 원소 a, b, c에 대해

$a * (b + c) = (a * b) + (a * c)$ 가 성립하면 (+에 대한 *의) 좌분배법칙이,

$(b + c) * a = (b * a) + (c * a)$ 가 성립하면 (+에 대한 *의) 우분배법칙이 성립한다고 하며,위 두 가지가 모두 성립할 경우 집합 S에서 연산 *은 연산 +에 대해 분배법칙(+에 대한 *의 (양쪽) 분배법칙)이 성립한다고 한다. 두 항을 곱할 때 각 항들을 나누어 곱한 후 더하는 방식이다.즉, "(3 + 2) x 4"가 있.. 2025. 2. 19.

지수법칙 & 모듈러 연산 알고리즘 문제를 풀다가 지수법칙과 모듈러 연산에 관한 수학적인 문제가 나와 기억하기 위해 작성한다.지수법칙(거듭제곱의 곱)지수법칙은 다음과 같다.

$x^{n} \ast x^{m} = x^{n+m}$ ex)

$x^8$ 지수가 짝수일 때 즉,

$x^8 = x^{4+4}$ =

$x^4 * x^4$ =

$(x^2 * x^2) * (x^2 * x^2)$ =

$((x^1 * x^1) * (x^1 * x^1)) * ((x^1 * x^1) * (x^1 * x^1))$ ex)

$x^9$ 지수가 홀수일 때 즉,

$x^9 = x^{4+4} * x$ =

$x^4 * x^4 * x$ =

$(x^2 * x^2) * (x^2 * x^2) * x$ = $((x^1 * x^1) * (x^1 * x^1)) * ((x^1 * x^1) * (x.. 2025. 2. 13.

누적합(Prefix Sum) 누적합(Prefix Sum)누적합은 요소들의 누적된 합의 의미를 얘기합니다.배열의 첫 번째 0번째 배열의 요소부터 누적시키면서 더한 배열을 활용합니다. 일부 구간에 대한 합을 구하는 문제에서 사용이 됩니다. 단, 배열의 값들이 변하지 않는다는 전제가 필요합니다.

$N = 5$ 인 N 크기의 정수 배열 arr이 있을 때 여러 개의 구간 [a, b]에 대해 합을 구하려고 합니다.

$1\leq a\leq b\leq N$

$arr[a]+arr[a+1]+\cdots+arr[b]$ Index i01234arr[i]16425 간단하게 생각할 수 있는 방법은 반복문을 돌려서 각 요소를 더하는 것입니다. 이 방법은 각 쿼리에 대해 최대

$O(N)$ 시간 복잡도를 가지고, 만약 M개의 쿼리가 주어지면 시간 .. 2025. 1. 19.

DFS (Depth-First Search) BFS가 궁금하면 아래 글을 참조 BFS (Breadth-First Search) ✔ DFS(Depth-First Search) DFS는 깊이 우선 탐색이라고도 부르며, 그래프를 탐색하는 방법 중 하나이다. 하나의 정점으로부터 시작해 차례대로 모든 정점들을 한 번씩 방문하는 것으로 즉, 시작 노드에서 출발해 인접한 노드(가까운 노드)를 먼저 탐색하고 그 정점의 최대 깊이까지 탐색을 마친 후 돌아와 다른 분기로 다시 탐색하는 알고리즘이다. 넓게 탐색하기 전에 깊게 탐색 스택 or 재귀를 사용하여 구현 모든 노드를 방문할 때 사용 ※ 중요한 점은 방문한 정점은 다시 방문하지 않아야 한다. DFS는 스택으로도 구현할 수 있지만 재귀로 구현하는 편이 더 깔끔해서 재귀로 더 많이 구현하는 것 같다. DFS와 BF.. 2023. 6. 25.

큐(Queue) ✔ 큐(Queue) 큐도 스택과 마찬가지로 알고리즘보단 자료 구조에 해당하고 컴퓨터에서 많이 사용되는 자료 구조이다. 큐는 먼저 집어넣은 데이터가 먼저 나오는 선입선출(FIFO: First In First Out) 구조로 저장하는 형식을 말한다. 즉, 가장 처음에 넣은 값이 먼저 나오는 것을 FIFO 구조라고 한다. 나중에 넣은 값이 먼저 나오는 스택과는 반대되는 개념이다. 쉬운 예시로 파이프 혹은 드라이브 스루를 생각하면 된다. 드라이브 스루는 가장 먼저 들어가는 사람이 먼저 주문을 하게 되고 그 뒤로 차례로 줄을 서게 된다. 먼저 들어간 사람이 주문을 끝내고 가지 않는 이상 그 뒤로는 계속 기다려야 하는 구조이다. 이 구조가 큐 자료 구조에 해당한다. ✔ 큐의 연산 큐는 양쪽이 뚫려 있는 구조로 한쪽.. 2023. 5. 2.

이전 1 2 다음

티스토리툴바