개발공부/Algorithm

[알고리즘] 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..

[알고리즘] Priority Queues 우선순위 큐: 필수 기본 정리 - 구현, 활용, comparable, comparator

목차 우리는 이전 포스트 들에서 선입선출 FIFO 후입 선출 LIFO 와 같은 큐의 순서를 알아봤습니다. 새로 배우는 우선순위 큐도 이 큐들 중 한 종류입니다. 우선순위 큐(Priority Queue) 개념 일반적으로 쓰이는 queue에서는 선입선출(FIFO)과 다르게 특정 기준 순서로 아이템이 큐에서 빠지게 됩니다. 예를 들면 리스트에서 가장 큰 값 먼저 dequeue 될 수 있고 작은 값 먼저 dequeue 될 수 있습니다. 이러한 기준을 정하여 queue를 생성할 수 있는 것이 우선순위 큐의 특징입니다. 우선순위 큐는 두 가지 형태를 가지고 있을 수 있습니다. 1. Max-Priority : 가장 우선순위에있는 element는 가장 큰 값 2. Min-Priority : 가장 우선순위에있는 elem..