LiJell's 성장기

Binary index Tree 2진법 인덱스 구조를 활용해 구간 합 문제를 효과적으로 해결해 줄 수 있는 자료구조 다른 이름으로 fenwick tree라고도 함 정수에 따른 2진수 표기 정수 2진수 표기 7 00000000 00000000 00000000 00000111 -7 11111111 11111111 11111111 11111001 0이 아닌 마지막 미트를 찾는 방법 특정한 숫자 K의 0이 아닌 마지막 비트를 찾기 위해선 K & -K 계산하면 됨 K & -K 계산 결과 예시 정수 K 2진수 표기 K & -K 0 00000000 00000000 00000000 00000000 0 1 00000000 00000000 00000000 00000001 1 2 00000000 00000000 000000..

트리(Tree) 자료구조 트리는 가계도와 같은 계층적인(hierarchy) 구조를 표현할 때 사용할 수 있는 자료구조 나무를 뒤집어 놓은 모양을 생각하면 됨 1. 트리 관련 용어 root node: 부모가 없는 최상위 노드 뒤집은 나무의 최상위는 나무의 뿌리. ROOT!! leaf node: 자식이 없는 노드 뒤집은 나무의 최하위는 나뭇잎. LEAF!! size: 트리에 포함된 모든 node의 개수 depth: root node부터의 거리 친척들 촌수 셀 때 생각하면 됨 depth of root node = 0 height: depth 중 최대값 degree: 각 노드의 (자식 방향) 간선 개수 몇개 자식이랑 연결 되어 있는지 자식 두개랑 연결되어 있으면 2 트리의 크기가 N일 떄, 전체 간선의 개수는 ..