dongs

이진 탐색 트리(Binary Search Tree) 이진 탐색 트리(Binary Search Tree)는 트리 자료구조의 한 종류로 노드의 차수가 0~2로 자식 노드가 최대 두 개까지만 허용되는 트리이다. 이진 트리와 다르게 부모 노드를 기준으로 작은 값은 왼쪽 노드에 저장되고 큰 값은 오른쪽 노드에 저장된다. 이진 탐색 트리의 특징 이진 탐색 트리는 기본적으로 이진 트리에 데이터의 대소를 비교하여 왼쪽이나 오른쪽 노드에 저장하게 된다. 탐색을 목적으로 한 자료구조이기 때문에 데이터의 중복을 허용하지 않는다. 트리에 데이터가 한쪽 방향으로만 저장되는 경우엔 탐색 속도는 O(N), 포화 이진 트리의 경우 탐색 속도는 O(logN)이다. 중위순회(inorder traversal) 방법으로 순회한다. 이진 탐..

트리 (Tree) 트리는 이름 그대로 하나의 뿌리로부터 가지가 사방으로 뻗어있는 나무를 거꾸로 뒤집어 놓은 형태의 자료구조이다. 그림에서 볼 수 있듯이 하나의 데이터 아래에 여러 데이터가 존재할 수 있는 비선형적인 계층 구조이고 사이클이 존재하지 않는다. 대표적인 사용 예시는 디렉토리 구조, 토너먼트 대진표, 가계도 등이 있다. 트리의 구조와 용어 트리는 루트(Root)에서 시작해서 데이터가 담긴 노드들을 간선(edge)으로 연결한다. 부모 노드와 자식 노드가 있는데 자식 노드는 하나의 부모만 가질 수 있고 같은 부모를 가진 자식 노드들을 형제 노드 관계라고 부르고 자식이 없는 노드는 리프(leaf) 노드라고 부른다. 깊이 (depth) 루트로부터 하위 계층의 특정 노드까지의 깊이. 루트 노드의 dept..

큐 (Queue) 큐는 사전적 의미로 줄을 서서 기다리다, 대기열이라고 정의되어 있다. 단어로 짐작할 수 있듯이 가장 마지막에 추가된 데이터가 가장 먼저 삭제되는 스택과는 반대로 먼저 추가된 데이터가 먼저 삭제되는 선입선출 형태의 자료구조이다. 큐 사용 예제 은행이나 상담원 연결 대기번호 프린터 인쇄 대기열 BFS 큐의 특징 1. FIFO (First In First Out) 먼저 들어간 데이터가 가장 처음에 나오는 선입선출의 자료구조 2. 데이터는 하나씩 추가 / 삭제 데이터가 아무리 많아도 하나씩만 추가하거나 삭제할 수 있다. 3. 두 개의 입출력 방향 추가와 삭제의 방향이 같은 스택이랑 다르게 추가 삭제 방향이 다르다 큐 주요 메서드 및 구현 add() - 큐에 데이터 추가 poll() - 가장 처..

연결 리스트(LinkedList) LinkedList는 선형으로 그룹화된 데이터의 집합으로 데이터와 다음 데이터의 주소를 포함하고 있는 노드들을 선형으로 연결한 자료구조이다. 배열을 기반으로 사용하는 ArrayList는 연속된 공간 안에 메모리를 차지해서 데이터를 읽고 쓸 수 있다. 배열의 크기만큼 메모리를 할당해서 사용하기 때문에 데이터가 배열의 크기보다 많아지면 데이터를 새로 할당하고 추가/삭제 연산은 각 데이터를 앞으로 당기거나 뒤로 밀어야 한다. 반면 노드를 기반으로 한 LinkedList는 연속된 공간이 아니라 메모리 상에 흩어져 있는 노드들을 연결한 자료구조이기 때문에 데이터의 추가 삭제는 ArrayList보다 빠르게 연산할 수 있지만 특정 데이터를 찾는 연산은 노드를 하나하나 참조하여 찾아야..

스택 (Stack) stack은 사전적 의미로 쌓다 포개지다라고 정의되어 있다. 즉, 정의 그대로 데이터를 쌓으면서 관리하는 자료구조라고 할 수 있다. 그림에서 볼 수 있듯이 입력과 출력이 한 방향으로 자료를 쌓으면서 관리하기 때문에 가장 늦게 들어온 데이터가 가장 먼저 나가는 LIFO(Last In First Out) 형태의 자료구조이다. 스택의 특징 1. 하나의 입출력 방향 데이터의 입출력이 방향이 같다. 2. LIFO (Last In First Out) 스택은 입출력이 한쪽 방향으로만 발생하기 때문에 마지막에 들어온 데이터가 제일 먼저 나가는 자료구조이다. 스택 주요 메서드 및 구현 push() - 스택에 데이터 추가 pop() - 스택에 가장 마지막으로 추가된 데이터를 스택에서 삭제하고 데이터를 ..

재귀 함수(Recursive Function) Computer Science에서 재귀는 자신을 정의할 때 자기 자신을 재참조 하는 방법이라고 정의되어 있고 프로그래밍에서 재귀 호출로 많이 사용된다. public class RecursionTest { static void recursion() { System.out.println("Hello"); recursion(); } public static void main(String[] args) { recursion(); } } 위와 같이 자기 자신을 계속 호출하는 메서드를 재귀 함수(Recursive Function)라고 한다. 하지만 위 코드는 main에서 recursion 메서드를 호출하면 recursion 메서드가 자기 자신을 계속 호출하고 종료 조건..