슬라이딩 윈도우는 고정된 크기의 구간인 “윈도우"를 관리하되, 윈도우를 한 단위씩 움직여가면서 구간 내에서의 목푯값을 계산하는 알고리즘입니다. 이때, 고정된 크기의 구간을 움직이는 연산을 지원하기 위해서 덱을 사용할 수 있습니다. 따라서, 목푯값을 계산하는 데 덱을 이용한 최적화를 생각해볼 수 있도록 합니다. 구간의 관리 그럼 구간을 움직이는 연산을 어떻게 덱을 이용해 지원할까요? 구간을 움직일 때 구간의 양 끝에서만 자료의 추가와 삭제가 일어난다는 점에 집중하면 구간을 덱으로 쉽게 관리할 수 있다는 것을 알 수 있습니다....
알고리즘 시각화 템플릿을 테스트할 목적으로 쓴 글입니다. import attach from '/algo-vis.mjs'; import { steps, algorithm } from './reverse-algo.mjs'; attach(interactive, steps, algorithm);
각 건물 쌍은 3가지 중 하나의 관계를 맺고 있습니다. 서로 같은 나무를 심어야 한다. 서로 다른 나무를 심어야 한다. 제약이 없다. 단순하게 제약이 있는 나무들을 하나의 집합으로 만들어 관리하면 서로소 집합 자료구조를 이용할 수 있습니다. 단, 집합의 루트를 찾을 때 루트-리프 사이 관계를 계속 갱신해줘야 하는데, 서로 같은 나무를 심는 조건을 0, 서로 다른 나무를 심는 조건을 1로 두면 xor 연산을 통해 조건의 합성을 정의할 수 있습니다. 경로 압축 시에 조건을 합성해주는 코드를 추가하여 아래 그림처럼 만들 수 있습니다....
A를 가장 최대한 큰 덩어리로 나누어 A를 정렬하는 문제입니다. 우선 k = 3인 경우는 항상 A가 정렬 가능함을 알 수 있습니다. 배열에서 최댓값을 찾아 [ … ] [ 최댓값 ] [ … ] 조각으로 나눈 뒤, 최댓값을 맨 앞으로 보내는 작업을 $N$번 반복하면 되기 때문입니다. 다음으로 k = 2인 경우가 어디에 속하는지를 확인해야 합니다. 두 조각으로 잘랐을 경우에 재배열하는 경우는 배열을 특정한 원소 기준으로 회전한 경우와 같습니다. 따라서 최솟값이 위치한 인덱스 $i$부터 인덱스 $(i + N) \bmod N$까지 순회하며 정렬이 되었는지 확인하면 됩니다....
각 버스가 들어오고 나가는 것은 항상 짝이 맞습니다. 접근의 용이성을 위해 들어오는 것을 왼쪽 괄호 (, 나가는 것을 오른쪽 괄호 )로 생각하겠습니다. 사건의 시각이 주어져 있으므로 시간축을 가로축으로 하여 각 시각에 맞게 괄호를 늘어놓을 수 있습니다. 그러면 괄호가 가장 많이 겹쳐진 구간이 버스가 가장 많이 몰린 시간대이고 이때 겹쳐진 횟수가 답입니다. 괄호를 시간축에 늘어놓는 행위는 버스가 들어오고 나가는 사건을 시간순으로 정렬하는 것과 같습니다. 따라서 버스가 들어오고 나가는 사건을 시간순으로 정렬하고, 맨 처음 사건부터 버스가 들어오거나 나감에 따라 1을 각각 더하고 빼 주면 됩니다....
각 $q_i$에 대해서 다음을 구하는 문제입니다. $$\sum_{j = 1}^{N} a_j\left| q_i-x_j \right| $$ 절댓값을 그대로 계산하면 $O\left(N\right)$으로 전체 시간복잡도가 $O\left(NQ\right)$가 됩니다. 절댓값의 특성을 생각해보면 $q_i$보다 작은 $x_j$에 대해서는 $a_j\left(q_i-x_j\right)$를, $q_i$보다 큰 $x_j$에 대해서는 $a_j\left(x_j-q_i\right)$을 계산하면 됩니다. 이를 바탕으로 위 식을 다시 적으면 이렇게 됩니다. $$q_i\sum_{x_j\lt q_i} a_j - \sum_{x_j\lt q_i} a_jx_j + \sum_{x_j\ge q_i} a_jx_j - q_i\sum_{x_j\ge q_i} a_j$$ $\left\lbrace x_j\right\rbrace$를 미리 정렬해두면 $x_j\lt q_i$인 $j$를 $O\left(\log N\right)$에 구할 수 있고, $a_j$와 $a_jx_j$의 누적 합을 전처리하여 구간 합을 $O\left(1\right)$에 구할 수 있습니다....
1차 시도 문제에서 주어진 대로 코드를 작성했습니다. 전체 배열을 반으로 나누고 왼쪽 부분의 최대공약수를 구한 뒤 재귀적으로 오른쪽 부분의 아름다움을 구했습니다. 오른쪽 부분도 같은 방법으로 구하면 됩니다. 각 재귀 단계에서 왼쪽과 오른쪽 부분의 최대공약수를 모두 구하므로 시간 복잡도는 $O(N)$이며 재귀 단계마다 $N$의 크기가 반으로 줄기 때문에 총 시간 복잡도는 $O(N\log{N})$입니다. 2차 시도 1차 시도에서는 왼쪽 부분의 최대공약수를 구한 뒤 마지막으로 왼쪽 부분의 아름다움을 재귀적으로 구하는 과정에서 왼쪽 부분의 최대공약수를 다시 구하게 됩니다....
수열의 연속한 구간에서 최댓값과 최솟값의 차를 모두 더한 것이 최대가 되도록 하는 것이 문제입니다. 구간들이 연속한 원소로 이루어져 있기 때문에 수열의 앞쪽으로 전진하면서 이미 계산한 답안을 통해 새로운 원소에 대한 값을 계산하는 DP 전략이 필요해 보입니다. $n$번째 원소를 처리할 때, 탐색해볼 필요가 있는 경우는 많아야 $n$가지밖에 되지 않는다는 것을 알 수 있습니다. $n$번째 원소를 포함하여 왼쪽으로 길이가 $1, 2, \cdots, n - 1, n$인 구간을 한 조로 구성하는 경우만이 새로 추가되기 때문입니다....
대칭을 신경쓰지 않는 경우를 먼저 살펴봅니다. 2×N 크기 판을 1×2 (또는 2×1) 크기와 2×2 크기의 타일로 채우는 경우의 수를 $F(N)$이라고 하겠습니다. 왼쪽부터 $N$번째 위치에 타일을 오른쪽 정렬하여 놓는다고 생각하면 경우의 수가 좁혀집니다. 1×2 타일을 하나 두는 경우 왼쪽 $N - 1$개의 타일은 자유롭게 놓을 수 있으므로 $F(N - 1)$가지입니다. 2×1 타일을 두 개 두는 경우 왼쪽 $N - 2$개의 타일은 자유롭게 놓을 수 있으므로 $F(N - 2)$가지입니다....
결국 가장 먼 곳까지 가야 한다는 규칙을 발견하고, 이를 이용하는 것이 핵심인 문제입니다. 가장 먼 곳까지 가서 책을 꽂고 오면 항상 가장 먼 곳이 이전보다 가까워집니다. 이전보다 가까워지는 거리를 최대로 하기 위해서는 가장 먼 곳에서 먼 순서대로 $M$개의 책을 꽂고 와야 합니다. 이 때의 비용은 가장 먼 곳을 한 번 가는 것과 같으므로 최선의 선택이 됩니다. 위의 알고리즘을 구현하기 위해서는 우선 책의 위치를 정렬하고 시작점인 0의 위치를 찾은 뒤 음수 쪽에서 $M$개씩 책을 가져오고, 0에 다시 도착하면 양수 쪽에서 $N$개씩 책을 가져오는 것을 반복해야 합니다....