Hippo's data

오늘은 비교정렬 중 하나인 힙 정렬(Heap Sort)에 대해 알아보겠습니다힙 정렬은 힙 구조를 이용하여 정렬을 수행하는데욥 힙구조란 무엇일까요? # 힙(Heap) 구조란?완전 이진 트리(Complete Binary Tree)의 일종인데욥(왼->오, 위->아래 순번끊김 없는 트리)  우선순위 큐(Priority Queue)에도 사용되는 구조입니다!https://hipposdata.tistory.com/104 우선순위 큐 구현 (PriorityQueue, Heap)오늘은 우선순위 큐 구현에 대해 알아보겠습니다! # 우선순위 큐란?일반적인 큐(queue) 구조는 선입 선출인 FIFO(First In, First Out) 방식으로 작동합니다! https://hipposdata.tistory.com/11 스택(..

오늘은 정렬 알고리즘인 쉘 정렬(Shell Sort)에 대해 알아보겠습니다!쉘 정렬(Shell Sort)의 쉘(Shell)은 1959년 해당 알고리즘을 고안한 도널드 셸(Donald L. Shell)의 이름을 따서 지어졌는데욥삽입 정렬(Insertion Sort)의 개선된 버전으로 값을 비교하며 정렬하는 비교정렬에 속합니다!https://hipposdata.tistory.com/108 삽입 정렬 (Insertion Sort) 알고리즘오늘은 비교정렬 알고리즘인 삽입 정렬 (Insertion Sort) 알고리즘에 대해 알아보겠습니다! # 동작과정 삽입정렬은 이름과 같이 매번 적절한 위치에 해당 값을 삽입하는 알고리즘입니다!간단한hipposdata.tistory.com # 동작과정 데이터를 일정 간격(gap)..

오늘은 선택문제(Selction Problem)에 속하는 Median of medians 알고리즘에 대해 알아보겠습니다! 지난번에 선택문제에 대해 다뤘었는데욥 다시 복습하자면선택문제란, k번째로 작은(또는 큰) 요소를 찾는 문제입니다!  해당 문제를 해결하는 방법에는 여러 전략이 존재하는데욥 1) 매번 큰 값을 찾아 k번째 큰 값을 찾기가장 쉽게 생각할 수 있는 전략이다매번 큰 값을 찾아 총 k번 큰 값을 찾으면, k번째로 큰 값을 찾을 수 있다 총 비교횟수를 생각해보면1st max : n-12nd max: (n-1) + (n-2) = 2n-33rd max: (n-1) + (n-2) + (n-3) k번째 max: (n-1) + (n-2) + (n-3) + ... + (n−k)  등차수열의 합: 항의개수k..

오늘은 정렬 알고리즘의 안정성(Stability)에 대해 알아보겠습니다! 지금까지 매우 다양한 정렬 알고리즘들을 소개해 보았는데요이러한 정렬 알고리즘에서 정렬이 얼마나 빨리 가능한지 속도(시간복잡도) 측면이 제일 중요하지만또 다른 기준인 안정성(Stability) 또한 중요합니다 # 안정성(Stability) 이란?정렬 전후 값이 동일한 데이터들의 순서가 동일한지 여부를 의미하는데요안정적인(Stability) 정렬 알고리즘은 동일한 값의 데이터가 정렬 전후에 원래의 순서를 유지하는 반면.안정적이지 않은(Unstability) 정렬 알고리즘은 동일한 값의 데이터가 정렬 전후에 순서가 바뀌게 됩니다! 예) 3_a, 2, 3_b, 5, 3_c 1, 7 7개의 값을 오름차순으로 정렬하려고 합니다 (3인 중복된 ..

오늘의 포스팅은 프림 알고리즘(Prim's)의 변형인 다익스트라 (Dijkstra) 알고리즘입니다!다익스트라 알고리즘은 데이크스트라라고도 불리는데욥TMI)백준 알고리즘분류에는 데이크스트라라고 분류되어 있네욤,,,여담으로 다익스트라 알고리즘은 1956년에 네덜란드 태생 컴퓨터 과학자인 다익스트라에 의해 개발되었다고 하는데욥까페에서 피앙세를 기다리던 도중 20분정도만에 아이디어를 생각해낸 알고리즘이라고 합니다,,,, 다익스트라 알고리즘은 특정 노드에서 모든 노드로 가는 최단 경로(Shortest path)를 구하는 알고리즘인데요양의 가중치를 가지는 그래프에서만 사용 가능합니다! (음의 가중치는 벨만-포드 알고리즘 사용) 다익스트라 알고리즘은 greedy알고리즘에 속하기도 하는데욥매번 현재 노드에서 가장 가까..

오늘은 위상정렬(Topological Sort)에 대해 알아보겠습니다! 위상정렬은 방향그래프, 사이클이 없는 그래프(DAG, Directed Acyclic Graph) 에서 노드의 순서를 정하는 알고리즘입니다!(사이클이 있다면 시작점을 정할 수 없으므로 순서를 파악할 수 없음) 일반화 한다면, 순서가 정해져 있는 작업에서 조건에 맞게 순서를 결정해주는 것을 말합니다!대표적인 예시로 선수과목 순서에 따라 수강과목을 정하기, 작업 스케줄링에 따라 작업순서 선정 등이 있습니다특히 결과로 여러 답이 존재합니다! (유니크한 결과 X) # 동작과정 위상정렬은 2가지 방식으로 구현가능한데욥1) 스택(stack)이용 - DFS2) 큐(queue)이용 - BFS일반적으로 큐를 이용한 방식이 주로 사용되므로 해당 방식을 ..

오늘은 그래프 알고리즘 중 하나인 유니온 파인드(Union-Find)에 대해 알아보겠습니다! 유니온 파인드는 합집합 찾기, 서로소 집합(Disjoint Set) 알고리즘 등 다양한 이름으로 불리는데욥그래프에서 같은 그래프에 속하는지 확인(각 노드의 연결 여부 확인)하거나, 같은 집합인지 확인하는 즉. 같은 소속인지 확인하는 알고리즘입니다! 특히 최소 신장 트리(Minimum Spanning Tree, MST)를 찾는 크루스칼 알고리즘(Kruskal's Algorithm)에 기반이 되는 알고리즘 입니다간선을 연결할 때 사이클이 생성되지 않도록 유니온 파인드 알고리즘을 활용하는데욥(두 간선 연결할때, 부모노드동일할시 = 같은집할일때 -> 사이클O / 부모노드 동일하지 않을시 = 다른집합일때 -> 사이클 X)..

오늘의 포스팅은 탐색 시리즈 중 보간 탐색(Interpolation Search)입니다!보간탐색은 지난 이진탐색(Binary Search)의 개선된 버전이라고 할 수 있습니다! # 동작과정 보간 탐색(Interpolation Search)은 보간(Interpolation)이라는 단어에서 유추할 수 있는데요 보간(Interpolation)은 이미 알고 있는 값들 사이에서 미지의 값을 추정하는 것을 의미하는데,보간 탐색(Interpolation Search)은 이를 기반으로 탐색 값이 정렬된 데이터 내 어디에 위치할지 비례적으로 추정하는 탐색법입니다!이로인해 탐색할 값과 해당 위치는 비례한다는 가정에 기반합니다 동작과정은 이진탐색과 유사한데요 이미 정렬된 데이터에서만 적용할 수 있으며,특히 데이터가 균등하게..