algorithm

이진 탐색 트리 (Binary Search Tree, BST) 이진 탐색 트리는 각 노드가 최대 두 개의 자식을 갖는 이진 트리로서, 다음과 같은 특징을 가지고 있습니다. BST의 특징: 노드 insertion 및 search 시간 복잡도: 평균적으로 삽입과 검색

이진 탐색(Binary Search) 정렬된 배열 또는 리스트에 적합한 고속 탐색 방법

RBT는 균형을 유지하는 이진 탐색 트리입니다. 이는 트리의 높이가 O(log n)이 되도록 보장하며, 이로 인해 탐색, 삽입, 삭제 연산의 평균 시간 복잡도가 O(log n)이 됩니다.RBT는 이진 탐색 트리의 기본 속성을 BST와 동일하게 모두 가지고 있으나, 추가

이진탐색 (Binary search) Divide: 정렬된 배열의 중간값을 확인합니다. Conquer: key값을 Arr[mid]값과 비교합니다. 만약 일치하면 탐색이 완료됩니다. 목표 값이 작다면 왼쪽 하위 배열을, 크다면 오른쪽 하위 배열을 재귀적으로 탐색합니다.

HeapSort 힙(Heap)은 자료 구조 관점에서 완전 이진 트리(Complete Binary Tree) 구조를 가진 특수한 트리 형태입니다. 힙 정렬은 최악의 경우에도 O(n log n)의 시간 복잡도를 가지며, 이는 매우 효율적인 정렬 방법 중 하나입니다. 힙

Heap은 bottom-up의 방법으로 하위배열에서 Heapify() 함수를 실행함으로써 만족시킬 수 있습니다. 자식이 없는 leaf node는 자동적으로 힙의 속성을 만족하므로, leaf node를 제외 한 나머지 노드들에 대해 순차적으로 Heapify를 수행하면

HeapSort Algorithm HeapSort Algorithm은 배열을 정렬하는 알고리즘 중 하나입니다. 졍렬되지 않은 최대힙을 이용하여 정렬합니다. 그 과정은 다음과 같습니다. A[1…n] 의 주어진 배열을 BUILD-HEAP(A, n)함수

HeapSort는 좋은 알고리즘이지만, 실제로는 우선순위 큐가 더 자주 쓰입니다.힙 데이터구조는 우선순위 큐 구현에 매우 효율적입니다.각 요소가 키값또는 키와 연관된 동적 집합 S를 유지하기 위한 데이터구조입니다.Insert(), Maximum(), ExtractMax

Quicksort 분할 정복 알고리즘입니다.'in place'정렬 알고리즘으로, 병합 정렬과 달리 추가적인 메모리 공간을 많이 사용하지 않습니다.평균적을 O(nlogn)의 시간복잡도를 가지며, 최악의 경우, O(n^2)의 시간복잡도를 가집니다.Quicks

입력값의 범위에 따른 Quick sort의 성능차이 알고리즘을 풀때 입력값의 범위를 크게 주어 Arrays.sort()를 사용했을때 run tume error가 발생하게끔 만들어 사용하지 못하게 만든 문제가 있었습니다. 결과부터 말 하자면, 퀵소트를 사용할 때 입력

그리디 알고리즘 > 그리디 알고리즘이란 ? 최적의 해를 구하는데 사용되는 근사적인 방법입니다. 여러 경우 중 하나를 결정해야할 때 마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달합니다.

Graphs Graph G = (V,E) 이때, V는 정점(Vertices)의 집합, E는 간선(Edges)의 집합을 의미하며, E는 VXV의 부분집합입니다. 간선의 크기는 $$O(|V|²)$$로 제한됩니다. 이는 간선이 최대 정점 쌍의 개수에 비례 할 수 있다는것을

Graph search Graph search 에 대해 알아봅시다. $$G = (V,E)$$ 가 주어졌을때 목표는 모든 정점과 간선을 탐색하는 것 입니다. 궁극적으로는 그래프의 정점과 간선을 탐색하면서, 그래프에서 발견된 연결된 정점들로 트리를 구성한드는 뜻 입니다.

BFS 특징 너비 우선 탐색 큐의 FIFO(First In First Out) 성질을 이용하여 정점들을 차례로 탐색합니다. 그래프 탐색의 경우, 어떤 노드를 방문했는지 여부를 반드시 검사해야합니다. 재귀적으로 동작하지 않습니다. BFS는 인접리스트로도 구현할 수 있고

탐색이란 많은 데이터 안에서 원하는 데이터를 찾는 과정을 의미합니다. 프로그래밍에서는 그래프나 트리 등의 자료구조 안에서 탐색을 하는 문제들을 자주 다룹니다. 트리는 그래프 중에서 싸이클이 존재하지 않는 특별한 형태의 연결그래프입니다. 트리에서 각 정점은 한개의 부모를

최단 경로 문제 최단 경로 문제란, 가중그래프에서 간선의 가중치의 합이 최소가 되는 경로를 찾는 문제입니다. 최단 비용을 구하는 알고리즘에는 다익스트라 알고리즘, 벨만 포드 알고리즘, 프로이드 워샬 알고리즘 등이 있습니다. 그리고 최단 경로 계산하는 방식에도 아래와

그래프 탐색 구현 flow 그래프 탐색에는 DFS와 BFS이 있습니다. 그래프를 생성하는 과정과 방문기록 배열의 생성은 DFS나 BFS나 동일합니다. 탐색 방식에 따른 구현부만 달라지는데, 보통 둘 다 재귀를 이용해 호출합니다. 1. 그래프 표현하기 및 데이터 저장 >adjList 생성 (linkedList) $\rarr$ 모든 adjList를 ...