Hippo's data

오늘은 위상정렬(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)은 이를 기반으로 탐색 값이 정렬된 데이터 내 어디에 위치할지 비례적으로 추정하는 탐색법입니다!이로인해 탐색할 값과 해당 위치는 비례한다는 가정에 기반합니다 동작과정은 이진탐색과 유사한데요 이미 정렬된 데이터에서만 적용할 수 있으며,특히 데이터가 균등하게..

오늘의 포스팅은 탐색(serach) 알고리즘에 속하는 이진탐색(Binary Search)입니다! 지금까지 원하는 기준으로  값을 정리하는 정렬특정 순위의 요소를 찾는 선택 알고리즘들을 알아봤는데요!이번에는 특정 값을 찾는 탐색 알고리즘에 대해 알아보겠습니다! # 탐색알고리즘이란? 주어진 데이터에서 원하는 값을 찾는 것을 말하는데요 탐색알고리즘에는 순차탐색, 이진탐색, 깊이우선탐색(DFS), 너비우선탐색(BFS) 등이 있습니다!  # 동작과정 정렬된 데이터에서만 동작하는데욥!중앙값과 타겟(찾을 값)을 비교하며 절반씩 탐색 범위를 줄여가며 탐색을 진행합니다!총 3가지 경우로 구분할 수 있는데욥 1) 중앙값 == 타겟-> 탐색 종료2) 중앙값 > 타겟 -> 중앙값 왼쪽 데이터셋 탐색3) 중앙값 -> 중앙값 오..

오늘은 그래프 구조를 구현하는 방법에 대해 알아보겠습니다 구현방법을 알아보기 전에, 먼저 그래프 구조 용어에 대해 간단히 알아보겠습니다!# 그래프 구조 용어 그래프는 기본적으로 각 객체와 객체들을 연결하는 선으로 구성되어 있는데욥 객체: 노드(node), 정점(vertex)선: 간선(edge), 링크(link)선의 방향유무, 가중치 유무에 따라 여러 종류로 구분됩니다! 선의 방향 유무방향 그래프 (Directed Graph) / 무방향 그래프 (Undirected Graph) 선의 가중치 유무가중치 그래프 (Weighted Graph) / 비가중치 그래프 (Unweighted Graph) 이때, 가중치(weight)는 해결하고자 하는 문제의 시간, 비용, 거리 등등을 의미합니다!!학부수준에서는 가중치가 ..

안녕하세욥 오늘은 선택 문제(Selection Problem) 의 해결방법 중 하나인 퀵 선택(Quick selct)에 대해 알아겠습니다! # 선택 문제(Selection Problem) 란? 선택 문제(Selection Problem)는 특정 순위의 요소를 찾는 문제인데요 k번째로 작은(또는 큰) 요소를 찾는 문제입니다! 지금까지 포스팅한 정렬(sort)는 일정한 순서(오름차순, 내림차순 등)로 요소를 정리하는 방법이었는데욥선택 문제(Selection Problem)도 정렬(sort) 후, k번째 수를 찾으면 되지만 지금까지 알아본 비교정렬의 특성상 아무리 빨라도 O(nlogn)의 시간복잡도가 필요하기 때문에 해당 선택 문제(Selection Problem)는 O(nlogn)의 시간복잡도가 필요하게 됩..

오늘은 퀵 정렬(Quick sort)와 유사한 병합정렬(Merge Sort) 알고리즘에 대해 알아보겠습니다병합정렬은 존 폰 노이만(John von Neumann) 1945년에 개발한 알고리즘인데요해당 알고리즘은 비교정렬에 속하며 여러 비교정렬 알고리즘 중에 빠른 성능을 보이는 알고리즘입니답 # 동작과정 병합정렬을 한문장으로 이렇게 표현할 수 있습니다! " 일단 반씩 계속 쪼개고 나중에 합침"  퀵정렬과 유사하게 분할 정복(Divide and Conquer)의 방식으로 동작하는데욥 2단계로 세분화하여 살펴볼 수 있습니다 step1) 분할 분할된 크기가 1이 될때까지 절반씩 분할합니다 step2) 병합 및 정렬분할된 배열을 한 묶음이 될때까지 각각 병합하면서 정렬합니다 38, 27, 43, 3, 9, 82,..

이번에는 계수 정렬(Counting Sort) 알고리즘에 대해 알아보겠습니다! 지난 포스팅의 기수 정렬(Radix sort)와 마찬가지로 비교기반 정렬이 아닌 특수한 정렬 인데욥!이로인해 기수 정렬(Radix sort)처럼 이론상 비교정렬의 하한 시간복잡도인 O(nlogn)을 뛰어넘는 정렬알고리즘입니다!https://hipposdata.tistory.com/105 비교정렬 시간 성능의 하한(lower bound): O(nlogn)안녕하세욥! 오늘은 비교 기반의 정렬 알고리즘(Comparison-based Sorting) 시간 성능의 하한(lower bound)에 대해 알아보겠습니다!!  비교 기반의 정렬 알고리즘(Comparison-based Sorting)에는 여러 종류가 있는hipposdata.tis..