본문 바로가기

전체 글

 (74)
[BOJ 1762] 평면그래프와 삼각형 https://www.acmicpc.net/problem/1762 1762번: 평면그래프와 삼각형 첫째 줄에 두 정수 N, M이 주어진다. M은 간선의 개수를 나타내는 0 이상의 정수이다. 다음 M개의 줄에는 각 간선이 연결하는 서로 다른 두 정점의 번호가 주어진다. 같은 간선이 중복되어 입력으 www.acmicpc.net Tag : 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개의 간선쌍..
Simulated Annealing INTRO 동아리에서 진행하는 방학 프로젝트에서 다들 휴리스틱을 고르는 분위기여서 저 또한 Simulated Annealing을 적용할 수 있는 문제로 잘 알려진 TSP를 고르게 되었습니다. 언젠가 봐야지하고 6개월쯤 미뤄뒀던 Simulated Annealing을 이제야... (Optimization By Simulated Annealing에도 TSP가 언급되어있네요) 방학 프로젝트의 결과물은 아래 링크에 있습니다. 보고서를 급하게 쓰기도 했고 제가 잘 아는 것도 아니라 오류가 꽤 있을거라 생각됩니다. 너그럽게 봐주세요... https://github.com/kim1109123/Euclidean_TSP GitHub - kim1109123/Euclidean_TSP Contribute to kim110912..
[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은 일반적인..
[BOJ 1725] 히스토그램 https://www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 www.acmicpc.net Tag : DSU 풀이 히스토그램은 모노톤 큐, 분할정복, 세그먼트 트리 풀이가 있다는 것이 잘 알려진 문제입니다. 이 히스토그램을 유니온 파인드로도 풀 수 있는데 저는 이 풀이가 가장 쉽고 구현도 편한다고 생각합니다. 일단 (a[i], i)를 관리하는 벡터 v를 만들고 이를 내림차순으로 정렬합니다. 그리고 이를 순회하며 a[i - 1], a[i + 1]을 보며 a[i..
Efficient Range Minimum Queries using Binary Indexed Trees 주제 : 역원이 존재하지 않는 연산에 대한 구간 쿼리 (펜윅 트리) 펜윅트리에서 요구하는 연산을 $, 이 연산의 역원을 #라고 정의하겠습니다. 흔히 펜윅트리에서 구간 [L, R]에 대한 쿼리를 처리할 때는 ([1, R] 쿼리의 답) # ([1, L) 쿼리의 답)과 같은 형태로 답을 구합니다. $이 +라고 한다면 ([1, R] 쿼리의 답) - ([1, L) 쿼리의 답)을 의미합니다. * 역원은 연산 *에 대해 a * ? = 항등원을 만족하는 연산 ?를 말합니다. 역원이 존재하지 않는 연산은 어떻게 처리해야할까요? 그 예로 \( min(a, ?) = \infty \)를 만족하는 ?는 존재하지 않기 때문에 min에는 역원이 존재하지 않습니다. 그래서 일반적인 형태의 펜윅 트리로는 구간 [L, R]의 min값을..

티스토리툴바