퀵정렬(Quick Sort)이란? 퀵정렬은 분할정복에 기반한 알고리즘이다. 분할정복이란 전체를 공략하는 대신 전체를 구성하는 구성 요소들을 나누어 잘게 쪼개진 적을 공략하는 개념이다. 퀵 정렬은 아래와 같은 과정으로 분할 정복을 이용해 정렬을 한다. 데이터 집합 내에서 임의의 기준 요소를 선택하고, 기준 요소보다 작은 요소들은 순서에 관계없이 무조건 기준 요소의 왼편에, 큰 값은 오른편에 위치시킨다. 1에서 나눈 데이터 집합들을 다시 1처럼 임의의 기준 요소를 선택하고 같은 방법으로 데이터 집합을 분할한다. 1,2 과정을 더 이상 데이터 집합을 나눌 수 없을 때까지 반복하면 정렬된 데이터 집합을 얻는다. 이를 토대로 예시를 들어보겠다. 요소 5를 기준으로, 5보다 작은 요소는 왼쪽, 5보다 큰 요소는 오..
삽입 정렬(Insertion Sort) 데이터 집합을 순회하면서 정렬이 필요한 요소를 뽑아내어 이를 다시 적당한 곳에 삽입해 나가는 알고리즘이다. 삽입 정렬도 버블 정렬만큼 구현이 간단해서 프로그래머들에게 애용된다. 삽입 정렬은 아래와 같은 과정을 진행한다.(오름차순 정렬) 데이터 집합에서 정렬 대상이 되는 요소들을 선택합니다. 이 정렬 대상은 왼쪽부터 선택해 나가며, 그 범위가 처음에는 2개지만, 알고리즘 반복 횟수가 늘어날 때마다 1개씩 커진다. 정렬 대상의 최대 범위는 '데이터 집합의 크기 - 1' 이다. 정렬 대상의 가장 오른쪽에 있는 요소가 정렬 대상 중 가장 큰 값을 갖고 있는지 확인한다. 그렇지 않다면 이 요소를 정렬 대상에서 뽑아내고 이 요소가 위치할 적절한 곳을 정렬 대상 내에서 찾는다...
2022.06.16 - [자료구조] - 트리(Tree) 개념 및 구현 트리(Tree) 개념 및 구현 트리는 말 그대로 나무와 유사한 자료구조를 말한다. 이는 사회나 컴퓨터공학에서 흔히 사용되고 있다. 예를 들어보자면 회사 조직도가 있다. 회사의 사장이 나무의 뿌리에 해당한다고 하면, 사 rooftoproom-whale.tistory.com 우리는 앞서 트리에 대한 기본적인 내용에 대해 알아봤다. LCRS 트리는 N개의 자식을 가지는 트리였는데 지금 알아볼 이진 트리는 자식을 최대 2개까지 가질 수 있는 트리이다. 그래서 이름도 이진(Binary) 이다. 자식이 많으면 좋은게 아닌가? 왜 2명으로 제한을 둘까? 라는 의문이 생기는데 이 이진트리를 통해 탐색과 수식 처리하는 알고리즘이 존재하기때문에 이진 트..
트리는 말 그대로 나무와 유사한 자료구조를 말한다. 이는 사회나 컴퓨터공학에서 흔히 사용되고 있다. 예를 들어보자면 회사 조직도가 있다. 회사의 사장이 나무의 뿌리에 해당한다고 하면, 사장 밑에 있는 각 부서의 부장들은 뿌리에서 뻗어 나온 가지라고 할 수 있다. 부장 밑에 있는 차장, 과장, 대리 등은 부장이라는 가지에서 뻗어 나온 잔 가지가 된다. 컴퓨터 공학에서도 활용도가 높은 자료구조인데 우선 운영체제의 파일 시스템이 트리 구조로 이루어져 있고, HTML이나 XML 문서를 다룰 때 사용하는 DOM(Document Object Model)도 트리 구조이다. 이뿐만 아니라 검색 엔진이나 데이터베이스도 트리 자료구조에 기반해서 구현된다. 트리의 구성 요소 트리는 그림과 같이 뿌리(Root), 가지(Bra..
스택은 데이터의 입력과 출력이 이루어지는 공간이 top 하나뿐이고 FILO or LIFO 인 자료구조이다. 큐는 이와 반대로 입력과 출력 공간이 따로 존재하고 제일 먼저 들어간 데이터가 제일 먼저 나오는(FIFO) 자료구조이다. 그렇다면 큐를 왜 사용하는 것일까? 데이터 입력이 폭주하는 경우를 생각해보자. 먼저 입력받은 데이터의 처리가 안 끝났는데 그 뒤에 새로운 데이터가 계속 입력되면 그 데이터는 보관할 곳이 없기때문에 모두 버리게 된다. 이때 밀려드는 데이터를 저장하기위해 큐를 쓴다. 우리는 이런 구조를 자바에서 쉽게 찾아볼 수 있다. 바로 버퍼(Buffer)가 큐를 사용한다. 큐의 주요 기능 : 삽입과 제거 큐의 기본적인 구조는 아래와 같다. 큐는 삽입은 후단(rear), 제거는 전단(front) ..
중위 표기법 후위 표기법 1 + 3 1 3 + 23 / 7 + 12 23 7 / 12 + (117.32 + 83) * 49 117.32 83 + 49 * 1 - 3 * 2 1 3 2 * - 우리 일상적으로 사용하는 계산식을 중위 표기법(Infix Notation)이라 부른다. 이 방법은 사람이 보면 바로 계산이 가능하지만 컴퓨터가 보기엔 계산이 힘들다. 그래서 컴퓨터가 비교적 쉽게 받아 들일 수 있는 표기법이 없을까 하고 나온게 후위 표기법이다. 그럼 후위 표기법(Postfix Notation)이란 무엇일까? 후위 표기법은 역 폴리쉬 표기법이라고도 하는데 이 표기법의 규칙은 연산자를 피연산자 뒤에 위치시키는 것이다. 그래서 계산을 후위표기식으로 한다면 계산식을 쉽게 이해가능하다. 후위 표기식을 계산하는 ..
더블 링크드리스트란? 링크드리스트의 탐색 기능을 개선한 자료구조이다. 링크드리스트는 노드를 찾으려면 헤드에서 테일 방향으로만 탐색할 수 있었는데 더블 링크드리스트는 양방향으로 탐색이 가능하다. 아래는 더블 링크드리스트의 노드 구조이다. class Node { private Object data; private Node prevNode; private Node nextNode; public Node(Object newData) { this.data = newData; this.prevNode = null; this.nextNode = null; } } 주요 연산 링크드리스트와 동일하며 이전 노드를 처리하기 위한 구현이 더 추가될 뿐이다. 노드 생성 Node CreateNode(Object newData) ..
링크드리스트란 기본적으로 배열을 선언할 때 new int [10]으로 크기를 지정해서 선언한다. 허나 배열의 용도에 따라 계속 크기가 변할 수 있다면 결과를 예상해 크기를 선언하기엔 메모리 낭비가 발생하여 애매모호합니다. 이때 유연하게 크기를 바꿀 수 있는 자료구조를 사용해야 하는데 그중에 하나가 링크드리스트이다. 노드 링크드리스트 내의 각 요소는 노드(Node)라고 부른다. 이 노드에는 데이터를 보관하는 필드와 다음 노드와의 연결고리 역할을 하는 포인터로 이루어져 있다. 링크드리스트는 아래처럼 리스트의 첫 번째 노드인 헤드와 마지막 노드인 테일을 갖고 있다. 이런 구조라면 데이터의 크기를 미리 알지 못해도 된다. 데이터가 늘어날 때마다 노드를 만들어 테일에 붙이면 되기 때문이다. 리스트 사이에 노드를 ..
