connecting the dots

이전 포스팅의 스택과 큐는 선형 자료구조라고 부릅니다. 선형 자료구조는 데이터를 순차적으로 나열시킨 구조를 뜻합니다. 이번 포스팅에서는 비선형 자료구조인 트리(Tree)에 대해서 알아봅시다! 트리(Tree)란 ? 비선형이 무엇일까요? 비선형 자료구조는 선형 구조와는 다르게 데이터가 계층적으로 구성되어 있습니다. 비선형 자료구조인 트리는 일반적으로 대상 정보의 각 항목들을 계층적으로 연관되도록 구조화시키고자 할 때 사용하는 자료구조입니다. 즉, 데이터 요소들의 단순한 나열이 아닌 부모 - 자식 관계의 계층적 구조로 표현됩니다. 그렇다면 트리의 구조를 그림과 함께 알아봅시다. 루트, 부모, 자식, 레벨 등 다양한 용어가 존재합니다. 이것들을 한번 정리하고 가야겠죠. node: 트리를 구성하고 있는 각 요소 ..

큐(Queue) 이전 포스팅인 스택에 이어서 큐에 대해 알아보고 배열과 링크드리스트를 이용해 구현해보려고 합니다. 큐(Queue)란? 큐는 줄(Line)이라는 의미를 가지고 있습니다. 지난 번 스택은 선입후출(First In Last Out)이라고 했었죠? 반대로 큐는 선입선출(First In Fitst Out) 형태의 자료구조입니다. 줄로 설명하자면 가장 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황을 떠올려볼 수 있습니다. 큐에서 가장 오래전에 입력된 데이터는 front (head) 라고 하며 가장 최근에 입력된 데이터는 rear (tail) 라고 합니다. 큐는 선입후출의 구조이기 때문에 데이터의 삽입은 rear에서 이루어지고 삭제는 front에서 이루어집니다. 큐의 메소드 - add(e)와 offe..

스택(Stack) 스택이란? 한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조를 의미합니다. 즉 Last In First Out 특성을 가집니다. 스택은 다음과 같은 연산을 사용합니다. - pop() 스택에서 가장 위에 있는 데이터를 삭제합니다. - push(item) item 하나를 스택의 가장 윗 부분에 추가합니다. - peek() 스택에서 가장 위에 있는 데이터를 반환합니다. 탑 포인터가 가리키는 데이터를 반환만 할 뿐, 탑의 인덱스 는 변화시키지 않는 연산을 의미합니다. - isEmpty() 스택이 비어있을 때에 true를 반환합니다. 스택의 구현 스택은 배열이나 링크드리스트를 통해서 구현할 수 있습니다. 다음은 자바로 배열을 사용해 스택을 구현한 것입니다. public class ArrayStac..

오늘은 검색 알고리즘에 대해 다뤄보도록 하겠습니다. '검색'이란 단어, 정말 익숙하죠? 무언가 특정한 데이터를 찾아나갈 때 사용하곤 합니다. 검색의 과정을 정리하며 더 자세하게 설명해보자면 어떠한 특정 항목에 관심이 있고 이는 우리가 주목하고 있는 것입니다. 여기서 이 주목하는 것을 키(key)라고 합니다. 검색 기법의 종류 검색 기법은 다양합니다. 우리는 각 기법의 장단점을 고려하여 알고리즘을 선택해야 합니다. 배열을 활용한 검색 알고리즘에는 일반적으로 세 가지 방법이 있습니다. - Linear Search : 무작위로 늘어놓은 데이터 모임에서 검색을 수행 - Binary Search : 일정한 규칙으로 늘어놓은 데이터 모임에서 아주 빠른 검색을 수행 - Hash : 추가 / 삭제가 빈번하게 일어나는 ..