yoongrammer

목차 이진 탐색 트리 (BST, Binary Search Tree) 이진 탐색 트리란 정렬된 이진트리로써 다음과 같은 속성을 가지고 있습니다. 노드의 왼쪽 하위 트리에는 노드의 키보다 작은 키가있는 노드 만 포함됩니다 노드의 오른쪽 하위 트리에는 노드의 키보다 큰 키가있는 노드 만 포함됩니다. 왼쪽 및 오른쪽 하위 트리도 각각 이진 검색 트리 여야합니다. 중복된 키를 허용하지 않습니다. 이러한 이진 탐색 트리의 특성 때문에 효율적인 검색이 가능합니다. 생성 예시 50, 15, 62, 80, 7, 54, 11 주어진 요소를 사용하여 BST를 생성하는 과정은 다음과 같습니다. 50을 트리의 루트로 트리에 삽입합니다. 다음 요소를 읽고 루트 노드 요소보다 작 으면 왼쪽 하위 트리의 루트로 삽입합니다. 그렇지 ..

목차 트리 순회 (Tree Traversal) 트리의 모든 노드들을 방문하는 과정을 트리 순회(TreeTraversal)라고 합니다. 선형 자료 구조(연결 리스트, 스택, 큐 등)는 순차적으로 요소에 접근하지만 트리 자료구조는 다른 방식을 사용해야 합니다. 일반적으로 트리 순회에는 다음과 같은 방법들이 있습니다. 전위 순회 (Preorder) 중위 순회 (Inorder) 후위 순회 (Postorder) 이러한 순회는 보통 재귀로 쉽게 구현할 수 있습니다. 전위 순회 (Preorder Traversal) 전위 순회는 깊이 우선 순회(DFT, Depth-First Traversal)이라고도 합니다. 트리를 복사하거나, 전위 표기법을 구하는데 주로 사용됩니다. 트리를 복사할때 전위 순회를 사용하는 이유는 트리..

목차 [자료구조] 이진트리 (Binary tree) 알아보기 이진트리(Binary tree)란 모든 노드들이 둘 이하의 자식을 가진 트리입니다. 이진트리 유형 전 이진트리 (Full Binary Tree or Strict Binary Tree) 전 이진 트리는 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리입니다. 완전 이진 트리 (Complete Binary Tree) 완전 이진 트리는 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있는 트리입니다. 마지막 레벨은 꽉 차 있지 않아도 되지만 노드가 왼쪽에서 오른쪽으로 채워져야 합니다. 포화 이진 트리 (Perfect Binary Tree) 포화 이진 트리는 모든 내부 노드가 두 개의 자식 노드를 가지며 모든 잎 노드가 동일한 깊이 또는 레벨을 ..

목차 트리 (Tree) 트리 (Tree)란 노드들이 나무 가지처럼 연결된 비선형 계층적 자료구조입니다. 트리는 다음과 같이 나무를 거꾸로 뒤집어 놓은 모양과 유사합니다. 트리는 또한 트리 내에 다른 하위 트리가 있고 그 하위 트리 안에는 또 다른 하위 트리가 있는 재귀적 자료구조이기도 합니다. 컴퓨터의 direcory구조가 트리 구조의 대표적인 예가 될 수 있습니다. 트리 구조에서 사용되는 기본 용어 노드 (Node) 트리를 구성하고 있는 기본 요소 노드에는 키 또는 값과 하위 노드에 대한 포인터를 가지고 있음. A, B, C, D, E, F, G, H, I, J 간선 (Edge) 노드와 노드 간의 연결선 루트 노드 (Root Node) 트리 구조에서 부모가 없는 최상위 노드 root node : A 부..

목차 큐(Queue) 구현하기 in Go 큐는 선입 선출 (FIFO) 원리를 따라 정렬된 데이터 구조입니다. golang에서 Slice를 사용하면 쉽게 큐를 구현할 수 있습니다. built-in 함수인 append를 사용하여 enqueue를 구현합니다. 배열의 첫 번째 요소를 잘라내는 방식으로 dequeue를 구현합니다. 구현 package main import "fmt" type Queue []interface{} //IsEmpty - 큐가 비어있는지 확인하는 함수. func (q *Queue) IsEmpty() bool { return len(*q) == 0 } //Enqueue - 큐에 값을 추가하는 함수. func (q *Queue) Enqueue (data interface{}) { *q = a..

