개발공부/Algorithm

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