트리 (Tree)트리는 원소들 간 일대다 관계를 가지는 비선형 자료구조이다. 다른 말로는 원소들 간 계층 관계를 가지는 계층형 자료구조이다. 따라서 트리는 부모와 자식 관계를 갖게 된다. 트리에서는 노드, 차수, 높이, 루트 노드, 리프 노드를 가지고 있는데 각각의 의미는 다음과 같다.노드(Node): 트리의 원소노드의 차수 (Degree): 노드에 연결된 자식 노드의 수. 가장 큰 값이 트리 전체의 차수가 된다.노드의 높이 (Height): 노드의 레벨이라고도 하며, 루트에서 노드에 이르는 간선의 수를 말한다. 이 역시 가장 큰 값이 트리의 높이가 된다.루트 노드 (Root Node): 부모가 없는 노드단말 노드 (Leaf Node): 자식이 없는 노드로 차수가 0인 노드트리는 차수에 따라 구분이 가능..

큐큐(Queue)는 삽입과 삭제가 각각 다른 곳에서 수행되는 자료구조이다. 삭제는 front, 삽입은 rear에서 이루어지기 때문에 선입선출(FIFO, First In First Out)의 구조를 가지는 유한 순서 리스트이다. 큐를 2개로 분리하면 선형 큐와 원형 큐로 나뉠 수 있는데, 원형 큐는 배열로 구현한 선형 큐의 한계점을 보완한다는 특징이 있다. 인덱스의 범위를 벗어나면 원소가 들어갈 자리가 있어도 삽입을 못하는 문제가 발생하는 선형 큐와는 달리, 원형 큐는 배열의 크기보다 작은 원소가 저장되어 있는 경우라면 원소 삽입이 가능하다는 장점이 있다. 아래 자바로 구현한 코드를 함께 보자. 배열을 이용한 원형 큐class CircularQueue { private int front; pri..

스택스택이란 자료를 쌓아 올린 형태의 자료구조로 후입선출(LIFO, Last In First Out)의 구조를 말한다. 스택이 후입선출 구조인 이유는 원소를 top이라고 부르는 한 곳에서만 접근이 가능하기 때문이다. 스택의 삽입 연산은 push라고 하며, 삭제 연산은 pop이라고 한다. Java에서 스택은 Stack 클래스로 구현이 가능하다. 하지만 우리가 알고 있는 Stack과 다르게도 구현이 가능하다. 그 이유는 Stack 클래스가 Vector 클래스를 상속받고 있기 때문이다. Vector 클래스에는 add 메소드가 오버로딩이 되어 있는데, 일반적으로 push 연산을 할 때는 top을 통해서 구현해야 하지만 Vector의 add 메소드에서는 인덱스를 지정하여 원소를 삽입할 수가 있다. Stack에서 ..

해시 (Hash)해시는 임의의 길이의 입력 데이터나 메시지를 고정된 길이의 값이나 키로 변환하는 것을 의미한다. 해시 알고리즘을 해시 함수라고 부르며, 해시 함수로 변환된 값이나 키를 해시값 또는 해시키라고 부른다.  해시 함수 (Hash Function)해시 함수는 원소의 키 값을 원소의 위치로 변환하는 함수이다. 즉, 검색 키 값을 해시 테이블 주소로 매핑하는 함수이다. 해시 함수는 해싱 구현을 위해 결정해야 할 사항 중 하나인데, 해싱은 키가 있는 위치를 계산하여 바로 찾아가는 계산 검색 방식을 말한다.해싱 수행 방법검색 키 값을 해시 함수에 대입하여 주소를 구하고, 구한 주소에 해당하는 해시 테이블 위치로 바로 이동하는 방식이다.검색/삽입/삭제의 평균 시간 복잡도 = O(1) 해시 함수의 종류로는..