이진탐색트리(Binary Search Tree)이란? 이진탐색트리란 다음과 같은 특징을 갖는 이진트리를 말한다. ( #이진트리 - 각 노드의 자식 노드가 최대 2개인 트리) 1. 각 노드에 중복되지 않는 키(key)가 있다. 2. 루트노드의 왼쪽 서브 트리는 해당 노드의 키보다 작은 키를 갖는 노드들로 이루어져 있다. 3. 루트노드의 오른쪽 서브 트리는 해당 노드의 키보다 큰 키를 갖는 노드들로 이루어져 있다. 4. 좌우 서브 트리도 모두 이진 탐색 트리여야 한다. 예를 들어 다음과 같은 트리가 이진탐색트리이다. 이진 탐색 트리의 특징 이진 탐색 트리는 기존 이진트리보다 탐색이 빠르다. 이진 탐색 트리의 탐색 연산은 트리의 높이(height)가 h라면 O(h)의 시간 복잡도를 갖는다. 이러한 효율적인 탐..
트리의 순회 이 게시글에서 설명하는 트리의 순회는 이진트리를 기준으로 한다. 이진 트리에 대해 모른다면 다음 포스팅을 참고하자. [자료구조] 트리(Tree)의 개념, 이해, 종류 | 이진 트리, 전 이진 트리, 완전 이진트리, 포화 이진 트리(Tree)의 개념 트리는 노드로 이루어진 자료구조로 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조이다. 트리는 계층적 관계를 표현하는 자료구조이다. 트리는 다음과 같은 특징들을 code-lab1.tistory.com 트리의 순회 중 중위(inorder) 순회, 전위(preorder) 순회, 후위 순회(postorder) 순회에 대해 알아보자. 여기서 설명할 때 L은 Left, V는 Visit, R은 Right를 의미한다. 즉 왼쪽 서브 트리, 노드 방문, 오..
트리(Tree)의 개념 트리는 노드로 이루어진 자료구조로 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조이다. 트리는 계층적 관계를 표현하는 자료구조이다. 트리는 다음과 같은 특징들을 갖는다. 1. 트리는 하나의 루트 노드를 갖는다. 2. 루트 노드는 0개 이상의 자식 노드를 갖는다. 3. 자식 노드 또한 0개 이상의 자식 노드를 갖는다. 4. 노드(Node)들과 노드들을 연결하는 간선(Edge)들로 구성되어 있다. 트리에는 사이클(cycle)이 존재할 수 없다. 여기서 사이클이란 시작 노드에서 출발해 다른 노드를 거쳐 다시 시작 노드로 돌아올 수 있다면 사이클이 존재한다고 한다. 트리는 사이클(cycle)이 없는 하나의 연결 그래프(Connected Graph)라고 할 수 있다. 트리의 노드는 s..
피보나치 수열 피보나치수열은 제2항 까지는 1, 제3항부터는 바로 앞의 두 항을 더한 수가 반복되는 수열이다. 1, 1, 2, 3, 5, 8, 13, 21, 34, 55... 이러한 피보나치수열을 구현할 때는 보통 재귀를 통해 표현하게 된다. c언어에서는 아래와 같이 구현 할 수 있다. 1 2 3 4 5 6 int fibo(int n){ if (n
큐(Queue) 란? 큐는 컴퓨터의 기본적인 자료구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out) 구조로 저장하는 형식을 말한다. 나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념이다. 스택은 아래 부분이 막히고 윗 부분이 뚫린 통과 같았다면, 큐는 양 쪽이 뚫린 통과 같다. 스택이 가장 윗부분에서 데이터를 넣고 꺼냈다면, 큐는 front 에서 Dequeue(데이터를 꺼냄) 연산이 진행되고, rear 부분에서 Enqueue(데이터를 넣음) 연산이 진행된다. c언어 구현 큐는 배열 혹은 연결리스트로 구현할 수 있다. 배열로 구현할 시에는 여러가지 문제점이 발생할 수 있다. 여기서는 연결리스트를 이용해 큐를 구현해보도록 한다. 1. 노드 정의, ..
스택(Stack) 이란? 스택 자료구조는 마치 접시가 쌓이는 것과 비슷하다. 당신이 접시를 쌓는다면 아래부터 위로 차근차근히 접시를 쌓게 될 것이다. 이 때 가장 위에 있는 접시를 가장 먼저 꺼낼 수 있을 것이고 가장 아래에 있는 접시는 가장 나중에 꺼낼 수 있을 것이다. 스택도 이와 동일하다. Last In First Out(LIFO) 구조로 가장 나중에 들어간 원소가 가장 먼저 나오게 된다. 스택의 연산은 Push, Pop 으로 단순하다. Push 연산시 가장 위에 원소를 추가하게 되고, Pop 연산시 가장 위의 원소를 반환한다. C언어 구현 스택을 구현 할 때는 배열로 구현할 수도 있고, 연결리스트(Linked List)를 이용해 구현할 수도 있다. 여기서는 배열을 이용해 간단히 구현해본다. 1. ..
배열과 연결리스트는 순차적으로 데이터를 저장한다는 점에서 비슷하다. 두 자료구조에 대해서 알아보자. 배열(Array) 배열은 논리적 저장순서와 물리적 저장순서가 일치하는 자료구조이다. 즉 인덱스(index)로 해당 원소에 접근 할 수 있다. 따라서 원소의 인덱스값을 이용하면 O(1)에 해당 원소에 접근 할 수 있다. 그러나 삭제 또는 삽입의 과정에서 추가적인 시간이 소요될 수 있다. 예를 들어 아래와 같은 상황에서 배열의 첫번째 자리(Arr[0])에 새로운 원소를 추가한다고 하자. 위와 같은 상황에서 Arr[0] 에 데이터 10을 추가하기 위해서는, Arr[0] 부터 Arr[4] 까지 모든 원소가 한 칸 씩 오른쪽으로 이동하게 된다. 즉, 원소를 삽입할 때 최악의 경우 모든 원소들을 1씩 옮기는 작업이 ..
정의 Divide and Conquer(분할정복)은 해결하기 힘든 큰 문제를 작은 문제로 분할하여 해결(정복)한 후 병합하는 알고리즘이다. 접근법 분할정복은 보통 다음과 같은 3단계의 과정을 거친다. 1. Divide(분할) : 문제를 더 작은 문제들로 분할 2. Conquer(정복) : 분할한 작은 문제들을 해결한다. 3. Combine(병합) : 작은 문제들의 해결법을 병합해 큰 문제의 해결법을 찾는다. 특징 1. 문제를 나눌 때 보통 재귀(recursion)를 많이 사용한다. 2. 재귀(recursion)를 이용할 때 오버헤드가 커 메모리를 많이 사용할 수 있다. 예시 Merge Sort(병합 정렬) 병합 정렬은 분할정복의 대표적인 예이다. n개의 데이터를 가진 배열을 오름차순으로 정렬하기 위해 병..
연결리스트(Linked List)란? -연결리스트(Linked List)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조이다. - 각 노드는 다음 노드를 가리키는 포인터를 포함한다. - 다음 노드를 가리키는 포인터는 다음 노드의 주소를 값으로 가지고 있다. - 각 노드의 포인터 변수는 다음 노드의 데이터의 주소를 값으로 가진다. 또한 각 포인터 변수의 주소도 따로 존재한다. (그림에 나타난 주소는 정확하지 않다. 이해를 돕기 위해 임의로 설정했다. 실제 주소값은 저런식으로 저장되지 않는다) 단순연결리스트(Singly Linked List)의 구현 가장 간단한 연결리스트인 단순 연결리스트를 구현해보자. 여러 구현 방법이 있지만, 아래 내용들을 응용하면 다양한..