Coding/Algorithm 썸네일형 리스트형 BOJ(백준) 1068 - 트리 https://www.acmicpc.net/problem/1068 자료구조(트리), 리프노드, 차수, 트리 방향성루트 있는 트리가 주어지고, 각 노드들의 부모노드가 주어진다. 어떤 한 노드를 제거 했을 때, 남는 리프노드(단말노드)의 개수를 구하는 프로그램을 작성하라. 시간복잡도 : O(N) N은 트리 노드의 개수 점검해봐야 할 부분-루트가 있는 트리의 방향성-리프 노드의 성질 https://github.com/jongwuner/Algorithm/blob/master/BOJ/1068.cpp 1234567891011121314151617181920212223#includeint p[50], a, c[50];int main(){ int n, d; scanf("%d", &n); for (int i = 0; i.. 더보기 BOJ(백준) 11725 - 트리의 부모찾기 https://www.acmicpc.net/problem/11725 자료구조(트리), 트리 순회루트가 1인 트리가 주어지면(트리의 속성 : 정점N개, 간선N-1개), 2번 ~ N번 노드의 부모노드를 출력하는 프로그램을 작성하라 시간복잡도 : O(N)N은 트리의 정점 개수 점검해봐야할 부분- 부모를 기억한 채로 순회- 루트가 주어지면 방향성도 이미 정해진 것 https://github.com/jongwuner/Algorithm/blob/master/BOJ/11725.cpp 12345678910111213141516171819202122232425262728#include#include#define MAX 100005using namespace std;vector adj[MAX];bool visit[MAX].. 더보기 BOJ(백준) 4803 - 트리 https://www.acmicpc.net/problem/4803 자료구조(트리), 연결요소, 그래프의 정점과 간선이 주어지면, 포레스트(트리의 집합)속에서 트리의 갯수를 찾는 프로그램을 작성하라. 시간복잡도 : O(N) N은 포레스트 내에 정점 개수. 연결요소 검사를 하고나서 다시 중복으로 확인하지 않는다. 점검해봐야 할 부분-자료구조를 왜 깊게 공부해야 하는지 교훈을 주는 문제. (노드의 개수 = 간선의 개수 - 1)+순수 자료구조의 속성에 대해 증명해보고 체화되어있지 않으면 문제를 너무 어렵게 풀게 된다.- 트리는 방향성 없는 상태에서 사이클이 없는 연결요소라는 개념- 그래프와 트리에서의 사이클 판단은 다르다.- 사이클찾는 아이디어(visit, finish 자료구조)? 총 연결요소 개수 - 사이클 .. 더보기 BOJ(백준) 16437 - 양 구출 작전 https://www.acmicpc.net/problem/16437 자료구조(트리), 트리의 순회N개의 섬으로 이루어진 나라가 있다. N-1개의 섬에서 1번 섬으로 가는 경로는 항상 유일하다. 각 섬에는 늑대와 양들이 살고 있으며, 한 섬에 두 종이 같이살고 있지는 않다. 양들은 1번 섬으로 이동하려고 한다. 양이 늑대가 사는 섬을 지나갈 때, 양은 늑대에게 잡아먹힌다. 이 때, 늑대 1마리는 양 1마리만 잡아먹을 수 있다. 살아서 1번 섬으로 도착하는 양의 수를 구하여라. 시간복잡도 : O(N) 후위 순회로 1번섬에 최종적으로 도착하는 양의 수를 구하면 된다. 점검해봐야 할 부분- '경로는 유일하다.'에서 트리 임을 해석 https://github.com/jongwuner/Algorithm/blob/m.. 더보기 이전 1 2 3 다음
