분류 전체보기

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

[알고리즘] Heap 힙 데이터구조 : 필수 기본정리 - Min Heap, Max Heap, 삽입, 제거, 탐색 구현

목차 힙(Heap) 개념 힙은 우선 우선순위의 개념을 대입한 자료구조입니다. 전포스트에서 다뤘던 Stack,Queue와 같이 자료가 들어오고 나가는 순서를 정할수있습니다. 우선순위개념과 Stack Queue에대하여 자세히 알고싶으시다면 아래 포스트를 참고해주세요. [알고리즘] Stack 스택: 기본정리 - pop, push, peek, count - Kotlin 목차 스택 자료구조 개념 스택은 아이템을 쌓아 올리는 구조입니다. 제거할 때도 가장 위에 있는 아이템부터 제거하게 되고 추가할 때도 위에서부터 추가합니다. 그래서 스택에는 2가지 동작이 underdog11.tistory.com [알고리즘] Queue 큐: 기본정리 - DoublyLinkedList(이중연결 리스트), Ring Buffer(원형큐)..