Algorithm/KBro Study

[자료구조] 그래프(Graph) + 구현하기(Java의 인접행렬과 인접리스트)

그래프(Graph)란? 그래프란 요소들이 서로 복잡하게 연결되어 있는 관계를 표현하는 자료구조이다. 그래프는 정점(vertex)과 정점과 정점을 연결하는 간선(edge)들의 집합으로 구성된다. -> 정점(vertex)는 노드(node)라고도 함 아래는 대표적인 그래프 종류들의 예시이다. 그렇다면 이러한 그래프를 구현하는 방법에 대해 알아보자. 그래프 구현하기 컴퓨터에서 그래프를 구현하는 방법에는 배열(Array)를 사용하는 방법과 연결리스트(Linked List)를 사용하는 방법이 있다. 그래프 구현 - 인접 행렬(Adjacency Materix) 정점 a와 정점 b를 잇는 간선이 있을 경우, 행렬(a,b)에 1을 표기해준다. 만약 가중치가 있는 그래프라면 1 대신 가중치를 넣을 수 있다. 기본적으로 무..

[알고리즘] Brute Force(브루트 포스)

Brute Force(브루트 포스) 브루트 포스는 Brute : 난폭한 / Force : 힘 => 난폭한 힘으로 해석이 된다. 이를 설명하면, 무식하게 모든 경우의 수를 탐색(완전탐색)하면서 조건에 충족되는 결과만을 가져온다. 이 알고리즘의 가장 큰 특징은 모든 영역을 전체 탐색하는 방법이다. 전체 탐색하는 방법으로는 선형 구조를 전체적으로 탐색하는 순차 탐색, 비선형 구조를 전체적으로 탐색하는 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS), 백트래킹(Backtracking) 가 기본적인 도구이다. 어떤 방식으로든 전체 탐색으로 문제를 해결한다면 브루트 포스 알고리즘으로 풀었다고 할 수 있다. 브루트 포스는 완벽히 모든 경우의 수를 탐색하기에, 정확도는 우수하지만, 자원을 너무 많이 사용한다는 점에..

[자료구조] B-tree, B+tree 이론 정리

B-tree "데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종으로, 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다." 정리하자면, B-tree는 Binary search tree와 유사하지만, 한 노드 당 자식 노드가 2개 이상 가능하다 라고 할수있다. 여기서 먼저 트리구조에 대해 알아보자. 트리 구조는 꼭 데이터베이스에 한정하지 않더라도 시스템 세계에서는 데이터를 유지하기 위해 자주 사용하는 구조이다. '탐색' 시, 단시간 내에 실행할 수 있기 때문이다. B-tree의 핵심은 데이터가 정렬된 상태로 유지되어 있다는 것이다. 그림에 표시된 사각형으로 표시된 한 개 한 개의 데이터를 '노드(Node)'라고 한다. 가장 상단의 노드를 '루..

[자료구조] Java - 해시테이블(HashTable) 이론정리

해싱(Hashing)이란? 해싱이란 임의의 길이의 값을 해시함수(Hash Function)를 사용하여 고정된 크기의 값으로 변환하는 작업을 말한다. 해시테이블(HashTable)이란? 해시 테이블은 해시함수를 사용하여 변환한 값을 색인(index)으로 삼아 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조이다. 해시 테이블이 빠른 검색속도를 제공하는 이유는 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문이다. 해시 테이블은 각각의 Key값에 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색하게 된다. 여기서 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다. 이러한 해싱 구조로 데이터를 저..

[자료구조] Java - Heap(힙) 이론정리 + 구현 + Priority Queue(우선순위 큐)

자료구조 힙(Heap) 이란? 완전 이진 트리(마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있는 트리의 형태)의 일종으로 우선순위 큐(Priority Queue)를 위하여 만들어진 자료구조 여러 개의 값들 중에서 최대값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다. 힙은 형제노드 간의 우선순위를 고려하지 않고 부모 노드와 자식 노드의 키 값만 고려한다. 이러한 정렬 상태를 반정렬 상태 혹은 느슨한 정렬 상태 또는 약한 힙이라고 불린다. 힙 트리에서는 중복된 값을 허용한다. Heap의 종류 최대 힙(max heap) 부모 노드의 키값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리 key(부모 노드) >= key(자식 노드) 최소 힙(min heap) 부모 노드의 키 값이 자삭 노드의 키..