Hippo's data

오늘의 포스팅은 탐색(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..

오늘은 기수 정렬(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  # 삽입할 요소 보다 왼쪽에 위치..