기술 블로그

#include #include #include #include #include using namespace std;///////////////////////////////////////////////////////// 1. k-LCS (2차원 점화식 기반) - O(N^2)// 파일 입력: input_kLCS.txt// 형식: 첫 줄 k, 둘째 줄 문자열 X, 셋째 줄 문자열 Y///////////////////////////////////////////////////////int kLCS(const string& X, const string& Y, int k) { int n = X.size(), m = Y.size(); vector> dp(n + 1, vector(m + 1, 0)); ..

// 통합 그래프 알고리즘 구현 파일// 포함 알고리즘: DFS, TopoSort, SCC(Kosaraju), Kruskal, Prim, WidestPath, EFTF 구간 스케줄링, Box Stacking#include #include #include #include #include #include #include using namespace std;// ========================== 공통 변수 ==========================int V, E;vector>> adj; // 가중치 포함 그래프vector> graph, rev_graph;vector visited;vector parent;// ========================== DFS ==============..

[질문 1]에지가 n−1개인 연결된 그래프는 트리인가?✅ 정답: 예 (항상 트리)트리의 정의: 연결되어 있고 사이클이 없으며 간선이 정확히 n-1개조건 만족: 연결 + n-1개의 간선이면 사이클이 있을 수 없음 → 트리임[질문 2]에지가 n−1개인 사이클이 없는 그래프는 트리인가?❗ 정답: 아니오 (반드시 연결되었다는 보장이 없음)반례: 정점 5개, 간선 4개지만 연결되지 않은 2개의 구성요소 → 트리가 아님요점: 사이클이 없고 간선 수 n-1이면 트리인지 여부는 연결성까지 확인해야 함[질문 3]에지 개수가 n−1을 초과하면 반드시 사이클이 존재하는가?✅ 정답: 예사이클 없는 그래프(즉, 포리스트)의 최대 간선 수는 n-1n개의 정점에 대해 n개 이상 간선이 있다면 사이클이 반드시 존재함[질문 4]사이클..

input.txt로부터 정점 수, 간선 수, 시작 정점 입력 받기간선 입력 (u, v, w)최단 거리 출력최단 경로(경로 역추적 포함) 출력파일 없거나 경로 없을 때 오류 처리#include #include #include #include #include #include using namespace std;// 무한대 정의const int INF = numeric_limits::max();////////////////////////////////////////////////////////// 다익스트라 함수: 최소 거리 및 경로 계산////////////////////////////////////////////////////////void dijkstra(int N, int start, const vec..

// chap06_graph 전체 구현 + 입력 방식 2종류 (직접 addEdge vs 파일 입력)#include #include #include #include #include #include #include using namespace std;const int INF = 1e9; // 무한대 값 정의//--------------------------------------// 1. 인접행렬 표현class GraphMatrix {public: int n; // 정점 수 vector> adj; GraphMatrix(int size) : n(size), adj(n, vector(n, 0)) {} void addEdge(int u, int v) { adj[u][v] = 1; ..

Chaining#include #include #include using namespace std;class HashTable { int size; vector> table;public: HashTable(int m) : size(m), table(m) {} int hash(int key) { return key % size; } void insert(int key) { int idx = hash(key); table[idx].push_front(key); // 삽입은 맨 앞에 } bool search(int key) { int idx = hash(key); for (int val : table[id..

1번a) 인접 행렬의 경우 n x n의 배열이 필요해서 시간복잡도가 o(n^2) 입니다.하지만 인접리스트의 경우 각 노드의 연결된 부분만 저장하므로 o(n+m) 입니다. 따라서 간선이 적은 sparce graph의 경우 인접리스트가 더 효율적입니다. b) 인접행렬의 경우, 각 정점에서 다른 모든 정점을 확인해야 하므로 o(n^2)의 시간이 걸립니다. 인접리스트는 각 노드의 실제 연결된 간선만 확인하믈 o(n+m)의 시간에 탐색이 가능하기에 DFS/BFS 알고리즘의 일반적인 시간복잡도입니다. c) 인접행렬은 n x n 배열을 재할당해야 하므로 정점 추가가 어렵고 비용이 크지만 인접리스트는 단순히 리스트에 빈 항목을 추가하면 되므로 정점 추가가 간편합니다. 2번무방향 단순그래프란?무방향 : 간선에 방향이 없..

Floyd-Warshall Algorithm가중치 방향 그래프 G=(V,E) V={1,2, ..., n}모든 노드 쌍들간의 최단경로의 길이를 구함d^k[i,j]중간에 노드 집합 {1,2,...,k}에 속한 노드들만 거쳐서 노드 i에서 j까지 가는 최단경로 길이i.j 사이 어떤 노드도 경유하지 않고 가는 것은 무한대이다 라고 표시합니다. edge가 있으면 edge의 weight로 아니면 무한대로 표시합니다. 노드 i에서 j까지 가는데 1에서부터 n사이의 노드를 지날 수 있고 이것은 i에서 j까지 가는데 어떤 노드를 지나도 상관이 없다라는 것이고 이것이 i에서 j까지 가는 최단경로입니다. i^n[i, j] = 최단경로의 길이다 모든 i.j를 보는 것입니다. wij 자체가 만약 i에서 j로가는 edge가 있..

노드들을 반복해서 bellman-ford를 만들 수 있는 것에서 아무 에지나 릴렉스하지 않고 특별한 조건을 만족하는 relax에만 만족합니다. 그것이 dijkstra 알고리즘입니다. 초기화는 똑같습니다. 출발 노드만 distance estimator가 0이고 출발을 해서 첫번째 round에서 relax 할 때 distance 값이 최소인 노드를 찾습니다. 최소인 노드로부터 나가는 edge들만 relax합니다. 두번째 round에서는 다시 distance가 최소인 애를 찾는데 dijkstra 알고리즘은 이미 이전 round에서 선택이 되어서 edge들을 두번 선택할 필요는 없습니다. 이 노드의 최단 경로는 현재 노드가 가지고 있는 d[s] = 델타[s,s]입니다.dijkstra는 s만 0이고 나머지는 무한..

해쉬 테이블은 dynamic set을 구현하는 효과적인 방법 중 하나적절한 가정하에서 평균 탐색, 삽입, 삭제시간 o(1)보통 최악의 경우 o(n)해쉬함수는 h를 사용하여 키 k를 T[h(k)]에 저장h : U -> {0, 1, ... , m-1} 여기서 m은 테이블의 크기, U는 모든 가능한키들의 집합키 k가 h(k)에 해슁되었다고 말함 각 키에 대한 해쉬 함수값을 그 키를 저장할 배열 인덱스로 저장하는 것입니다. h(x) = x % m 이렇게 하고 search 할 때도 1024라면 24이기에 24에 가서 찾으면 됩니다. 해쉬함수의 예모든 키들을 자연수라고 가정 문자열ASCII 코드 : C=67, L=76, R=82, S=83문자열 CLRS는 (67*128^4) + (76 * 128^2) /// ..