힙 힙은 이진 트리에서 특정한 조건을 이룬 구조입니다. 이진 트리 T의 높이가 h라고 할때 h-1까지 완전 이진 트리이다. 모든 잎 노드는 깊이가 h나 h-1이다. 깊이 h의 모든 잎 노드들의 경로는 h-1의 모든 잎 노드보다 왼쪽에 있다. 힙은 역시 부분 순서 트리(Partial order tree)이기도 한데, 이는 모든 노드가 자식 노드보다 값이 크거나 같은 트리 ($key(parent)\geq key(child)$)입니다. -> 완전 순서 트리 (Total order tree) = 완전 정렬된 트리. 이진 탐색 트리에서는 중복된 값이 불가능하나, 힙에서는 가능합니다. 부모가 자식의 키 값보다 작은 최대 히프(max heap), 부모가 자식 노드보다 작은 최소 히프 (min heap) 두 종류가 존..

트리 트리 = 노드(node)로 이루어진 자료 구조. 하나의 루트 노드가 존재하고, 이로부터 0개 이상의 자식 노드들이 존재합니다. 이 노드들이 서브트리(subtree)를 구성합니다. 루트와 서브 트리, 각각 노드들간은 간선(edge)로 연결되어 있습니다. 그래프의 한 종류로써 트리는 asyclic connected(undirected) graph, 사이클이 없는 비방향성 그래프입니다. 루트 노드 (Root node) : 부모가 없는 노드 (트리의 처음) 잎 노드 (Leaf node) : 자식이 없는 노드 (트리의 마지막들) 부모 노드(Parent node) , 자식 노드(Child node)의 관계가 있음 노드의 깊이(Depth) : 루트노드(0)으로부터 도달하기 위해 거쳐야 하는 간선의 수 (부모 노..

배열, 문자열 배열 여러 개의 동일한 타입의 데이터를 한번에 만들때 사용하는 자료구조입니다. 배열 이름이 상수 포인터의 역할을 하여, 주소로 참조합니다. (첫 번째 인덱스의 주소) 2차원 배열은 첫번째 인덱스가 행, 두번째 인덱스가 열을 의미하며 보통 테이블 처럼 생각하면 됩니다. 하지만 실제 메모리 상에서는 그냥 쭉 나열되어 있는 형태입니다. 배열의 장점으로는 빠르게 데이터에 접근할 수 있고, 배열 생성 이후 데이터를 관리하기 편합니다다. 하지만 배열을 전부 사용하지 않으면 메모리 공간 낭비가 생길 수 있습니다. 동적으로 데이터를 관리하기도 힘듭니다. 문자열 char형이 단어 1글자 밖에 담지 못해서, 문자열을 표현하기 위해 char형 배열을 사용했었습니다. 이때 글자 수+\0 (NULL문자, 문장의 ..