본문 바로가기

알고리즘

 (62)
[BOJ 27014] Cube Stacking https://www.acmicpc.net/problem/27014 27014번: Cube Stacking Farmer John and Betsy are playing a game with N (1 ≤ N ≤ 30,000)identical cubes labeled 1 through N. They start with N stacks, each containing a single cube. Farmer John asks Betsy to perform P (1≤ P ≤ 100,000) operation. There are two types of ope www.acmicpc.net Tag : DSU 스몰투라지, 세그 등... 뇌절각은 잔뜩 보이는데 그냥 \(O(logN)\) 이하의 유니온 파인드로 생각을 했을 ..
[BOJ 11003] 최솟값 찾기 - 모노톤 큐 없이 O(n) https://www.acmicpc.net/problem/11003 11003번: 최솟값 찾기N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다.www.acmicpc.net 최솟값 찾기는 모노톤 큐를 사용해 푸는 풀이가 보편적인데 모노톤 큐를 사용하지 않는 \(O(n)\) 풀이를 소개하겠습니다. 1. 배열을 k개씩 묶음으로 쪼개 각각 묶음에서 prefix min, suffix min을 구한다.2. min(prefix_min[i], suffix_min[i - k + 1])을 출력한다. i mod k = 0인 i는 i - k + 1 = 0) ..
[BOJ 24978] Subset Equality https://www.acmicpc.net/problem/24978 24978번: Subset Equality The cows are trying out a new method of exchanging coded messages with each-other where they mix irrelevant letters in among relevant letters to make the messages hard to decode. The cows transmit two strings $s$ and $t$ each of length at most $10^5$ consi www.acmicpc.net Sol 1) 메모이제이션 잘한 완탐 문자 집합 A에 대해 정답이 Y라면 A의 부분집합 B는 모두 Y다. N이라면 ..
[BOJ 1762] 평면그래프와 삼각형 https://www.acmicpc.net/problem/1762 1762번: 평면그래프와 삼각형첫째 줄에 두 정수 N, M이 주어진다. M은 간선의 개수를 나타내는 0 이상의 정수이다. 다음 M개의 줄에는 각 간선이 연결하는 서로 다른 두 정점의 번호가 주어진다. 같은 간선이 중복되어 입력으www.acmicpc.netTag : sqrt? 문제요약 평면그래프 G(v, e)가 주어질 때 크기가 3인 사이클의 개수를 구하라. 풀이 sol 1) 평면그래프는 \( |E| \leq 3|V| - 6 \)을 만족하기 때문에 m은 최대 \(300000 - 6\)입니다. 가장 직관적인 풀이를 생각해보겠습니다. 모든 간선 (i -> j)를 순회하며 (i -> k), (j -> k) 가 모두 존재하는 k의 개수를 세어주고 ..
[BOJ 1801] 직사각형 만들기 https://www.acmicpc.net/problem/1801 1801번: 직사각형 만들기 첫째 줄에 막대의 개수 N이 주어진다. N은 4보다 크거나 같고, 16보다 작거나 같은 자연수이다. 둘째 줄에 막대의 길이가 공백을 사이에 두고 주어진다. 막대의 길이는 10보다 작거나 같은 자연수 www.acmicpc.net Tag : knapsack, optimization 문제요약 주어진 막대를 조합해 만들 수 있는 가장 큰 직사각형의 넓이를 구하라. \((N \leq 16)\) 풀이 직관적으로 떠올릴 수 있는 풀이는 다음과 같다. D[a][b][c][d] = 막대를 중복되지 않게 합쳐 a, b, c, d를 만들 수 있는가 이때 시간복잡도는 \(O(N \times 80^4) = 655360000 \)이 될..
[BOJ 16583] Boomerangs https://www.acmicpc.net/problem/16583 16583번: Boomerangs Let G = (V, E) be a simple undirected graph with N vertices and M edges, where V = {1, . . . , N}. A tuple is called as boomerang in G if and only if {(u, v),(v, w)} ⊆ E and u ≠ w; in other words, a boomerang consists of two edges which shar www.acmicpc.net Tag : constructive, greedy 문제요약 양방향 그래프 G(v, e)를 인접한 2개의 간선들로 분할하라. 이 때 인접한 2개의 간선쌍..
[BOJ 12858] Range GCD https://www.acmicpc.net/problem/12858 12858번: Range GCD 첫째 줄에 수열의 원소의 개수를 나타내는 하나의 자연수 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄에 수열의 각 원소를 나타내는 N개의 자연수가 주어진다. i번째로 등장한 자연수는 수열의 i번째 www.acmicpc.net Tag : segment tree 문제요약 구간 업데이트(덧셈)가 있을 때 쿼리마다 구간의 gcd를 구하라. 풀이 a > b일 때 gcd(a, b) = gcd(a, a - b)임이 잘 알려져있습니다. 따라서 gcd(A[l], ... , A[r]) = gcd(A[l], A[l + 1] - A[l], ... , A[r] - A[r - 1])이 성립합니다. 세그먼트 트리의 각 노..
Randomize Binary Search Trees, Treap INTRO 잘 아려진 BBST(Balanced Binary Search Tree : 균형이진탐색트리)의 종류로는 rb tree, b tree 등이 있습니다. 그러나 위의 rb tree와 같이 대부분의 연산을 \(O(logN)\)에 처리하는 트리는 동작 자체도 복잡하고 구현량이 많기 때문에 직접 구현해가며 PS에 사용하기 어렵습니다. (stl에 있는 것을 가져다 쓰면 좋겠지만 연산을 변형해야하는 경우도 존재하니까요) 그래서 삽입, 삭제 등의 연산에 amortized \(O(logN)\)의 시간복잡도를 가지며 상대적으로 구현량이 적은 Splay Tree를 가장 많이 사용합니다. 하지만 Splay Tree도 zig-zag step 등 헷갈릴만한 요소가 많아서 저는 Treap을 선호합니다. Treap은 일반적인..

티스토리툴바