connecting the dots

이번 포스팅에서는 퀵정렬의 개념과 방식에 대해 알아보고 자바로 구현해보겠습니다. 퀵정렬이란 ? 퀵정렬은 Divide and Conquer(분할정복) 알고리즘 중 하나입니다. 즉 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아 원래의 문제를 해결하는 전략이죠. 분할정복 방식은 보통 순환 호출을 이용해 구현합니다. 이러한 분할정복 알고리즘의 특징은 평균적으로 매우 빠른 수행속도를 자랑한다는 것입니다. - Divide : 동일한 문제에 대해서 더 작은 부분으로 나누는 것 - Conquer : 작은 부분들을 재귀적으로 해결하는 것 퀵정렬의 과정 그렇다면 퀵정렬은 어떻게 수행되는 걸까요? 무엇을 기준으로 Divide 해서 문제를 해결하는 걸까요? 여기에서 말하는 '기준'을 pivot(피봇)이..

이전 포스팅의 스택과 큐는 선형 자료구조라고 부릅니다. 선형 자료구조는 데이터를 순차적으로 나열시킨 구조를 뜻합니다. 이번 포스팅에서는 비선형 자료구조인 트리(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..