알고리즘

간단하게 정리하면배열 두 번째 원소부터 하나씩 뽑아온다 (key)뽑은 원소보다 큰 애들은 오른쪽으로 한 칸씩 밀어낸다.비어진 자리에 key를 꽂는다.이걸 끝까지 반복하면 정렬 완료j를 2부터 시작하는이유는 배열의 첫번째 인덱스를 i=1로 두기 위함이다이유는 배열의 첫번

merge sort는 병합 정렬로 배열의 개수가 1~n까지 n개라고 했을때 재귀호출을 통해 정렬할 요소가 하나만 있을때까지 절반으로 나누고 그후 merge함수를 통해 정렬하는 방식이다.단계는 분할, 정복, 병합 3가지로 나눌 수 있다.Divide: 배열을 절반씩 나눈다

HEAP DEFINITION 완전 이진 트리(complete binary tree) 형태의 자료구조 힙은 부모와 자식 노드 간의 대소 관계를 만족해야 한다 최대 힙(Max-Heap): 부모 노드의 값 ≥ 자식 노드의 값 (루트에 최댓값이 위치) 최소 힙(Min-He

Easy to codeFast on small inputs (less than ~50 elements)Fast on nearly-sorted inputsWorst case=O(n^2), Best case=O(n), Average case=O(n^2)reverse-sor

min-heap: parent ≤ childmax-heap: parent ≥ childfor all node N, Ni가 모든 힙 properties를 만족해야함1.Max heapify\-O(lgn)\-한쪽 서브트리만 max-heap구조를 만듬2.Build-Max-He

Inputs: G =(V,E),시작 정점 sOutputs:dv: s에서 v까지 최단 경로 길이(nums of edge)πv: s->v 최단 경로의 직전 정점(predecessor) ex) v의 parents 노드(vertex)dv= ∞ : 도달 불가일시 표기법White

스택을 씀(이전 단계 저장,복구)가장 최근 발견된 vertex v 에 대한 edges를 탐색한다.모든 v에 대한 모든 edges가 탐색되었을때, v의 predecessor에 대한 edges들을 탐색한다먼저 가능한안에 깊이가 큰 순으로 탐색한다모든 vertices가 or

Bellman–Ford는 단일 시작점에서 모든 정점까지의 최단 거리를 구하는 알고리즘이다.음수 가중치를 가진 그래프에서도 동작하며, 음수 사이클 감지도 가능하다.간선 리스트(edge list)를 기반으로 하는 대표적인 relaxation 알고리즘이다.Single Sou