기억을 위한 기록들

www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net #include using namespace std; int map[100][100]; int Check[100]; int Computer = 0; int Line = 0; int cnt = 0; void DFS(int n){ Check[n] = 1; cnt++; for (int i = 1; i > Computer >> Line; for (int i = 0; i ..

www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net #include #include #include #include #include using namespace std; int VerNumber = 0; int LineNumber = 0; int StartNumber = 0; int CheckArr[10001]; vector node[1001]; void BFS() { queue q; q.push(StartNumber); i..

플러드 필 혹은 시드 필은 다차원 배열의 어떤 칸과 연결된 영역을 찾는 알고리즘이다. 이 알고리즘은 그림 프로그램에서 연결된 비슷한 색을 가지는 영역에 "채우기" 도구에 사용되며, 바둑이나 지뢰 찾기 같은 게임에서 어떤 비어 있는 칸을 표시 할 지를 결정할 때에도 사용된다. -출처: ko.wikipedia.org/wiki/%ED%94%8C%EB%9F%AC%EB%93%9C_%ED%95%84 플러드 필 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 4방향 재귀적 플러드 필 플러드 필(영어: flood fill) 혹은 시드 필(영어: seed fill)은 다차원 배열의 어떤 칸과 연결된 영역을 찾는 알고리즘이다. 이 알고리즘은 그 ko.wikipedia.org

연산자 오버로딩을 이용한 sort #include #include #include #include using namespace std; struct Data { int money; int when; Data(int a, int b) { money = a; when = b; } bool operator b.when; } }; int main() { int n, i, j, a, b, res = 0, max = -2147000000; vector T; priority_queue pQ; scanf_s("%d", &n); for (i = 1; i max) max = b; } sort(T.begin(), T.end()); //정렬시 13번줄 return 0; } 사용 예 hyo-ue4study.tistory.com..

#include #include using namespace std; int check[10000]; int dir[3] = { 1,-1,5 }; int main() { int s, e; queue q; cin >> s >> e; check[s] = 1; //현재 시작 위치 q.push(s); int CurTarget = 0; int NextTarget = 0; while (!q.empty()) { CurTarget = q.front(); q.pop(); for (int i = 0; i < 3; i++) { NextTarget = CurTarget + dir[i]; //갈수 있는 위치 조사 if (NextTarget 10000) //범위 벗어날시 continue; if (NextTarget == e) {..

#include using namespace std; int map[10][10]; int ch[10][10]; int cnt = 0; int dx[4] = { 1, 0, -1, 0 }; int dy[4] = { 0, 1, 0, -1 }; void D(int x, int y) { int xx; int yy; if (x == 6 && y == 6) cnt++; else { for (int index = 0; index 6 || yy 6) //범위 벗어남 continue; if (map[xx][yy] == 0 && ch[xx][yy..

#include using namespace std; int n; int result; int arr[10]; int cnt = 0; void D(int L, int sum) { if (L == n) { if (result == sum) { cnt++; } } else { D(L + 1, sum + arr[L]); D(L + 1, sum); D(L + 1, sum - arr[L]); } } int main() { cin >> n; cin >> result; int input; for (int i = 0; i > input; arr[i] = input; } D(0, 0); if (cnt == 0) { cout

basic_string substr(size_type pos = 0, size_type count = npos) const; 문자열의 일부를 리턴한다. 인자 : pos : 첫번째 문자열의 위치 count : 부분 문자열의 위치 #include #include using namespace std; int main() { string a = "Hellow World!"; cout

위상이란?? 즉, 어떤 정점이 다른 사물과의 관계 속에서 가지는 위치나 상태를 말한다. 그래프안에서 인접해 있는 정점 사이의 관계의 '위치'라는 속성이 존재. 그러므로 위상 정렬이 가능하려면, 첫째로 그래프에 방향성이 있어야하고, 둘째로는 그래프내에 사이클이 있어야한다. 이러한 그래프를 DAG(Directed Acyclic Graph)라고 한다. DAG 그래프 예 위상정렬은 두 정점이 이웃 또는 인접관계에 있다는 사실뿐만 아니라 간선이 방향성을 가지는 경우에는 어느 정점이 선이고 어느 정점이 후인지도 설명합니다. 정점은 두 가지 종류의 방향성 간선을 가질 수 있는데 그중 하나는 정점으로 들어가는 진입간선과 다른 하나는 진출 간선입니다. 1. 리스트 하나를 준비 2. 그래프에서 진입 간선이 없는 정점을 리..

배열이나 링크드리스트에서는 특정 데이터를 찾기위해 순차 탐색, 이진 탐색을 사용. 이진 탐색트리에서도 이진탐색을 사용한다. 근데 그래프에서는?? 이와같은 방법들이 쉽게 통하지 않는다. 대표적인 기법 2가지가 있다. 바로 깊이우선탐색과 너비우선탐색이다. 깊이 우선 탐색(DFS) (길 끝까지 깊이 들어간다.) 재귀활용 (or stack stl를 활용) 설명 : 최상단노드부터 말단 노드까지 빠르게 내려가면서 탐색하는 방법으로 보통 경우의 수를 확인 할 때 (사용 예: 바둑, 장기 등) 1. 시작정점을 방문표시 2. 해당 정점과 이웃하고 있는 정점중 아직 방문표시 없는곳을 선택하고 시작정점으로 삼고 dfs시작 다시 1번. 3. 정점에 더이상 방문하지 않은 인접 정점이 없으면 이전 정점으로 돌아가서 2번. 4. ..

정점 : 지점을 나타낸것 간선 : 2개 이상의 정점을 연결한 것 인접(Adjacent) : 나와 이웃하고 있는 정점 경로(Path) : 한 정점에서 다른 정점까지의 길 사이클(Cycle) : 단순 경로의 시작과 종료 정점이 동일한 경로 연결성 : 모든 정점이 서로 연결되어 있는것 방향성 그래프(Directed Graph) : 간선이 방향성을 가짐. 무방향성 그래프(Undirected Graph) : 간선에 방향성이 없음. 그래프는 정점의 집합? 간선의 집합? 정점의 집합 표현 방법 : 배열, 링크드 리스트 등 간선의 집합 표현 방법 : 간선은 그냥 선이 아니라 '인접관계'를 나타냄. 그래서 인접행렬(Adjacent Matrix) 또는 인접리스트(Adjacent List)로 표현 간선의 집한 표현방법 2가..

m.blog.naver.com/PostView.nhn?blogId=kmc7468&logNo=220989121076&proxyReferer=https:%2F%2Fwww.google.com%2F C++에서 RAII가 필요한 이유 2017.4.18 ~ 2017.4.21 김민찬 (C) 2017. kmc7468 all rights reserved. C++에는 RAII라는 독특한 디... blog.naver.com