전체 글

[알고리즘] BFS 너비 우선 탐색 : 필수 기본 정리 : 과정, Kotlin 구현예제

목차 저번 포스트에서 그래프를 통해 object 사이에 관계를 살펴보았습니다. 그래프는 정점으로 object를 나타내고, 변으로 object의 관계를 나타냈습니다. 그래프에 대하여 자세히 알고 싶으시다면 이전 포스트를 참고해주세요. [알고리즘] Graph 그래프 : 필수 기본 정리 - 가중치, 방향, 무방향 그래프, 인접리스트, 인접행렬 목차 그래프(Graph) 그래프는 objects의 관계를 나타내는 데이터 구조입니다. 이렇게 관계를 나타내는 이유는 무엇일까요? 두 object의 연결은 둘이 서로 알고 있다는 뜻입니다. 서로 안다는 양방향성 underdog11.tistory.com 이런 그래프탐색을 위한 알고리즘이 존재하는데 그중 하나가 BFS 너비우선탐색 알고리즘입니다. BFS는 정점(vertex)의..

[알고리즘] Graph 그래프 : 필수 기본 정리 - 가중치, 방향, 무방향 그래프, 인접리스트, 인접행렬 구현

목차 그래프(Graph) 그래프는 objects의 관계를 나타내는 데이터 구조입니다. 이렇게 관계를 나타내는 이유는 무엇일까요? 두 object의 연결은 둘이 서로 알고 있다는 뜻입니다. 서로 안다는 양방향성 관계를 뜻합니다. 그래프는 정점 (Vertices)와 변(Edges)들로 이루어져 있습니다. 아래와 같이 꼭짓점은 노드이고 선은 각 노드들을 이어줍니다. 그래프 종류 그래프 종류에는 3가지가있습니다. 아래 각 그래프의 특징들을 살펴보겠습니다. 다이어그램 설명 가중치 그래프 가중치그래프는 옆에 이미지와 같이, 정점 사이의 코스트나 거리등을 나타내어 활용됩니다. 예를 들어 도쿄에서 워싱턴 디씨를 거쳐 샌프란시스코를 간다면 총 300+ 337불이 들게됩니다. 방향 그래프 방향그래프는 말그대로 방향성이있는..

[알고리즘] Quick Sort 퀵정렬 : 필수 기본 정리 - 로무토 분할, 호어, 효율적인 피봇값 정하기

목차 퀵 정렬은 비교 연산을 이용한 정렬 알고리즘입니다. 이전 포스트에서도 많은 정렬 알고리즘을 다뤘는데요, 아래 정렬 알고리즘들을(버블 정렬, 삽입 정렬, 선택 정렬, 병합 정렬, 힙 정렬) 모르신다면 보고 오시는 것을 추천드립니다. [알고리즘] O(n2) 3가지 기본 정렬 알고리즘 : 버블 정렬, 선택정렬, 삽입정렬 Kotlin 구현 목차 개요 정렬할 때 O(n²) 속도를 가진 알고리즘은 성능 면에서 효율적이지는 않지만, 정렬 알고리즘에서 우리가 이해하기 쉬운 방법입니다. O(n²) 알고리즘은 공간면에서는 효율적입니다 왜냐 underdog11.tistory.com [알고리즘] Merge Sort 병합정렬 : 필수 기본 정리 - 구현, split, merge 코드 설명 - Kotlin 목차 병합 정렬(..

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

[알고리즘] 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(원형큐)..