자료구조

[자료구조] B Tree

B 트리는 이진트리에서 발전되어 모든 리프 노드들이 같은 레벨을 가질 수 있도록 자동으로 밸린스를 맞추는 트리입니다. 정렬된 순서를 보장하고, 멀티레벨 인덱싱을 통한 빠른 검색을 할 수 있기 때문에 DB에서 사용하는 자료구조중 한 종류입니다. B트리는 하나의 노드에 다수의 정보를 저장할 수 있습니다. 최대 M개의 자식을 가질 수 있는 트리를 M차 B트리라고 하며, 다음과 같은 특징을 갖습니다. 노드는 최대 M개부터 M/2개 까지의 자식을 가질 수 있습니다. 노드에는 최대 M-1개부터 M/2 -1 개의 키가 포함될 수 있습니다. 노드의 키가 x개 라면 자식의 수는 x + 1개입니다. 최소 차수는 자식수의 하한 값을 의미하며, 최소 차수가 t 라면 M=2t-1을 만족합니다. (최소 차수가 2라면 3차 B트리..

[프로그래머스] 크레인 인형뽑기-python3

문제 설명 게임개발자인 "죠르디"는 크레인 인형뽑기 기계를 모바일 게임으로 만들려고 합니다. "죠르디"는 게임의 재미를 높이기 위해 화면 구성과 규칙을 다음과 같이 게임 로직에 반영하려고 합니다. 게임 화면은 "1 x 1" 크기의 칸들로 이루어진 "N x N" 크기의 정사각 격자이며 위쪽에는 크레인이 있고 오른쪽에는 바구니가 있습니다. (위 그림은 "5 x 5" 크기의 예시입니다). 각 격자 칸에는 다양한 인형이 들어 있으며 인형이 없는 칸은 빈칸입니다. 모든 인형은 "1 x 1" 크기의 격자 한 칸을 차지하며 격자의 가장 아래 칸부터 차곡차곡 쌓여 있습니다. 게임 사용자는 크레인을 좌우로 움직여서 멈춘 위치에서 가장 위에 있는 인형을 집어 올릴 수 있습니다. 집어 올린 인형은 바구니에 쌓이게 되는 데,..