Storage Gonie

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

영상 : https://youtu.be/IJIXjmUtbbQ 1. Congratulations! - 축하해 2. Look who's married! - 누가 결혼했는지 봐! 3. And just in time to, I hear ( 투아이히얼 ) - 때마침 들었단다. @ just in time : 때마침 4. What? Ross! - 무슨소리에요? 로스! 5. So If you've got this all under control, I'm just .. (유브) - 너가 이 모든걸 수습할 수 있다면, 나는 그냥.. 6. I just wanted you to know / that you have made us happier. (원디드) - 나는 단지 너가 우리를 얼마나 기쁘게 만들었는지 알았으면해. 7. ..

연결요소(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

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/390 # C++ #include #include #include #include #include using namespace std; vector vec[100001]; // 인접리스트 int check[100001]; // bfs를 위한 check 배열 int dist[100001]; // 루트로부터의 거리를 저장할 배열 void bfs(int x); int main() { int n; cin >> n; // 입력받아서 인접리스트 만들기 for (int i = 0; i > s; //끝정점 및 가중치를 입력받아 인접리스트에 추가. while(true){ int p..

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터7-3-트리-문제풀이 # C++(DFS, 인접리스트를 이용한 풀이) #include #include using namespace std; int e; // 간선의 개수 vector vec[100001]; // 인접리스트 bool check[100001]; // check배열 int parent[100001]; void dfs(int x); int main() { //정점의 개수 cin >> e; //입력을 받아 인접리스트 만들기 for (int i = 0; i > a >> b; // 주어진 간선이 양방향이라고 하였으므로 vec[a].push_back(b); vec..

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터7-3-트리-문제풀이 # C++(2차원 배열로 왼쪽자식과 오른쪽 자식을 저장하는 방식) # include using namespace std; int arr[26][2]; void preOrder(int x){ if(x == -1) return; cout > parent >> leftChild >> rightChild; // 부모노드 parent = parent - 'A'; // 왼쪽 자식노드의 값 삽입 if (leftChild == '.') arr[parent][0] = -1; else arr[parent][0] = leftChild - 'A'; // 오른쪽 자식노드의 값 삽입 if (rightChild == ..

https://www.facebook.com/dgtgrade/posts/1340177956041067?hc_location=ufi https://www.facebook.com/dgtgrade/posts/1328790023846527?hc_location=ufi https://www.facebook.com/dgtgrade/posts/1854447711280753?hc_location=ufi https://www.facebook.com/dgtgrade/posts/1855100104548847?hc_location=ufi

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터6-3-그래프-그래프의-탐색 # C++(인접 행렬 사용) #include #include #include // memset using namespace std; int v, e, startNum; int arr[1001][1001]; // 인접행렬 bool check[1001]; // check배열 void dfs(int x); void bfs(int x); int main() { /*정점의 개수, 간선의 개수, 탐색시작 정점의 번호 입력받기*/ cin >> v >> e >> startNum; /*입력을 받아 인접행렬 만들기*/ while(e--){ int x, y; cin >> x >> y; arr[x][y] ..