본문 바로가기

백준일지65

[백준] 6497번 전력난 [ 최소 스패닝 트리 ]: 주어진 간선에 대한 정보들을 통해서, 최소의 비용으로 모든 정점을 연결한다.1. 크루스칼 알고리즘모든 가중치를 오름차순으로 정렬 -> 가중치가 가장 작은 간선 선택 -> 두 정점이 연결 안되어 있다면(사이클도 존재 x) 연결 -> 이 과정을 반복1) 서로 같은 부모를 갖는지 판단해주는 함수  2) 1번 과정을 위해서, 부모를 찾는 find 함수  3) 서로 다른 부모일 경우, 두 개의 노드를 연결해야 하므로, 합치는 union 함수출처: https://yabmoons.tistory.com/186 2. 프림 알고리즘임의의 한 점을 선택 -> 이 점과 연결된 정점들 중 짧은 간선 선택 -> 짧은 간선으로 선택된 정점 & 처음 정점들 중 가장 짧은 거리 선택 -> 이 과정을 반복하며.. 2025. 4. 7.
[백준] 1781번 컵라면 #include #define fastio cin.tie(0)->sync_with_stdio(0)using namespace std;const int MAX = 200001;int N;vector problems[MAX];int optimize(){ int ret = 0; priority_queue, less> pq; for(int day=N; day>=1; day--){ for(auto p:problems[day]) pq.push(p); if(!pq.empty()){ ret+=pq.top(); pq.pop(); } } return ret;}int main(){ fastio; cin>>N; for(int .. 2025. 4. 3.
[백준] 1450번 냅색문제 #include #define fastio cin.tie(0)->sync_with_stdio(0)typedef long long ll;using namespace std;int N, C;vector items(30);vector lCom, rCom;void makeCombi(vector& v, int idx, int x, int end){ if(x>C) return; if(idx == end){ v.push_back(x); return; } makeCombi(v, idx+1, x+items[idx], end); makeCombi(v, idx+1, x, end);}int main(){ fastio; cin>>N>>C; for(int i=0.. 2025. 4. 2.
[백준] 달빛 여우 16118번 #include #define fastio cin.tie(0)->sync_with_stdio(0)#define INF 1e9using namespace std;int N,M, cnt;vector> v[4001];int dist[4001];int dist2[4001][2];void dijk(int start){ for(int i=0; i, vector>, greater> pq; pq.push({0, start}); while(!pq.empty()){ int d = pq.top().first; int now = pq.top().second; pq.pop(); if(dist[now] dist[now] + cost){ .. 2025. 3. 31.

티스토리툴바