전체 글 (7) 썸네일형 리스트형 [백준 14601] 분할 정복 한 변의 길이가 $n$인 정사각형 3개로 만든 ㄱ자 타일을 길이가 $n$인 ㄱ자 타일이라고 정의하자.길이가 2인 ㄱ자 타일은 길이가 1인 ㄱ자 타일로 아래 그림과 같이 만들 수 있다. 같은 방법으로 길이가 2인 ㄱ자 타일로 길이가 4인 ㄱ자 타일을 만들 수 있고 길이가 $2^{n-1}$인 ㄱ자 타일로 길이가 $2^n$인 ㄱ자 타일로 만들 수 있다. 따라서 전체 정사각형 타일을 사분면으로 나눈 뒤 배수구가 어느 사분면에 위치해 있는지 파악하고, 배수구가 없는 사분면은 분할정복으로 ㄱ자 타일을 배치하는 과정을 반복하면 된다. [백준 11003] 우선순위 큐, 덱 우선순위 큐 또는 덱으로 해결할 수 있다. 방법 1) 우선순위 큐 (최소 힙) 1. 우선순위 큐의 top에서 인덱스가 $i-L+1$ 보다 작은 값들을 모두 pop 해준다. 2. 우선순위 큐에 $A_i$ 를 삽입한다. 3. 우선순위 큐의 top을 출력한다. #include #include using namespace std;using pii = pair;int arr[5000000];priority_queue, greater> pq;int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N, L; cin >> N >> L; for(int i=0; i> arr[i]; int i = 1-L, j = 0; while(j 방법.. [백준 15647] 트리 dp 전체 노드 수를 $N$, 노드 $x$ 로부터 다른 모든 노드들까지의 최단거리 합을 $f(x)$, 노드 $x$ 를 포함해서 $x$ 가 가진 자식 노드의 수를 $g(x)$, 노드 $x$ 와 노드 $y$ 를 잇는 간선의 길이를 $l_{xy}$ 라 할 때 아래의 점화식이 성립한다. $f(child) = f(parent) + (N - 2 * g(x)) * l_{pc}$ 예시) $f(2)$ 를 이미 구했고 $f(4)$ 를 구한다고 했을 때 파란색 노드들은 $l_{24}$ 를 경유해야하고 빨간색 노드들은 $l_{24}$ 를 경유할 필요가 없다. $f(4) = f(2) - (빨간 노드의 수) * l_{24} + (파란 노드의 수) * l_{24}$ 이고$(파란 노드의 수) = N - (빨간 노드의 수)$ 이며$(빨간 .. [백준 11062] MiniMax Tree MiniMax는 2인, 완전 정보, 제로섬 게임에서 최악의 경우에도 최선의 결과를 보장하는 수를 찾기 위한 알고리즘이다.이름 그대로 Min과 Max를 번갈아 적용한다. 두 플레이어의 정의: Max Player: 점수를 최대화하는 것이 목표 Min Player: 점수를 최소화하는 것이 목표 알고리즘 작동 방식: 1. 트리 생성: 현재 상태를 root로 하여 게임이 끝날 때까지 가능한 모든 수를 트리형태로 펼친다. 2. Leaf 노드 평가: 게임이 끝나는 상태에 점수를 매긴다. 3. Back propagation: Max 노드는 자식 노드들 중 가장 높은 점수를 선택하고 Min 노드는 자식 노드들 중 가장 낮은 점수를 선택한다. 4. 최종 결정: 이 과정을 root 노드까지 반복하여 최종 점수를.. 희소 배열 (sparse table) 희소 배열은 특정 구간에 대한 query를 빠르게 처리하기 위한 자료 구조이다. 주로 특정 구간의 최솟값, 최댓값, 합 등을 구할 때 모든 요소를 방문하지 않고 처리하기 위해 사용된다. 예시를 통해 확인해보자. $f_{13}(x)$ 를 생각해보자. $f_{13}(x)$ 를 구하는 가장 쉬운 방법은 $f$ 를 13번 합성하는 것이다. 그러나 이는 쿼리 1개당 시간 복잡도가 $O(n)$ 이고, 전체 시간 복잡도는 $O(nQ)$ 인 비효율적인 방법이다. $f$ 를 13번 합성하는 대신 $f_{13}(x)=f_{8}(f_{4}(f(x)))$ 로 표현할 수 있다. $f_{2^{i}}(x)$ 를 매번 구하면 단순히 $f$ 를 13번 합성하는 것과 같은 시간 복잡도를 갖는다. 그러나 이 값들을 미리 저장을 한 뒤 매.. 행렬로 표현한 피보나치 수열 피보나치 수열이란 첫번째 항과 두번째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. 편의상 0번째 항을 0으로 나타내기도 한다. 피보나치 수열을 수식으로 나타내면 아래와 같다. $$F_{0}=0,\;F_{1}=1,\;\;F_{n}=F_{n-1}+F_{n-2}\;(n\geq 2)$$ 이때 점화식 $F_{n}=F_{n-1}+F_{n-2}\;(n\geq 2)$ 을 아래와 같이 행렬로 나타낼 수 있다. $$\begin{bmatrix} 0 & 1 \\ 1 & 1 \\ \end{bmatrix} \begin{bmatrix} F_{n-2} \\ F_{n-1} \\ \end{bmatrix} = \begin{bmatrix} F_{n-1} \\ F_{n} \\ \end{bmatrix}$$ 또는 2x2 행.. 모듈러 곱셈 역원 기본적으로 모듈러 연산은 곱셈 연산에 대해 다음과 같은 수식이 성립한다. $$ (A \times B)\;mod\;C = (A\;mod\;C\times B\;mod\;C)\;mod\;C $$ 이는 어떤 두 수에 대해서 두 수를 곱한 후 mod 연산을 한 것과 두 수에 mod 연산을 먼저 한 후 곱한 것이 같다는 의미이다. 그러나 나눗셈에서는 곱셈과 같이 모듈러 연산이 닫혀있지 않다. 나눗셈에 대해서 모듈러 연산을 하지 못한다면 큰 수의 나눗셈을 할 때 시간이 매우 오래 걸린다. 따라서 나눗셈에서도 위의 수식과 같은 계산을 하기 위해 필요한 개념이 모듈러 곱셈 역원이다. 기본적인 아이디어는 곱셈과 같은 형태를 만드는 것이다. 먼저 아래의 수식이 성립한다. $$a^{p}\equiv a\;\;\;mod\;p$$.. 이전 1 다음
