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..

오늘은 정렬 알고리즘 중에 기초인 버블정렬(Bubble sort)(=거품정렬) 알고리즘에 대해 알아보겠습니다! # 동작과정 두개의 수씩 차례대로 비교해나가는 식으로 정렬을 수행하는데욥! 두수씩 묶어 비교하는게 거품같지 않나요?!?! 아래는 거품정렬의 간단한 예시인데욥 4,3,5,1,2의 수를 오름차순으로 정렬하는 과정입니다총 4번의 순회를 통해 정렬이 수행되며, 최초 순회시에는 마지막 값이 최댓값이 됩니다   # Python 코드버블정렬은 코드 구현이 매우 쉽습니다! for i in range(len(arr) - 1):    for j in range(len(arr) - i - 1):        if arr[j] > arr[j + 1]: # 비교 후 교환            arr[j], arr[j +..

오늘은 비교정렬 알고리즘인 삽입 정렬 (Insertion Sort) 알고리즘에 대해 알아보겠습니다! # 동작과정 삽입정렬은 이름과 같이 매번 적절한 위치에 해당 값을 삽입하는 알고리즘입니다!간단한 예시로 트럼프 카드 게임을 생각하면 되는데욥! 1. 카드를 뽑고 2. 위치를 찾고 3. 삽입 하는 과정을 생각하면 됩니다!!  아래는 5,3,4,1,2 다섯개의 숫자를 정렬하는 예시인데욥동그라미 숫자는 동그라미 왼쪽의 정렬된 값에서 매번 삽입될 위치를 찾는 식으로 동작합니다! # Python 코드def insertion_sort(A):    n = len(A)    for i in range(1,n):        key = A[i] # 삽입할 요소        j = i-1  # 삽입할 요소 보다 왼쪽에 위치..

이번에는 비교정렬 알고리즘인 선택 정렬 (Selection Sort) 알고리즘에 대해 알아보겠습니다! # 동작과정 선택정렬은 매우매우매우 간단합니다매번 비교마다 최솟값(오름차순 정렬) 혹은 최댓값(내림차순 정렬)을 제일 앞으로 보내주면 되는데요 간단한 만큼 직관적이지만 시간복잡도가 꽝입니다... # Python 코드오름차순으로 정렬하는 코드입니다!인덱스를 처음부터 순회하며 매번 최솟값 인덱스를 찾아 해당 위치의 값과 최솟값 인덱스의 값을 교환해줍니다  def selection_sort(A):    n = len(A)    for i in range(n):        least = i # 현재 위치를 최솟값 위치로 가정         for j in range(i+1, n):            if A..