Hippo's data

오늘은 그래프 구조를 구현하는 방법에 대해 알아보겠습니다 구현방법을 알아보기 전에, 먼저 그래프 구조 용어에 대해 간단히 알아보겠습니다!# 그래프 구조 용어 그래프는 기본적으로 각 객체와 객체들을 연결하는 선으로 구성되어 있는데욥 객체: 노드(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..

오늘은 기수 정렬(Radix sort)에 대해 알아보겠습니다! 기수정렬은 지금까지 포스팅한 비교정렬 알고리즘(삽입, 선택, 퀵 등등)과는 다른 알고리즘인데욥값을 일일이 비교하지 않고 정렬하는 알고리즘 입니다!특히 이로인해 이론상 비교정렬의 하한 시간복잡도인 O(nlogn)을 뛰어넘는 정렬알고리즘입니다!https://hipposdata.tistory.com/105 비교정렬 시간 성능의 하한(lower bound): O(nlogn)안녕하세욥! 오늘은 비교 기반의 정렬 알고리즘(Comparison-based Sorting) 시간 성능의 하한(lower bound)에 대해 알아보겠습니다!!  비교 기반의 정렬 알고리즘(Comparison-based Sorting)에는 여러 종류가 있는hipposdata.tist..