힙 자료구조 힙 자료구조는 원소 값들 중에서 최대값과 최소값을 구하는데 효율적인 자료 구조를 의미합니다. 트리의 개념을 공부하고 싶으면 04 트리와 이진트리 (Tree & Binary Tree) 기본 여기를 참조해주세요. 힙은 완전 이진 트리의 형태를 가지면서 동시에 다음과 같은 힙 성질을 만족해야 합니다. ● 부모노드가 자식노드보다 큰 경우 - 최대 힙 ● 부모노드가 자식노드보다 작은 경우 - 최소 힙 ▶ 이번 게시글에서는 최대 힙을 기준으로 설명 하겠습니다. 왼쪽 최대 힙을 보면 모두 부모 노드의 값이 자식 노드 값보다 큰 형태를 이루고 있습니다. 부모 노드 50의 경우 자식 노드 25와 40보다 크며, 부모 노드 25는 자식 노드 12와 14보다 큰 형태를 이루고 있습니다. 즉, 힙의 이러한 성질 ..

트리 (Tree) 계층적인 구조를 표현하기 위한 자료구조로 여러 노드가 한 노드를 가리킬 수 없는 구조를 의미합니다. 일반적으로 조직도, 디렉토리 구조등을 생각하면 됩니다. 스택이나 큐와 같은 선형구조가 아닌 뒤집어놓은 나무 모양 같은 계층구조를 가지며, 탐색이나 계층적 구조를 가져야 하는 데이터를 다루는데 많이 사용됩니다. 트리의 특징 ▶ 트리는 노드(A,B,C,D,E,F)와 노드들 사이를 이어주는 링크로 이루어져 있습니다. 트리의 노드가 n개라면 링크의 개수는 n-1개가 됩니다. 최상위 노드 A를 루트 노트라고 부르며 B,C를 가지노드라 하며 D,E,F와 같이 자식을 가지지 않는 최하위 노드들을 리프노드라고 부릅니다. ▶ 트리는 기본적으로 부모-자식 관계를 가집니다. A노드 입장에서는 B,C의 자식 ..

원형큐 (Circular Queue) 원형 큐는 선형 큐의 문제점을 보완하기 위한 자료구조입니다. 앞선 포스팅에서 선형큐의 문제점은 rear이 가르키는 포인터가 배열의 마지막 인덱스를 가르키고 있을 때 앞쪽에서 Dequeue로 발생한 배열의 빈 공간을 활용 할 수가 없었습니다. 원형큐에서는 포인터 증가 방식이 (rear+1)%arraysize 형식으로 변환하기 때문에 배열의 첫 인덱스부터 다시 데이터의 삽입이 가능해집니다. ■ Enqueue rear의 포인터를 1증가 시키고 그 위치에 데이터 삽입이 이루어집니다. 만약 rear+1이 배열의 끝이고 포화상태가 아니라면 배열의 첫 번째 인덱스에 데이터를 삽입합니다. → 배열의 포화상태 여부를 판단하기 위하여 배열의 1칸은 비워둡니다. (rear+1)%arra..

선형 큐 (Linear Queue) 큐는 가장 먼저 들어온 데이터가 가장 먼저 내보내지는 (FIFO : First In First Out) 구조를 가집니다. 선형 큐는 데이터를 집어넣는 Enqueue 기능과 데이터를 내보내는 Dequeue 기능을 제공합니다. ■Enqueue 기능 Enqueue는 큐 자료구조에 데이터를 집어 넣는 기능을 수행합니다. 영화 매표소에 사람들이 줄을 선다고 생각해봅니다. 이때 매표소 가장 앞사람을 가르키는 것을 front라 하고 마지막에 서있는 사람을 가르키는 것을 rear이라고 부릅니다. 1번이 Enqueue 되어진 상태입니다. 첫 번째로 줄을 선 사람이므로 front와 rear이 둘다 1번을 가르키고 있습니다. 다음으로 2번이 Enqueue 기능을 수행 한 상태입니다. Fr..

스택 (Stack) 스택(Stack)은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO- Last In First Out)으로 되어있습니다. 자료를 넣는 것을 PUSH라고 하고 넣어둔 자료를 꺼내는 것을 POP이라고 합니다. ■ 스택 입/출력 방식 실제로 스택이 어떤 식으로 자료가 입/출력 되는지 살펴 보겠습니다. 상자안에 책을 쌓는다고 생각을 하면 됩니다. 즉 가장 먼저 넣은 책은 가장 나중에 꺼낼 수 있으며, 가장 최근에 넣은 책을 가장 먼저 뺄수 있습니다. 가장 먼저 5를 PUSH 합니다. 스택 자료 구조에 가장 아래에 위치하게 됩니다. 차례대로 PUSH 4, PUSH 3을 한 결과입니다. POP 2회를 실시하게 되면 출력 결과는 3,4가 됩니다. 즉 3은 가장 나중에 입력 되었지만 ..

