일단 시작해보는 블로그

package com.algorithm2020; import java.util.ArrayList; enum HeapType { MIN, MAX } public class Heap { ArrayList arr; int n; // 남아 있는 노드 개수 HeapType type; // 생성자 public Heap(ArrayList arr, int firstN, HeapType type) { this.arr = arr; this.n = firstN; this.type = type; if (type.equals(HeapType.MIN)) { sortMinHeap(n); } else { sortMaxHeap(n); } } public int top() { return arr.get(1); } public void ..

이진 검색 트리 (Binary Search Tree) 임의의 이진검색트리의 노드 N은 다음 조건을 만족한다. - 노드 N의 왼쪽 서브 트리의 모든 키 값은 N보다 작다. - 노드 N의 오른쪽 서브 트리의 모든 키 값은 N보다 작다. - 같은 키 값을 갖는 노드는 없다. 이때, 이진검색트리를 중위순회(Inorder)하면 다음과 같이 키 값의 오름차순으로 노드를 얻을 수 있다. 1 - 4 - 5 - 6 - 7 - 9 - 11 - 12 - 13 - 14 - 15 - 18 이렇게 중위 순회를 하면 키 값을 오름차순으로 노드를 얻을 수 있다는 점과 구조가 단순하다는 점, 이진 검색과 비슷한 방식으로 검색이 가능하다는 점, 노드의 삽입이 쉽다는 점 등의 특징이 있어 폭넓게 사용된다. 이진검색트리 구현 package..

1. Array 배열의 크기는 처음 한번 정하면 변경할 수 없다. 배열 초기화 시 메모리에 할당되어 ArrayList보다 속도가 빠르다. 논리적 저장 순서와 물리적 저장 순서가 일치한다. 따라서 인덱스로 해당 원소에 접근할 수 있다. 그렇기 때문에 찾고자 하는 원소의 인덱스 값을 알고있으면 O(1)로 원소에 접근할 수 있다. 즉, random access가 가능하다는 장점이 있다. 2. ArrayList 크기가 가변적이다. 저장하는 데이터 수에 따라서 크기가 변경된다. 데이터 추가, 삭제가 가능하지만 그마다 메모리를 재할당하기 때문에 속도가 배열보다 느리다. n개의 자료를 저장할 때 ArrayList는 자료들을 하나의 연속적인 묶음으로 묶어 자료를 저장 무작위 접근 가능 사이즈 고정되어 있음 삽입 시, ..

힙정렬 알고리즘은 입력받은 숫자를 최대 혹은 최소 힙 구조로 만들고 현재 값 중에 가장 큰값 혹은 작은 값을 루트로부터 추출하여 큰값부터 차례대로 뽑아 정렬문제를 해결하는 알고리즘이다. 아래 동영상이 도움이 많이 됐다아ㅏ.!!! LOGIC 1. 배열에 담기 2. max-heapify 3. 1번노드와 마지막 노드 exchange 4. 마지막 노드를 arraylist에 따로 담기, heap크기 = heap크기 -1 package data_structure; import java.util.ArrayList; // max heap! public class HeapSort { static ArrayList sortArr = new ArrayList(); static int[] swap(int[] a, int m,..

힙구조는 우선순위 큐를 위하여 만들어진 자료구조라고 한다. 자료구조 '힙(heap)' 이란? 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다. 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다. 힙은 일종의 반정렬 상태(느슨한 정렬 상태)를 유지한다. 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진트리를 말한다. 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.) 힙의 종류 최대힙 (max heap) - 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리 - key(부모노드) >= key(자식노드..

트리는 노드(자료 저장)와 간선(노드 연결)을 갖는 계층구조이다. 즉, 부모-자식(Parent-Child 관계) 1:n 관계 (여기서 1은 Root Node, n은 Root를 제외한 나머지 자식 노드 즉, n은 레벨이 1이상인 노드이다.) 트리는 응용프로그램, 알고리즘에서 자주 쓰인다. 트리의 종류 자식의 개수에 따라 binary tree : 최대 2개 자식 ternary tree : 최대 3개 부모를 기준으로 binary tree : 부모를 기준으로 노드의 숫자가 기준 없이 자유롭다. binary search tree : 부모를 기준으로 왼쪽은 부모보다 작아야하고 오른쪽은 큰 더 커야한다. complete binary tree : 레벨이 다 맞고 왼쪽부터 채워져 있는 트리 full binary tree..

1. 해쉬는 왜 생겼지? 가장 기본적인 자료구조인 배열의 경우 내부 인덱스를 이용하여 자료의 검색이 한번에 이루어지기 때문에 빠른 검색 속도를 보이는 반면 데이터의 삽입, 삭제 시 많은 데이터가 밀리거나 빈자리를 채우기 위해 이동해야 하므로 많은 시간이 소요된다. 또, 연결리스트는 삽입, 삭제 시 인근 노드들의 참조값만 수정해줌으로써 빠른 처리가 가능했지만 처음노드 마지막 노드 이외의 위치에서 데이터를 삽입, 삭제할 경우나 데이터를 검색할 경우에는 해당 노드를 찾기 위하여 처음부터 순회검색을 해야하기 때문에 데이터의 수가 많아질수록 효율이 떨어질 수 밖에 없는 구조였다. 이를 극복하기 위해 제시된 방법이 해쉬(Hash)이다. 2. 해쉬의 기본 개념 해쉬는 내부적으로 배열(Hash Table)을 사용하여 ..

큐(Queue)는 줄(line)이라는 의미를 가지고 있다. 먼저 들어간 데이터가 가장 먼저 출력되는, 선입선출(FIFO - First In First Out) 형태의 자료구조이다. 가장 오래전에 입력된 데이터(나갈 차례가 가장 빠른, 데이터 삭제) : front 가장 최근에 입력된 데이터(이제 들어온, 들어오는 곳, 데이터 삽입) : rear -> 따라서 큐를 구현하기 위해서는 front와 rear를 관리하는 배열을 이용하거나, front노드와 rear노드를 관리하는 연결 리스트를 이용할 수 있다. 큐의 동작 insert(삽입), remove(추출, 삭제), peek(읽기) 1) 삽입 - insert 새로운 데이터의 삽입은 리스트의 끝 부분을 가리키는 rear에서 발생하며, 데이터가 삽입 될 때 하나 증..