Storage Gonie

break를 사용하면 가장 가까운 범위에 있는 for문만 멈출 뿐 바깥 for문은 계속된다. #include using namespace std; int main() { for (int i = 0; i < 4; i++){ for (int j = 0; j < 3; j++){ if (j == 0){ cout

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/398 # C++(색을 모두 칠해준 다음, 모든 간선의 양끝 정점 색을 비교함 => 비효율적) #include #include using namespace std; vector arr[20001]; // 인접 리스트 int color[20001]; // 중복방문을 막기위한 check 배열, 단 방문시 색을 저장함 void dfs(int node, int c);// DFS탐색을 진행하며 1, 2를 번갈아가며 정점에 색칠하는 함수 int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); // 테스트 케이스의 개수 입력받기 int k; cin >> k; whi..

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/398 # C++ #include #include using namespace std; vector arr[1001]; // 인접 리스트 int check[1001]; // 중복방문을 막기위한 check 배열 void dfs(int node); // DFS 탐색함수 int main() { // cin, cout 속도 빠르게 하기 ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); // 정점의 개수 n과 간선의 개수 m 입력받기 int n, m; cin >> n >> m; // 연결된 두 정점들에 대한 정보를 받아서 인접리스트 생성 for(int i = 0; i < m; i..

개념을 적용한 문제풀이 # 이진트리의 프리오더, 인오더, 포스트오더 순서를 출력하는 문제 - https://www.acmicpc.net/problem/1991 - 코드상에서 3가지 방법의 차이는 출력을 언제 하는가의 차이이다. - 알파벳을 숫자화 해서 A : 0, B : 1, C : 2, ... i의 값으로 사용하고, 2차원 배열로 A[i][0] = 왼쪽 자식 값, A[i][1] = 오른쪽 자식 값을 저장하는 방식으로 트리를 저장하였음. 자식이 없는 경우 -1을 넣어주어 재귀호출이 끝나도록 하였음. * 이진트리의 순회는 왼쪽 자식과 오른쪽 자식의 값을 구분해 가지고 있는게 출력하기 편함. # 트리의 부모 찾기 - https://www.acmicpc.net/problem/11725 - DFS, BFS 두 ..

트리의 순회(Tree Traversal) - 트리도 그래프이기 때문에 DFS와 BFS 방식 모두 가능하다. - 그런데 트리에서만 가능한 아래의 3가지 방법이 있다.(각각의 차이는 루트 노드의 방문을 언제 하냐의 차이) - 이진트리에서는 아래의 3가지 방법이 모두 가능한데, 자식이 여러개인 트리에서는 '프리오더'와 '포스트오더'만 가능하다. 그 이유는 자식이 여러개인 트리의 경우, '인오더 방식'에서 출력이 어느 부분에 위치해야할지 가늠할 수 없기 때문이다. 프리오더 루트 L R 루트 children 인오더 L 루트 R 포스트오더 L R 루트 루트 children # Pre-order(전위순회) * 그래프의 DFS와 순서가 같음. 1) 루트노드 방문 2) 왼쪽 자식 노드를 루트로 하는 서브 트리를 프리오더..

트리의 개념 # 트리(Tree) - 자료구조의 일종으로 '사이클이 없는 그래프'를 Tree 라고 함(이 이유로 임의의 두 정점 사이의 경로는 오직 1개이다) 따라서, 정점의 개수는 V개이고, 간선의 개수는 V-1개 이다. - 트리는 임의의 두 정점 간의 경로가 오직 1개이기 때문에, BFS를 이용하여 찾아낸 그 경로가 바로 최단거리가 된다. - 주의할점이 있는데 (True) "Tree" 이면 "정점의 개수는 V개이고, 간선의 개수는 V-1개 이다." (False) "정점의 개수는 V개이고, 간선의 개수는 V-1개 이다." 이면 "Tree"이다. 그 이유는 아래와 같은경우 정점이 6개이고, 간선이 5개인데 사이클이 있어서 트리라고 볼 수 없는 반례가 존재하기 때문이다. (True) "정점의 개수는 V개, ..

플러드필 알고리즘 - 어떤 배열을 채우는 알고리즘이며, 어떤 위치와 연결된 모든 위치를 찾는 알고리즘이다. - dx, dy 가 사용됨. 유형1. 동시에 진행되는 탐색이 1개뿐인 것 # 단지에 번호를 붙이는 문제 - https://www.acmicpc.net/problem/2667 - 문제요약 : 정사각형 모양의 지도가 주어지는데, 0은 집이 없는 곳이고 1은 집이 있는 곳이다. 이 때 지도를 보고, 연결된 집의 모임 각각에 번호를 붙이려고 한다. 현재 위치를 기준으로 좌, 우, 아래, 위 중 한 곳이라도 집이 있다면 연결되었다고 할 수 있다. - 이 문제는 (x, y)형태로 값이 주어지지만, 이 값들을 그래프로 보면 연결요소의 개수를 구하는 것과 같다. BFS 혹은 DFS를 이용해서 탐색을 수행하는 것을..

연결요소(Connected Component) # 개념 - 연결요소란, '간선으로 연결된 정점들'이고, 이는 그래프를 구성하는 요소가 된다. - 아래의 경우 1개 혹은 2개의 그래프로 볼 수 있으며, 연결요소가 2개인 것은 변함이 없다. # 연결요소의 개수를 구하는 문제 - https://www.acmicpc.net/problem/11724 - 연결 요소의 개수를 구하는 것은 DFS나 BFS 탐색을 이용해서 구할 수 있다. 1) 정점을 차례대로 시작점으로 두고 DFS혹은 BFS를 진행하는데, check배열이 true로 방문한 상태이면 탐색을 진행하지 않는다. 2) DFS 혹은 BFS를 수행한 횟수를 세어주면 그것이 곧 연결요소의 개수가 된다. 이분 그래프(Bipartite Graph) # 개념 - 그래프..

C++에서는 보통 배열을 선언하면 디폴트 값으로 초기화 되어있는데, 초기화된 값을 2번 사용해야 하는 경우 memset을 사용하게 된다. #include bool check[1001]; int main() { memset(check, false, sizeof(check)); }

이 방식은 c++ 11부터 가능하다. #include #include using namespace std; int main() { vector arr(10, 3); for (int a : arr){ cout