Java 삽입정렬 (insertion sort) 정리 삽입 정렬(insertion sort) 알고리즘은 반복적으로 특정 값을 이미 정렬된 목록의 부분 집합에 삽입함으로써 값들의 목록을 정렬한다.한번에 하나씩 정렬되지 않은 원소는 정렬된 부분 집합의 적절한 위치에 삽입된다. 이러한 과정은 전체 목록이 정렬될 때까지 계속된다. ① 단지 한 개의 값만을 포함하는 정렬된 목록으로 시작한다.② 목록의 처음 두 개의 값을 비교하고, 필요하면 이들을 교환함으로써 정렬한다.③ 목록의 세 번째 값을 이미 정렬된 처음 두 개의 값과 비교하여 적절한 위치에 삽입한다.④ 다음에 네 번째 값을 목록의 처음 세 개의 값과 비교하여 적절한 위치에 삽입한다.⑤ 삽입이 이루어질때마다 정렬된 부분 집합에 속한 값들의 개수는 하나씩 증가..

Java 선택정렬 (Selection Sort) 정리 선택정렬(Selection Sort) 알고리즘은 반복적으로 특정 값을 정렬된 최종 위치에 배치시킴으로써 값들의 목록을 정렬한다. 즉, 목록의 각 위치에 대해서 이 알고리즘은 그 위치에 배치되어야 하는 값을 선택하고, 그 값을 그 곳에 배치한다. 선택 정렬에서 일반적인 전략은 다음과 같다.값들의 목록을 오름차순으로 배치하는 문제를 생각해보자. ① 목록 전체를 조사하여 가장 작은 값을찾는다.② 이 값과 목록의 첫 번째 위치에 있는 값을 교환한다. ③ 목록의 나머지 값들(첫 번째 값을 제외한 모든 값)을 조사하여 가장 작은 값을 찾고, 이 값과 목록의 두 번째 위치에 있는 값을 교환한다.④ 목록의 나머지 값들(처음 두 번째 값을 제외한 모든 값)을 조사하여..

Java 해쉬(Hash) 기본 개념과 구조 1. 해쉬(Hash)의 개요 앞에서 데이터를 삽입, 검색, 삭제하는데 사용되는 몇가지 자료구조를 살펴보았다.리스트, 스택, 큐 등의 자료구조를 배열로 구현하거나 연결 리스트로 구현하는 방법을 보면 삽입과 삭제는 연결 리스트가 효율적으로 동작하고 검색은 배열이 더 효율적으로 동작하는걸 확인할 수 있다. [JAVA/알고리즘,자료구조] - [자료구조] Java 배열(array)과 리스트(list) 비교 배열은 내부 인덱스를 이용하여 자료의 검색이 한번에 이루어지기 때문에 빠른 검색 속도를 보이는 반면 데이터의 삽입, 삭제시 많은 데이터가 밀리거나 빈자리를 채우기 위해 이동해야 하기 때문에 많은 시간이 소요된다.반면에 연결 리스트는 삽입, 삭제시 인근 노드들의 참조값만..

Java 원형 큐(Circular Queue), 우선순위 큐(Priority Queue), 데크(Deque-double ended queue) 1. 원형 큐(Circular Queue) 배열을 이용한 큐는 이미 사용한 영역인 front의 앞부분에 대해서 다시 활용을 못하기 때문에 메모리를 낭비한다는 단점이 있었다.그리고 이동 큐를 이용하여 큐가 다 찼을 경우 데이터들을 앞쪽으로 이동시켜 사용하는 방법이 있지만 남아있는 모든 데이터를 다 이동시켜야 한다는 불편한 작업을 수행해야 하기 때문에 그리 효율적으로 동작하지 못한다고 했었다. [JAVA/알고리즘,자료구조] - [자료구조] Java 큐(Queue) 정리 (배열, 연결리스트)원형 큐는 이와같은 단점을 보완하는 구조로 큐의 맨 끝과 맨 처음이 연결된 형태..

Java 큐(Queue) 정리 (배열, 연결리스트) 1. 큐(Queue)의 개요 큐(Queue)는 줄(line) 이라는 의미를 가지고 있다. 큐(Queue)는 데이터의 제거는 대기 줄의 가장 앞에서 수행되며 데이터의 삽입은 대기 줄의 가장 뒤에서 수행이 되는 제한된 리스트 구조를 말하며 가장 먼저 삽입된 데이터가 가장 먼저 제거되는 선입선출(FIFO - First In First Out) 형태의 자료구조이다. 가장 오래전에 입력된 데이터를 front 라고 하며 가장 최근에 입력된 데이터를 rear라고 한다. 데이터의 삽입은 rear에서 이루어지고 삭제는 front에서 이루어지기 때문에 큐를 구현하기 위해서는 front와 rear를 관리하는 배열을 이용하거나 front 노드와 rear 노드를 관리하는 연결..