Hippo's data

오늘은 기수 정렬(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..

오늘은 퀵정렬(Quick Sort) 알고리즘에 대해 알아보겠습니다!퀵정렬은 여러 정렬 알고리즘 중 하나로 이름에서도 알 수 있듯이 빠른(Quick) 속도를 보이는 알고리즘입니다!! # 특징 - 정렬 알고리즘 - 비교 정렬: 다른 원소와 비교를 통해 정렬 수행 - 1959년 토니 호어(Tony Hoare)에 의해 개발- 분할 정복(Divide and Conquer) 방식: 나열된 수를 두개로 분할하여 각각을 해결한 후, 결과를 모아서 원래 문제를 해결# 동작 원리퀵정렬을 한문장으로 정의하면 이렇게 표현할 수 있습니다!"pivot 값을 선정해 해당 값을 기준으로 정렬하는 방식" 동작은 크게 3가지로 확인할 수 있는데욥 1. 리스트(나열된 숫자)에서 기준값( = pivot) 선택2. 기준값( = pivot)과..

안녕하세욥! 오늘은 비교 기반의 정렬 알고리즘(Comparison-based Sorting) 시간 성능의 하한(lower bound)에 대해 알아보겠습니다!!  비교 기반의 정렬 알고리즘(Comparison-based Sorting)에는 여러 종류가 있는데욥! 버블 정렬 (Bubble Sort): 인접한 두 요소를 비교하며 정렬선택 정렬 (Selection Sort): 최솟값 또는 최댓값을 찾아가며 정렬삽입 정렬 (Insertion Sort): 정렬된 부분과 비교하며 새 요소를 삽입합병 정렬 (Merge Sort): 배열을 분할한 후 병합하면서 정렬퀵 정렬 (Quick Sort): 피벗을 기준으로 요소를 나눈 후 재귀적으로 정렬힙 정렬 (Heap Sort): 최대 힙, 최소 힙을 이용하여 정렬정렬 알고리..

오늘은 우선순위 큐 구현에 대해 알아보겠습니다! # 우선순위 큐란?일반적인 큐(queue) 구조는 선입 선출인 FIFO(First In, First Out) 방식으로 작동합니다! https://hipposdata.tistory.com/11 스택(Stack), 큐(Queue), 덱(Deque)오늘의 포스팅은 자료구조인 스택, 큐, 덱입니다!! 특히 차례대로 쌓이는 작업을 어떤 순서대로 처리할지 나타내는 자료구조들 입니다 알고리즘 문제를 풀 때 막무가내로 풀다가 시간초과가 나hipposdata.tistory.com하지만 높은 우선순위(제일 큰 값, 작은 값 등)을 기준으로 자료를 꺼낼때, 매번 모든 자료의 우선순위를 계산해야하는데욥 이를 쉽게 해결할 수 있는 데이터 구조가 우선순위 큐입니다! 우선순위 큐 구..

안녕하세욥! 오늘은 코딩역량시험인 PCCE 시험 후기에 대해 알아보겠숩니다! #  PCCE(Programmers Certified Coding Essential) 시험이란?  프로그래머스 플랫폼에서 주관하는 민간 자격증 코딩필수역량인증시험으로 코딩테스트 환경에서 코딩역량을 확인할 수 있는 시험입니다!! 특히 프로그래머스에서는 PCCE, PCCP 두 가지 난이도의 시험이 존재하는데욥! PCCE는 초중급자 대상! PCCP 상급자 및 전문가를 대상으로 하는 시험입니다!  Python, Java, C++ 총 3가지 언어 중 하나를 선택하여 50분동안 10문항의 문제를 풀게됩니다문제유형은 빈칸채우기, 디버깅과 같은 간단한 일부분 코드 작성과 전체 코드를 작성하는 문제 방식이 있습니당특히 쉬운 유형의 시험이라 ..