분류 전체보기

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