개발공부

[알고리즘] Heapsort 힙정렬: 필수 기본정리 - 힙정렬 원리, 구현

목차 힙 정렬은 전 포스트에서 다뤘던 버블 정렬, 선택 정렬, 삽입 정렬과 같이 비교 연산을 통해 정렬합니다. 힙을 사용하기 때문에 여러 장점이 있습니다. 바로 최솟값과 최댓값을 찾는데 최적화되어있습니다. 이 특성을 이용하여 정렬하는 것을 HeapSort라고 합니다. 이포스트를 보기 전 힙 데이터 구조를 설명한 이전 포스트를 보고 오는 것을 추천드립니다. [알고리즘] Heap 힙 데이터구조 : 필수 기본정리 - Min Heap, Max Heap, 삽입, 제거, 탐색 구현 목차 힙(Heap) 개념 힙은 우선 우선순위의 개념을 대입한 자료구조입니다. 전포스트에서 다뤘던 Stack,Queue와 같이 자료가 들어오고 나가는 순서를 정할수있습니다. 우선순위개념과 Stack Queue에대하 underdog11.ti..

[알고리즘] Radix Sort 기수 정렬 : 필수 기본정리 - 쉬운 원리 설명, 버켓 구현 - Kotlin

목차 기수 정렬 개념 전 포스트까지는(ex. 버블 정렬, 선택 정렬, 삽입 정렬) 정렬순서를 비교 연산을 통해 정했다면 이번 기수 정렬에서는 비교 연산을 통해 정렬 순서를 정하지 않습니다. 비교 연산을 사용하지 않기 때문에 O(dn) 빠른 속도를 가지고 있습니다. d값의 대해서는 기수 정렬 원리에서 자세히 다루겠습니다. 정렬 순서를 비교연산을 쓰지 않는다면 어떤 기준으로 정렬하는 것일까요? 바로 아래처럼 자릿수를 이용하여 정렬합니다. 기수 정렬은 가장먼저 리스트에서 가장 큰 자릿수 값을 구합니다. 그리고 1의 자리수부터 가장 큰 자릿수 값까지 정렬해 나갑니다. 설명이 부족하므로 아래 예제를 통해 기수 정렬의 원리를 알아보겠습니다. 기수 정렬 원리 Step 1 : 가장 큰 자릿수 값 구하기 [125, 38..

[알고리즘] Merge Sort 병합정렬 : 필수 기본 정리 - 구현, split, merge 코드 설명 - Kotlin

목차 병합 정렬(Merge Sort) 병합 정렬은 O(n log n) 속도를 가진 효율적인 정렬 알고리즘입니다. O(n log n)을 좀 더 자세히 알아보자면 , O(n log n)은 O(n) x O(log n)과 같습니다. 병합 정렬 하나의 큰 문제를 두 개의 작은 문제로 나눈 후 각자 계산 후 합치게 됩니다. 즉 반으로 정확히 나누고 나중에 정렬하는 게 핵심입니다. 개념 1. 카드를 병합 정렬해보겠습니다 아래 그림과 같이 정렬되지 않은 카드를 받았다고 가정해봅시다. 2. 병합 정렬 특징상 먼저 카드를 반으로 나눕니다. 이제 두 개의 정렬되지 않은 카드 뭉치가 됩니다. 3. 그리고 나눌 수 없을 때까지 나눠서 1배 열인 상태로 시작합니다. 4. 이제 나눴던 역순으로 다시 합칩니다. 합치는 순간 정렬이 ..

[알고리즘] O(n2) 3가지 기본 정렬 알고리즘 : 버블 정렬, 선택정렬, 삽입정렬 Kotlin 구현

목차 개요 정렬할 때 O(n²) 속도를 가진 알고리즘은 성능 면에서 효율적이지는 않지만, 정렬 알고리즘에서 우리가 이해하기 쉬운 방법입니다. O(n²) 알고리즘은 공간면에서는 효율적입니다 왜냐하면, O(1)만 필요하기 때문입니다. 이번 포스트에서는 버블 정렬(Bubble sort), 선택 정렬(Selection sort), 삽입 정렬(Insertion sort)을 다뤄보겠습니다. 비교 기반 알고리즘 버블 정렬(Bubble sort), 선택 정렬(Selection sort), 삽입 정렬(Insertion sort) 이 세 가지 알고리즘 모두 비교 기반 정렬 알고리즘입니다. 즉, 이들은 비교 메서드에 의존합니다. 그리고 이 비교 메서드가 얼마나 불리느냐가 이 알고리즘들의 성능을 좌우합니다. 버블 정렬(Bub..