살구의 개발자 첫걸음을 위한

1. 트리의 탐색 - 이진 트리가 아닌 경우 인오더 방식의 순회는 어떤 자식을 루트로 잡아 줄지가 명확하지 않아 불가능- 트리의 탐색은 DFS/BFS 알고리즘을 이용해서 할 수 있음(어차피 그래프이기 때문)- 트리는 사이클이 없는 그래프이기 때문에- 임의의 두 정점 사이의 경로는 항상 1개이다.- 따라서, BFS 알고리즘을 이용해서 최단 거리를 구할 수 있다.- 이유 : 경로가 1개라 찾은 그 경로가 최단 경로 2. 문제- 트리의 부모 찾기(11725번)#include #include #include using namespace std; vector a[100001];int parent[100001];bool check[100001]; void bfs(int x) {queue q;q.push(x);che..

1. 트리의 순회(Tree Traversal)- 트리의 모든 노드를 방문하는 순서이다.- 그래프의 경우에는 DFS와 BFS가 있었다.- 트리에서도 위의 두 방법을 사용할 수 있지만, 트리에서만 사용할 수 있는 세 방법이 있다.- 프리오더, 인오더, 포스트오더 또는 전위 순회, 중위 순회, 후위 순회- 세 방법의 차이는 루트 방문을 언제 하냐의 차이이다. 1) 프리오더 -노드 방문 -왼쪽 자식 노드를 루트로 하는 서브 트리 프리오더 -오른쪽 자식 노드를 루트로 하느 서비 트리 프리오더 -그래프의 DFS 탐색과 순서가 같다. 2) 인오더 -왼쪽 자식 노드를 루트로 하는 서브 트리 인오더 -노드 방문 -오른쪽 자식 노드를 루트로 하느 서비 트리 인오더 3) 포스트오더 -왼쪽 자식 노드를 루트로 하는 서브 트리..

