전체 글

0. 사전 지식 Undirected Graph DFS Traversal makes Forest// Undirected Graph는 시작점이 어디든 Tree 개수 일치 Directed Graph는 시작점 따라 Tree 개수가 다름. 1. 정의 Strongly Connected => 모든 쌍에서 길이 다 있음. 2. 특성 가질 수 있는 Edge 3종류 Cross, Back, Forward Edge Leaf Node에서 좌-> 우 Cross Edge가 불가능 한 이유는 DFS Traversal알고리즘 상 더이상 인접 노드가 없을 때 까지 깊이 들어가는데 좌->우 Cross Edge 존재 시 우측 노드를 이미 추가했었어야 한다. ∴ DFS Traversal Algorithm에 모순. 3. 알고리즘 1. DFS ..

1. 개념 위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 위상정렬을 가장 잘 설명해 줄 수 있는 예로 대학의 선수과목(prerequisite) 구조를 예로 들 수 있다. 만약 특정 수강과목에 선수과목이 있다면 그 선수 과목부터 수강해야 하므로, 특정 과목들을 수강해야 할 때 위상 정렬을 통해 올바른 수강 순서를 찾아낼 수 있다. 이와 같이 선후 관계가 정의된 그래프 구조 상에서 선후 관계에 따라 정렬하기 위해 위상 정렬을 이용할 수 있다. 정렬의 순서는 유향 그래프의 구조에 따라 여러 개의 종류가 나올 수 있다. 위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하지 않아야 한다. 즉, 그래프가 비순환..

1. 정의복사 생성자-> '값'이 복사되는 것임.같은 값을 갖는 여러 Object, Instance 생성시 유용. 2. 구문const student &s 처럼 const reference사용 (원본의 data를 변경할 일은 없기 때문에) 3. 예제12345678910111213141516171819202122232425262728293031323334353637383940414243 #include using namespace std; class student{ private: int score; string name; public: student(){ //Default Constructor this->score = 0; this->name = " "; } student(string name, int s..

1. 문제 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다. www.acmicpc.net 2. 해결 IDEA Union-Find 알고리즘 (초기상태) Parent Index 1 2 3 4 5 6 7 8 9 Node Index 1 2 3 4 5 6 7 8 9 바이러스 근원 노드가 '1'이므로 1과 같은 Group으로 Union 되는 노드의 Parent Index가 '1'이 되..

0. 소인수분해 정의임의의 자연수 N을 마지막 나머지가 '1'이 나올 때 까지 '소수'로 나누어 곱으로 표현한 것. EX)120이란 수를 소인수분해 한다면? N이란 숫자를 몫 i로 나누어 떨어지는지 검사하고 나누어 떨어지면 떨어지는 동안 계속 나누기/ 나누어 떨어지지 않으면 i + 1 N의 나머지가 1이될 때까지 (그림에서는 5에서 멈춤) 1. 문제https://www.acmicpc.net/problem/1165311653번: 소인수분해첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.www.acmicpc.net2. 핵심 IDEAQ. i(몫)의 범위?저번 포스팅에서 소수를 검사하는 아이디어에서 '에라토스테네스의 Idea'에서 살펴 보았듯이임의의 자연수 N이 제곱근 이하에서 소수로 나누어..

1. 문제 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. www.acmicpc.net 2. 핵심 아이디어 DFS는 재귀 (Stack) BFS는 Queue가 비어있을 때 까지. 3. 실수 (1) Node별 연결상태를 저장한 vector Array List를 오름차순으로 출력해주기 위해서 sort 필요 (2) Array Index가 0부터인지 1부터 시작인지 체크..