최소 간선 수를 만족하는 그래프 구성
문제의 핵심은 제약 조건을 만족하면서 간선의 총 개수를 최소화하는 그래프를 구성하는 것이다. 단순히 직관적으로 접근하면 함정에 빠지기 쉬우므로, 수학적 분석을 통해 최적해를 도출해야 한다.
문제 분석
다음 조건을 만족하는 그래프를 구성해야 한다:
모든 정점의 차수는 k 이상
차수가 정확히 k인 정점들 사이에는 간선이 존재하지 않음
두 정점 사이에는 최대 ...
8월 11일 22:58에 게시됨
알고리즘 문제 해결 전략: 비트마스크부터 수론까지
격자 상태 탐색 및 비트마스크 활용
첫 번째 문제는 주어진 격자에서 특정 행과 열을 선택하여 제거했을 때, 남아있는 검은색 셀의 개수가 정확히 K 가 되는 경우의 수를 찾는 문제이다. 행과 열의 개수가 작으므로 비트마스크를 이용하여 모든 조합을 탐색하는 방식이 적합하다.
각 행과 열에 대해 선택 여부를 비트로 표현하여 반복문을 구성한다. 선택된 행이나 열에 포 ...
8월 10일 07:39에 게시됨
AGC007 문제 풀이
A - Shik and Stone
시작점 \((1, 1)\)에서 경로를 시뮬레이션하며 이동하면 된다.
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 15;
string grid[MAX_N];
bool visited[MAX_N][MAX_N];
int main() {
int rows, cols;
cin >> rows >> cols;
string padding(cols + 2, '.');
grid[0] = grid[rows + 1] = pad ...
8월 6일 23:41에 게시됨
NOI2025 예선 대비 문제 풀이 정리
[NOI2025 예선 R1] A - 기본 사이클 구조
다음의 수학적 원리를 활용한다:
Cayley 정리
n개의 노드가 k개의 연결 성분으로 구성되어 있을 때, 이들을 연결하기 위해 k-1개의 간선을 추가하는 방법의 수는 n^(k−2) × ∏(i=1 to k) size_i이다.
이 정리를 바탕으로, 입력 그래프에 이미 사이클이 존재하는 경우 답을 직접 계산할 수 있다.
반면, 초기 상태에서 사이 ...
7월 24일 03:13에 게시됨
LeetCode 일일 문제 2024/11/25-2024/12/1
743. 네트워크 지연 시간
너비 우선 탐색(BFS)을 사용하여 현재 노드 k에서 시작하여 k와 연결된 모든 노드를 탐색합니다. 만약 노드 to의 시간을 업데이트할 수 있다면, 노드 to를 큐에 추가하여 나중에 고려합니다.
def calculateNetworkDelay(networkConnections, nodeCount, startNode):
"""
:type networkConnections: List[List[int]]
...
7월 20일 22:52에 게시됨
문제 풀이 기록: 다양한 알고리즘 문제들
A. 버스 문제 (3)
주어진 s_i, t_i 값들의 최소와 최대를 각각 L, R로 정의합니다. p < min(s_i)인 경우, 우리는 항상 R까지 이동하게 됩니다. 이후에는 s_i > t_i인 구간만 남게 됩니다.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e6 + 5;
int n, q, m, mn, mx;
long long w[MAXN], f[MAXN], d[MAXN], a[MAXN], b[MAXN], p[MAXN], z[MA ...
7월 17일 21:06에 게시됨
자바로 구현하는 서로소 집합(Union-Find) 자료구조와 경로 존재 여부 판별
서로소 집합(Union-Find) 자료구조의 이해
서로소 집합(Disjoint Set) 또는 유니온-파인드(Union-Find)는 그래프 이론에서 두 원소가 동일한 집합에 속하는지 판별하거나, 동적 연결 상태를 관리하는 데 특화된 자료구조입니다.
핵심 원리 및 동작 방식
1차원 배열을 사용하여 트리 구조를 표현하며, 각 인덱스는 노드를 의미하고 저장된 값은 해당 노드의 부모를 나타냅 ...
7월 7일 05:14에 게시됨
캡슐화된 체인 포워드 스타 구현
체인 포워드 스타 클래스 (캡슐화 버전)
struct ChainForwardStar {
vector<int> head, to, next, weight;
int edgeCount = 0;
ChainForwardStar(int capacity) {
head.assign(capacity + 1, -1);
to.resize(capacity + 1);
next.resize(capacity + 1);
weight.resize(capacity + 1);
}
void connect ...
7월 4일 17:41에 게시됨
2025-5-21 네트워크 유량 문제 풀이 노트
2025-5-21 네트워크 유량 문제 풀이 노트
le0n님의 강의를 기반으로 정리한 네트워크 유량 문제 풀이 노트이다.
목차
CF2046 D - For the Emperor!
ICPC 2023 Polish E - Express Eviction
ABC397 G - Maximize Distance
ARC142 E - Pairing Wizards
CF1427 G - One Billion Shades of Grey
ICPC 2024 Shanghai K - Knights of Night
AGC031 E - Snuke the Phantom Thief
...
7월 3일 17:12에 게시됨
NOIP 2023 알고리즘 문제 풀이
문제 1: 간단한 문자열 처리
첫 번째 문제는 매우 straightforward합니다. 각 행의 문자를 추출하여 정렬한 후 최소 문자열을 만들고, 역순으로 배치하여 최대 문자열을 만들면 됩니다.
코드 확인하기
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<typename T>
void processRange(T* start, T* end, function<void(T*)& ...
6월 29일 21:06에 게시됨