Algorithm2 BCC(이중 연결 요소) 이쁘게 구현하기 이중 연결 요소를 제가 이해할 수 있도록 설명한 글이 없어서 조금 더 직관적인 방식으로 구현한 BCC에 대해 소개해보고자 합니다. 먼저, 알고리즘의 대략적인 설명은 이렇습니다.1. 아무 정점에서 DFS 스패닝 트리를 구성한다.2. 백엣지가 있는 경우, 양 끝점을 잇는 경로 위의 점들은 모두 같은 BCC에 포함되므로 묶어준다.3. 2. 에서 중복 간선이 있는 경우를 예외 처리한다. 더 자세한 디테일들은 코드와 함께 설명하겠습니다. #include using namespace std;#define int long long#define fastio; cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);const int mod=1e9+7, MOD=9982443.. 2025. 11. 29. [비재귀] 세그먼트 트리 & 느리게 갱신되는 세그먼트 트리 세그먼트 트리를 비재귀로 구현하는 것이 얼마나 아름답고 즐거운 일인지 아시나요? 모르는 사람이 꽤 많은 것 같아, 비재귀 세그먼트 트리의 아름다움을 조금 더 많은 사람들에게 알리기 위해 설명글을 작성해 보았습니다.각각의 목표는 BOJ 2042(구간 합 구하기), BOJ 10999(구간 합 구하기 2)를 푸는 것을 목적으로 하겠습니다.(괄호를 클릭하면 코드를 볼 수 있습니다.)rpdd# 비재귀 세그먼트 트리비재귀 세그먼트 트리의 경우, 세그먼트 트리의 리프 노드가 모두 같은 깊이에 있는 것이 구현에 훨씬 유리하기 때문에 완전 이진 트리를 만들어 구현하는 것을 기본으로 합니다. 노드의 인덱스를 다음과 같이 정하고 배열로 생각하면 좋습니다.(코드 - 배열 정의)const int X=4;int seg[1리프 노.. 2025. 5. 14. 이전 1 다음
