[취업준비일지] - 32

1.B-Tree는 이진 트리를 확장한 방식으로 
블럭 단위로 입출력하는 데이터를 관리하기 위해
블록의 한도에 맞춰 데이터를 넣는 방식으로 되어있다.

B+Tree는 B-Tree의 변형구조로
인덱스 역할만 하는 노드가 추가로 있어 사이즈를 더 많이 이용할 수 있다.
하지만 탐색 시 B-Tree와는 다르게 leaf노드까지 내려가야 해서 시간이 더 걸릴 수 있다는 단점이 있다.

여기서 중요한 점은 하드디스크와 같은 2차 저장장치일 경우에 유용하다는 점이며 각 노드마다 저장하는 데이터는 디스크 블록이나 저장장치에서 하나의 블록과 최대한 유사한 크기로 압축해 트리의 높이를 낮추고 효율을 높이는 방식이라는 것이다.





(1).백준 9372 상근이의 여행은 비행기를 타고 이동할 수 있는 경로를 받은 다음 모든 국가를 여행하는데 사용하는 최저 비행기 가짓수를 구하는 문제였다.
처음에는 연결되기만 하는 예제라서 저렇게 나오고 다른 방식으로는 어떻게 나오는지 모르는 상황이었는데 비행 횟수가 아닌 비행기 가짓수가 포인트라는 사실을 알고나니 아주아주 단순한 트리의 총 간선 갯수는 정점-1개라는 포인트를 묻는 문제라는 사실을 알 수 있었다.

let input = `2
3 3
1 2
2 3
1 3
5 4
2 1
2 3
4 3
4 5`.split('\n')
let result = []

for(let i = 1 ; i < input.length ; i++){
    let [a,b] = input[i].split(' ').map(Number)
    result.push(a-1)
    i += b
}

console.log(result.join('\n'))