#include #include using namespace std;const int ROOT = 1;int unused = 2;const int MX = 10000 * 500 + 5; // 최대 등장 가능한 글자의 수bool chk[MX];int nxt[MX][26];int c2i(char c) { return c - 'a';}void insert(string& s) { int cur = ROOT; for (auto c : s) { if (nxt[cur][c2i(c)] == -1) nxt[cur][c2i(c)] = unused++; cur = nxt[cur][c2i(c)]; } chk[cur] = true;}bool find(str..
알고리즘/코드
#include using namespace std;/** * @brief ans 변수를 사용하는 lower_bound * @param arr 오름차순 정렬된 배열 * @param val 찾고자 하는 값 * @return arr 내에서 (arr[idx] >= val)을 만족하는 가장 작은 idx * (없으면 arr.size() 리턴) */int my_lower_bound_ans(const vector& arr, int val) { int l = 0; int r = (int)arr.size() - 1; int ans = (int)arr.size(); // 없을 경우 기본값 while (l = val) { ans = mid; // 조건 만족..
1. 크루스칼(Kruskal) 그래프 표현: 보통 간선 리스트 형태로 가지고 있습니다.핵심:모든 간선을 비용 기준으로 오름차순 정렬유니온 파인드(Union-Find)로 사이클 확인비용이 작은 간선부터 차례대로 MST에 추가#include using namespace std;struct Edge { int u, v; // 간선을 잇는 두 정점 long long cost; // 간선의 가중치};// 전역 혹은 클래스 내 Union-Findstatic const int MAXN = 100000; // 정점 최대 개수 예시 (원하는 만큼)int parentSet[MAXN];int rankSet[MAXN];// Union-Find find 함수(경로 압축)int Find(int x) { ..
#include #include #include #include #include using namespace std;const int MAX_SIZE = 101;int parent[MAX_SIZE];int rankArr[MAX_SIZE];void initialize() { for (int x = 0; x rankArr[B]) { parent[B] = A; } else { parent[B] = A; rankArr[A]++; }}int main(int argc, char** argv) { ios::sync_with_stdio(false); cin.tie(nullptr); return 0;}유니온 파인드란?유니온 파인드(..
#include using namespace std;// CCW 함수: 세 점의 방향성을 판단합니다.int ccw(int x1, int y1, int x2, int y2, int x3, int y3) { // 벡터 AB와 벡터 AC의 외적 계산 int crossProduct = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1); // 방향성 판단 if (crossProduct > 0) { return 1; // 반시계 방향 (Counter ClockWise) } else if (crossProduct > x1 >> y1 >> x2 >> y2 >> x3 >> y3; // CCW 결과 확인 int result = ccw(x1,..
#include #include #include using namespace std;const int INF = 1e9;bool bellmanFord(int start, int n, vector>& edges, vector& dist) { dist[start] = 0; // 모든 간선을 최대 (V-1)번 반복 for (int i = 0; i > n >> m; vector> edges; for (int i = 0; i > u >> v >> w; edges.push_back({u, v, w}); } int start; cin >> start; vector dist(n, INF); bool noNegativeCycle = bellmanFord(..
#include #include #include #include using namespace std;const int INF = 1e9; // 무한을 나타내기 위해 사용vector dijkstra(int start, int n, vector>>& graph) { vector dist(n, INF); // 최단 거리 테이블을 무한으로 초기화 priority_queue, vector>, greater> pq; dist[start] = 0; pq.push({0, start}); // 시작 노드로 가기 위한 비용은 0으로 설정 while (!pq.empty()) { int cost = pq.top().first; // 현재 노드까지의 비용 int u = ..
LIS#include #include #include using namespace std;int LIS(const vector& arr) { if (arr.empty()) return 0; vector lis; for (int i = 0; i arr = {10, 22, 9, 33, 21, 50, 41, 60, 80}; cout LCS#include #include #include using namespace std;int LCS(const string& X, const string& Y) { int m = X.size(); int k = Y.size(); vector> lcs(m + 1, vector(k + 1, 0)); for (int i = 1; i
#include #include #include // std::min 사용using namespace std; // std 네임스페이스를 전역적으로 사용const int INF = 1e9; // 무한대를 의미하는 큰 값void floydWarshall(vector>& dist, int V) { // 모든 정점 쌍 (i, j)에 대해 i에서 j로의 최단 경로 계산 for (int k = 0; k > V; // 거리 행렬 초기화 vector> dist(V, vector(V)); cout > dist[i][j]; } } // 플로이드-워셜 알고리즘 수행 floydWarshall(dist, V); // 결과 출력 cout
https://www.acmicpc.net/problem/2960#include #include #include #include #include using namespace std;bool check[1000001];int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin >> n >> k; int count = -1; for (int i = 2; i