1. 트리(Tree)- 자료구조의 일종- 사이클이 없는 그래프- 정점의 개수 V- 간선의 개수 V-1 - 정점의 개수가 V 이고 간선의 개수가 V-1 이면 트리일까? 답) NO, 연결되어 있다는 조건이 있어야 트리 2. 루트 있는 트리 (Rooted Tree)- 루트가 있는 트리- 아래 그림에서 1번이 루트이다. - 루트부터 아래로 방향을 정할 수 있다. 1) 부모(Parent) - 1은 2의 부모, 2는 4의 부모 2) 자식(Children)- 2는 1의 자식, 4는 2의 자식- 3의 자식 : 6, 7 3) 단말 정점(Leaf Node)- 자식이 없는 정점- 4, 5, 6, 7 4) 형제(Sibling)- 같은 부모를 가지면 형제- 4와 5는 형제- 6과 7은 형제- 2와 3도 형제 5) 깊이(Dept..

1. Term Project 9466번 2. 단지번호붙이기 2667번#include #include #include using namespace std; int a[25][25]; // a[i][j] : (i,j) 집int check[25][25]; // (i,j)를 방문안했으면 0, 했으면 단지번호int ans[25 * 25];int n; int nextX[4] = { 0, 0, 1, -1 };int nextY[4] = { 1, -1, 0 , 0 };void bfs(int x, int y, int number) {queue q;q.push(make_pair(x, y));check[x][y] = number;while (!q.empty()) {x = q.front().first;y = q.front()...

1. 반복수열(2331번) (내 소스)#include #include #include using namespace std; vector d;bool check[236197];int p; int next(int a) {int ans = 0;while (a > 0) {ans += pow(a % 10, p);a /= 10;} return ans;} // 수열을 구해나가다가, 반복된 값이 나오면 해당 값을 returnint go(int x) {if (check[x] == true) {return x;}check[x] = true;d.push_back(x);go(next(x));} int main(void) {int a;cin >> a >> p;int result = go(a);int cnt = 0;for (au..

1. 순열 사이클- 순열이 주어졌을 때, 순열 사이클의 개수를 찾는 문제- 이전에 풀어봤던 연결 요소 문제와 유사- 이 문제의 경우, 각 정점마다 하나의 간선만 존재하므로 인접행렬이나 인접리스트로 구현하지 않아도 됨- 1차원 배열로 각 정점에 연결된 정점을 저장해서 구현 2. 문제 정답 #include using namespace std; int a[1001]; // a[i]는 i번 정점에 연결된 정점int check[1001]; void dfs(int x){if(check[x]==true){return;}check[x]=true;dfs(a[x]);} int main(void){int t;cin >> t;while(t--){int n;cin >> n;for(int i=1;i> a[i];check[i]=f..

1. 이분 그래프(Bipartite Graph, 1707번)- 그래프를 다음과 같이 왼쪽(A), 오른쪽(B) 으로 나눌 수 있으면 이분 그래프라고 한다. - A에 포함되어 있는 정점끼리 연결된 간선이 없음- B에 포함되어 있는 정점끼리 연결된 간선이 없음- 다음 정점의 색을 현재 정점의 색(집합)과 다르게 표시하면서 DFS 탐색을 했을 때, - 이분 그래프가 되기 위해서는 나와 연결된 정점들은 나와 다른 색(집합)이어야 한다.- 나와 연결된 정점이 나와 같은 색(집합)이면 이분 그래프가 아니다. 2. 정답 코드#include #include using namespace std; vector a[20001];int check[20001];// check[i] = 0 : 정점 i 방문하지 않음// 1 : 정..

1. 연결 요소(11724번)1) 연결 요소(Connected Component) - 그래프가 아래 그림과 같이 연결되어 있지 않은 경우가 있을 수도 있다.- 이렇게 나누어진 각 각의 그래프를 연결 요소라고 한다.- 연결 요소는 해당 연결 요소에 속한 모든 정점을 연결하는 경로가 있어야 한다.- 또, 다른 연결 요소에 속한 정점과 연결하는 경로가 있으면 안된다.- 아래 그래프는 총 2개의 연결 요소로 이루어져 있다.- 연결 요소를 구하는 것은 DFS나 BFS 탐색을 이용해서 구할 수 있다. 2) 정답 코드 #include #include using namespace std; vector a[1001];bool check[1001]; void dfs(int x) {check[x] = true;for (in..

1. 그래프의 탐색 - 목적 : 모든 정점을 1번씩 방문- DFS : 깊이 우선 탐색, 최대한 깊숙히 많이 방문, 재귀 또는 stack 구현- BFS : 너비 우선 탐색, 최대한 넓게 많이 방문, queue 구현, 모든 가중치가 1일 때 최단거리 구할 수 있음 2. 깊이 우선 탐색(Depth First Search) - 스택을 이용해서 갈 수 있는 만큼 최대한 많이 가고 (stack에 push)- 갈 수 없으면 이전 정점으로 돌아간다. (stack에서 pop)- stack이 비면 탐색 종료- 재귀 호출을 이용해서도 구현할 수 있다. (예시 1) - 인접행렬, 재귀 호출void dfs(int x){check[x]=true;printf("%d", x);for(int i=1;i m >> s;for (int i..

1. 그래프의 표현(Representation of Graph) - 인접행렬, 인접리스트, 간선리스트- 아래와 같은 그래프는 정점이 6개, 간선이 8개 있다. - 간선에 방향이 없기 때문에, 방향이 없는 그래프이다.- 정점 : {1,2,3,4,5,6}- 간선 : {(1,2),(1,5),(2,5),(2,3),(3,4),(2,4),(4,5),(4,6)} 2. 인접 행렬(Adjacency Matrix)- 정점의 개수를 V라고 했을 때- V * V 크기의 이차원 배열을 이용한다.- A[i][j] = 1(i->j 간선이 있을 때), 0 없을 때 (예시1) - n개의 정점, m개의 간선, 가중치 없는 양방향 그래프#include using namespace std;int a[10][10];int main(void)..