푸으름

✏️ 문제 링크 https://www.acmicpc.net/problem/14267 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net ✏️ 문제 설명 ✏️ 문제 풀이 1번이 사장이므로 트리에서 루트가 된다고 할 수 있으므로, 1번 노드에서 dfs를 탐색해서 트리를 구성해 줍니다. 당연히 부모 노드를 저장을 해야 합니다. 그런다음 칭찬을 받게 되는데 한 직원이 여러 번 칭찬을 받을 수 있다는 점을 주의해야 합니다. 처음에 저도 한 번만 받을 수 있는 줄 알고 그 방식으로 구현을 해서 틀렸는데 여러 번 받을 수 있..

✏️ 문제 링크 https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net ✏️ 문제 설명 ✏️ 문제 풀이 트리를 구현하고 서브트리의 개수를 구하는 문제입니다. 각 노드의 부모를 저장할 parent배열을 만든 후 parent[루트]의 값을 -1로 설정해줍니다. 루트번호에서 dfs함수를 돌려서 트리를 구성해주는데 저는 여기서 조건을 두 가지를 걸었습니다. 간선이 무방향으로 주어지다 보니 부모 노..

Algorithm 공부 #20 - 이진 트리 이진 트리(Binary Tree) ● 각 노드의 자식 노드의 개수가 2개 이하인 트리 ● 편리하고 직관적인 자료구조 형태는 배열 ● 이진 트리의 종류 1. 편향 이진 트리 : 트리의 노드들이 한쪽 방향으로만 편향돼 생성된 트리, 탐색 속도가 저하되고 공간이 많이 낭비 2. 포화 이진 트리 : 트리의 높이가 모두 일정하며 리프 노드가 모두 꽉 찬 트리 3. 완전 이진 트리 : 마지막 레벨을 제외하고 완전하게 노드들이 채워져 있고, 마지막 레벨은 왼쪽부터 채워진 트리 ● 이진 트리의 순차 표현 1. 루트 노드 : index = 1; 2. 부모 노드 : index = index / 2; (단, 현재 노드가 루트 노드가 아닐 때) 3. 왼쪽 자식 노드 : index ..

Algorithm 공부 #19 - 트리 트리(tree) ● 노드와 에지로 연결된 그래프 ● 순환(cycle)구조를 가지고 있고, 1개의 루트 노드가 존재 ● 루트 노드를 제외한 모든 노드들은 단 1개의 부모 노드를 가짐 ● 트리의 부분 트리(서브 트리)역시 트리의 특징을 따름 ● 트리의 구성 요소 1. 루트 노드 : 트리에서 가장 최상단에 위치하는 노드 2. 부모 노드 : 두 노드 사이의 관계에서 상위 노드에 위치하는 노드 3. 자식 노드 : 두 노드 사이의 관계에서 하위 노드에 위치하는 노드 4. 리프 노드 : 자식 노드가 없는 가장 하위에 위치하는 노드 5. 노드 : 데이터의 index와 value를 표현하는 요소 6. 에지 : 노드와 노드의 연결 관계를 나타내는 선 7. 서브 트리 : 전체 트리에 ..