ps하는블로그

A. Wonderful Permutation 문제 : $1$부터 $n$까지 각 값이 한번씩 등장하는 길이가 $n$인 수열 $p_1, p_2, ..., p_n$과 자연수 $k(k\leq n)$이 있다. 이 중 임의의 $i, j (1\leq i > n..

A. Traveling Salesman Problem 문제 : $2$차원 평면에 $n$개의 점이 있고 각 점들은 $x$축 또는 $y$축에 있으면서 $-100\leq x_i, y_i \leq 100$의 값을 가진다. $(0,0)$에서 출발해서 상하좌우로 $1$만큼 움직여 모든 점을 방문한 뒤 다시 원점으로 돌아올 때 필요한 최소 움직임을 구하면 된다. 풀이 : 점들이 축 위에 있으므로 $max(x_i,0) - min(x_i,0)$값의 2배와 $max(y_i,0) - min(y_i,0)$값의 2배를 더해주면 된다. 코드 : #include using namespace std; void solve() { int n, x, y; int y1 = 0, y2 = 0; int x1 = 0, x2 = 0; for (c..

A. 2-3 Moves 문제 : 정수로 된 직선에서 초기에는 $0$의 위치에 있고 $n$의 위치까지 이동하려 한다. $2, 3$의 거리를 이동할 수 있을 때($+2, +3, -2, -3$) 최소 몇번의 움직임으로 갈 수 있을지를 알아보면 된다.($1\leq n\leq10^9$) 풀이 : $n=1$일 때 : $2$번의 이동으로 갈 수 있다. $n\geq 2$일 때 : $\lceil\frac{3}{n}\rceil$번의 이동으로 갈 수 있다. 코드 : #include using namespace std; void solve() { int n; cin >> n; if (n == 1) cout > n; cout

A. Everyone Loves to Sleep 문제 : 현재의 시각과 특정 시간에 울리는 $n$개의 알람이 있을 때 가장 처음으로 울리는 알람까지의 시간이 얼마나 되는지 구하면 된다. 풀이 : $n$개의 시각 중 현재 시각보다 작으면 하루(24시간)를 더해준다. 그리고 시간을 분 단위로 바꿔서 가장 차이가 적게 나는 값을 다시 시 분 형태로 바꿔주면 된다. 코드 : #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int t; for (cin >> t; t--;) { int n, h, m, ans = 1e9; cin >> n >> h >> m; int t = h * 60 + m; for (int i = 0; i..

A. Perfect Permutation 문제 : $p_1, p_2, ... p_n$인 길이가 $n$인 수열이 있을 때 $i$가 $p_i$를 나누어 떨어지는 수가 최소가 되도록 수열을 정하면 된다. 수열에서는 1부터 $n$까지 한 번씩만 등장한다. 풀이 : $n$이 홀수면 $1\ 3\ 2\ 5\ 4\ ... n\ (n-1)$이 되고 $n$이 짝수면 $2\ 1\ 4\ 3\ ... n\ (n-1)$이 된다. 코드 : #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int t; for (cin >> t; t--;) { int n; cin >> n; if (n % 2) { cout k; vector ar(k); for..

1. 우선순위 큐 = 힙 priority_queue pq; priority_queue l_pq; priority_queue g_pq; for (int i = 0; i < 4; i++) { // 0 1 2 3 pq.push(i); l_pq.push(i); g_pq.push(i); } while (pq.size()) { // 3 2 1 0 cout

(이 내용은 제가 이해한 걸 정리해둔 거라 틀린 내용이 있을 수도 있습니다.) segment tree : 특정 구간에서 값이 변할 때 구간에 대한 쿼리를 처리하기 위한 자료구조(최대, 최소, 구간합, ... 등) 예를 들어 n개의 수열 a1, a2, ... an 이 있다고 했을 때 [l, r]구간의 합을 naive하게 구하면 O(r-l+1)의 시간복잡도를 가진다. d1=a1, dn=d(n-1)+an 이 점화식을 활용하여 구간합을 미리 구해두면 O(1)가 되지만 구간의 값이 바뀌게 된다고 하면 O(r-l+1)의 시간복잡도를 가지게 될 것이다. 이를 O(logN)만에 구해줄 자료구조를 segment tree(or fenwick tree(=binary indexed tree))라고 한다. segement tr..

(이 내용은 제가 이해한 걸 정리해둔 거라 틀린 내용이 있을 수도 있습니다.) (https://www.secmem.org/blog/2019/12/12/HLD/ 를 참고했습니다.) HLD(Heavy-Light Decomposition) : 트리의 각 노드를 chain 단위로 분할하고 1차원 배열처럼 사용하는 것 트리를 chain단위로 분할하는 과정은 (1) 각 노드들의 무게를 조사한다. 여기서 각 노드의 무게란 자신을 포함한 모든 자식들의 수가 된다. (2) 루트 노드부터 chain을 형성하게 되는데 자식들 중 가장 무거운 노드들을 chain에 포함하면 시키면서 탐색한다. (3) 리프노드까지 탐색을 마치면 다시 자신의 부모로 올라가서 탐색을 한다. 2번째부터 탐색되는 노드는 그 노드를 조상으로 하는 새로운..