목차 스택(Stack) 구현하기 in Go 스택은 후입 선출 (LIFO) 원리를 따라 정렬된 데이터 구조입니다. golang에서 Slice를 사용하면 쉽게 스택을 구현할 수 있습니다. built-in 함수인 append를 사용하여 push를 구현합니다. 배열의 마지막 요소를 잘라내는 방식으로 pop을 구현합니다. 구현 Go 언어로 구현하면 다음과 같습니다. package main import "fmt" type Stack []interface{} //IsEmpty - 스택이 비어있는지 확인하는 함수 func (s *Stack) IsEmpty() bool { return len(*s) == 0 } //Push - 스택에 값을 추가하는 함수. func (s *Stack) Push(data interface{..

목차 스택(Stack) 구현하기 in C 스택 자료형을 구현하는 방법은 일반적으로 다음 방법들을 사용합니다. 배열 기반으로 구현 동적 배열을 기반으로 구현 연결 리스트로 구현 배열 기반으로 구현 배열을 사용하여 스택을 구현하는 방법입니다. 배열 index를 추적하는 top변수를 사용합니다. top은 -1로 초기화합니다. top이 -1이라면 스택이 비어있다는 의미이고 배열 크기-1이라면 스택이 가득 찼다는 의미입니다. push연산은 top을 1 증가시키고 값을 top위치에 저장하도록 구현합니다. pop연산은 top을 1 감소시키도록 구현합니다. C 언어로 구현하면 다음과 같습니다. #include #include #include typedef struct ArrayStack { int top; int ca..

목차 [자료구조] 큐 (Queue) 큐는 먼저 집어넣은 데이터가 먼저 나오는 FIFO (First In First Out) 구조로 저장하는 선형 자료구조입니다. 실제 예로 매표소 대기열에서 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황과 비슷합니다. 나중에 집어넣은 데이터가 먼저 나오는 스택(Stack)과는 반대되는 개념입니다. 큐 표현 큐는 FIFO(First In First Out) / LILO(Last In Last Out) 순서를 따릅니다. FIFO : 처음 들어온 값이 처음에 나가는 것 LILO : 마지막에 들어온 값이 마지막에 나가는 것 큐에 끝(Rear)에서 요소를 추가하는 작업을 enqueue라고 하며 큐에 맨 앞(Front)에서 요소를 제거하는 작업을 dequeue라고 합니다. 가득 찬 ..

목차 [자료구조] 스택 (Stack) 스택은 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조로 되어 있습니다. 식당에 쌓여있는 접시들이 좋은 예입니다. 순서대로 쌓인 접시가 스택 구조와 같습니다. 접시가 필요하면 제일 위에 있는 접시부터 사용하며 가장 아래 있는 접시는 마지막에 사용됩니다. 스택은 LIFO (Last In First Out) / FILO (First In Last Out) 순서를 따릅니다. LIFO : 마지막으로 들어온 값이 처음으로 나가는 것 FILO : 처음 들어온 값이 마지막에 나가는 것 스택은 완전히 꽉 찼을 때 Overflow 상태라고 하며 완전히 비어 있으면 Underflow 상태라고 합니다. 삽입(Push)과 제거(Pop)는 모두 Top이라는 스택의 한쪽 끝에서만 일어납니..

목차 [자료구조] 연결 리스트 (Linked list) 연결 리스트는 데이터와 포인트로 구성된 노드 간의 연결(link)을 이용해서 리스트를 구현한 자료구조입니다. 연결 리스트는 배열의 고정크기의 단점을 보완하기 위해 만들어졌으며 배열과 달리 연속적인 메모리 공간에 저장되어 있지 않기 때문에 연결이 필요합니다. 연결 리스트 표현 연결 리스트는 아래 그림과 같이 포인터를 사용하여 각 노드를 연결합니다. 그림에서 알 수 있는 사실은 아래와 같습니다. Head 는 리스트의 처음을 나타냅니다. 노드는 데이터와 다음 노드를 가리키는 Next 포인터로 구성돼 있습니다. 각 노드는 next 포인터를 사용하여 다음 노드와 연결됩니다. 마지막 노드는 null을 가리켜 리스트의 끝을 나타냅니다. 시간 복잡도(Time co..