취미와 밥줄사이

트리(Tree)란 트리는 노드로 이루어진 자료구조 트리는 하나의 루트 노드를 갖는다. 루트 노드는 0개 이상의 자식 노드를 갖는다. 그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있고, 이는 반복적으로 정의된다. 노드(node)들과 노드들을 연결하는 간선(edge)들로 구성되어 있다. 트리에는 사이클(cycle)이 존재할 수 없다. 노드들은 특정 순서로 나열될 수 도 있고 그럴 수 없을 수도 있다. 각 노드는 부모 노드로의 연결이 있을 수도 있고, 없을 수도 있다. 각 노드는 어떤 자료형으로 표현 가능하다. 비선형 자로구조로 계층적 관계를 표현한다. Ex) 디렉터리 구조, 조직도 그래프의 한 종류 사이클(cycle)이 없는 하나의 연결 그래프(Connected Graph) DAG(Directed Ac..

배열(Array)이란? 배열은 메모리 상에 데이터(원소)를 연속하게 배치한 자료구조 배열은 같은 타입의 데이터를 여러개 나열한 선형 자료구조 연속적인 메모리 공간에 순차적으로 데이터를 저장 배열은 선언할 때 크기를 정하면, 그 크기로 고정이 된다. 선언된 값은 다시 배열을 선언하지 않으면 변경할 수 없다. 배열의 주소를 살펴보면, 한 칸마다 배열의 자료형의 크기를 가지고 있따. 배열의 자료형이 int라면, 배열 한 칸의 크기는 int(4byte)가 되는 것이다. 배열은 인덱스를 통해서 배열에 있는 요소에 접근할 수 있다. 배열의 특징 추가적으로 소모되는 메모리 양(=overhead)가 거의 없다 Cache hit rate가 높다. cache hit ratio: 적중률 = (캐시히트 횟수)/(전체 참조횟수..