mondegreen

[Part2-Chapter04-Clip04] - 백준 14267 회사 문화 1상사가 칭찬을 받으면 직속 부하를 연쇄적으로 칭찬하기 때문에 방향이 없는 그래프인 트리 구조를 활용하면 된다. 직속으로 타고 내려가다가 가장 말단 사원까지 점수를 더해줘야 하기 때문에 DFS 방식으로 점수를 더해주는 방식으로 구현한다. 먼저 입력값을 받아주는데 각 직원의 직속 상사를 입력할 때, 입력받는 순서인 인덱스가 '부하'이고 입력 받는 값이 '상사'이다. ArrayList를 원소로 가지는 배열을 생성해서 배열의 인덱스는 상사, 그 원소인 리스트는 연결된 부하로 값을 입력하면 트리 탐색이 가능한 형태가 된다. 이렇게 입력 받고 나면 칭찬을 순서대로 받아주면서 직속 부하들에게까지 점수를 입력하는데 이 때, 칭찬을 받을 때마다..

[Part2-Chapter04-Clip02]- 백준 11725 트리의 부모 찾기트리도 그래프의 일종이다. 단, 순환이 없는 그래프이다. 그래프 문제를 풀 때와 마찬가지로 인접 리스트를 선언하고 간선의 양 끝 정점을 리스트에 담아줬다. 부모를 찾는 함수를 구현하는 데 약간 어려움을 겪었다. 정점들을 연결된 순서대로 타고 가는데 루트 노드인 1부터 시작해서 따라가다 보면 직전의 정점이 즉, 나를 호출한 정점이 부모가 되는 로직이다. 이미 방문한 경우는 제외하고 자식 노드를 계속 찾아나가면서 자식 노드를 찾을 때마다 정답 배열에 부모인 직전 정점을 넣어주면 문제를 해결할 수 있다.package BaekJoon.tree;import java.util.ArrayList;import java.util.Scanner..

class Solution{ public int solution(int n, int a, int b) { int answer = 0; // 트리로 구현했을 때 1라운드의 위치를 인덱스로 두고(리프노드) // /2를 해가며 부모노드가 같아졌을 때 만나는 것으로 판정 // /2한 횟수가 지나 온 라운드 수 a = a+n-1; b = b+n-1; while(a!=b){ a /=2; b /=2; answer++; } return answer; } }

자료구조 트리에 대한 개념 트리는 그래프의 한 종류이며 비선형 자료구조로 계층적 관계를 표현한다. - DAG(Directed Acyclic Graph; 방향성이 있는 비순환 그래프)의 한 종류이다. 트리는 하나의 루트 노드를 가지며 루트 노드는 0개 이상의 자식 노드를 가지고 있다(즉, 루트 노드만 있어도 트리) 트리는 노드와 노드를 연결하는 간선으로 구성되어 있으며 트리에는 사이클이 존재하지 않는다. 노드: 트리를 구성하는 기본 요소 (노드의 구성요소: key, value, 하위 노드에 대한 포인터) 간선(링크, 엣지, 브랜치): 노드와 노드를 잇는 연결 간선의 수는 노드의 수 - 1이다. 루트 노드: 트리 내에서 단 한 개 존재, 부모 노드가 없는 노드 리프(말단, 외) 노드: 자식 노드가 없는 노드..