자료구조 알고리즘7 퀵 정렬 (C#) 📌 퀵 정렬(Quick Sort) 이란?퀵 정렬(Quick Sort)은 평균적으로 매우 빠른 실행 속도를 보이는 정렬 알고리즘이다.기본적인 원리는 '분할 정복(divide and conquer)' 전략을 사용하여, 한 번 분할될 때마다 최소한 한 개의 원소(피벗, pivot)가 최종 위치를 찾아가는 것이다.퀵 정렬의 기본 원리:1. 피벗 선택: 배열에서 하나의 원소를 선택한다. 이 원소를 중심으로 배열을 두 부분으로 나눈다.2. 분할: 피벗보다 작은 원소는 피벗의 왼쪽, 큰 원소는 피벗의 오른쪽으로 이동시킨다.3. 재귀적 정렬: 분할을 통해 생성된 두 개의 작은 배열에 대해 재귀적으로 이 과정을 반복한다.퀵 정렬의 성능은 피벗 선택 방법에 크게 의존하며, 최악의 경우 O(n^2)의 시간 복잡도를 가지지.. 2024. 6. 3. 이진 탐색 (C#) 📌 이진 탐색(Binary Search) 란?이진탐색(Binary Search)은 정렬된 배열이나 리스트에서 특정 값을 찾기 위한 효율적인 알고리즘이다.배열의 중간 요소를 선택해 일치하면 검색 종료.중간 요소가 찾는 값보다 크면 왼쪽 부분, 작으면 오른쪽 부분 배열에서 계속 검색.이렇듯 계속해서 배열의 부분배열을 반복적으로 나누며 검색한다. 계속해서 배열을 반으로 나누며 검색을 한다.정렬이 되어 있어야만 사용 가능하다.Up/Down 게임과 원리가 같다.시간 복잡도는 O(log n)이다.구현 코드static int BinarySearch(int[] arr, int target){ int left = 0; // 왼쪽 시작 int right = arr.Length - 1; // 오른쪽 시작 .. 2024. 5. 27. 선형 탐색 (C#) 📌 선형 탐색(Linear Search) 란?선형 탐색(Linear Search)이란 배열이나 리스트와 같은 데이터 구조에서, 원하는 값을 찾기 위해 처음부터 끝까지 차례대로 검사하는 가장 기본적인 탐색 알고리즘이다. 선형 탐색은 정렬되지 않은 데이터에서도 사용할 수 있으며, 구현이 매우 간단하다. 말 그대로 처음부터 끝까지 하나씩 검사하는 방식이다.정렬이 안 되어도 사용이 가능하다.시간 복잡도는 O(n)이다.구현 코드// 인덱스를 찾아주는 선형탐색static int LinearSearch(int[] arr, int target){ // arr 원소 하나씩 확인 해 target과 일치하면 index를 반환 for (int i = 0; i static void Main(){ int[] a.. 2024. 5. 19. 선택정렬 (C#) 📌선택(Selection Sort) 란?선택 정렬(Selection Sort)은 배열에서 최소값(또는 최대값)을 선택해서 맨 앞(또는 맨 뒤)으로 이동시키는 과정을 반복하여 전체 배열을 정렬하는 방식이다. 버블정렬때와 마찬가지로 오름차 순으로 다음 배열을 정렬해보자 선택 정렬은 다음과 같이 정렬된다. 첫 사이클을 돈 후, 배열에서 가장 작은값이 맨 앞으로 오게된다. 배열의 크기가 n일 때, i = 0, i i + 1 번 원소부터 마지막 원소 크기까지 비교하기 때문에 j = i + 1, j i == 정렬할 원소, j == 비교할 원소비교하는 원소들 중 가장 작은 값을 찾아야하므로 해당 인덱스를 저장할 int index를 따로 만들어 둔다.public void SelectionSort(int[] arr){.. 2024. 5. 19. 버블정렬 (C#) 📌 버블정렬 (Bubble Sort) 란?버블 정렬은 인접한 두 원소를 비교하여 큰 원소를 뒤로 보내는 방식으로 정렬하는 알고리즘이다. 이 과정을 배열의 모든 원소에 대해 반복하며, 가장 큰 원소부터 차례대로 배열의 끝으로 이동하게 된다. 버블 정렬은 구현이 간단하지만, 평균 및 최악의 경우 시간 복잡도가 O(n^2)으로 비효율적이다. 비효율적이라고 써놓긴 했지만 기초 알고리즘이므로 알고리즘 이해를 위해반드시 공부해야 하니 진행해 보도록 하자! 다음과 같은 배열이 있다고 할 때 오름차순으로 정렬을 해보자. 버블 정렬은 다음과 같이 이루어진다. 위처럼 첫 사이클에서 원소가 n개의 배열일 때 0 ~ n-1 번째 원소와 인접한 원소를 비교해 정렬을 한다.이때, 오름차순 기준 한 사이클을 돌면 배열에서 가장 .. 2024. 5. 19. (C#) BFS 📌BFS 너비 우선 탐색시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다 특징Queue를 이용해 방문할 노드를 예약(Enqueue) 후 선입선출(LIFO) 원칙으로 탐색한다.예약한 노드는 반드시 방문 여부를 검사 해야한다.하지 않았을 때 무한 루프에 빠질 수 있다. 구현 코드class Graph{ private int _nodeCount; private List[] _adj; public Graph(int nodeCount) { _nodeCount = nodeCount; _adj = new List[nodeCount];.. 2024. 5. 12. (C#) DFS 📌DFS 깊이 우선 탐색그래프/트리 탐색 기법중 하나이다.한 정점(Vertext)에서 연결되어있는 다른 정점으로 갈 때 한 분기의 가장 깊숙한 곳 까지 탐색하고 다시 돌아와 다른 분기를 탐색하는 기법이다. 특징자기 자신을 호출하는 순환 알고리즘 형태를 가지고 있다.어떤 노드를 탐색했는지 검사를 반드시 해야한다.하지 않았을 때 무한 루프에 빠질 수 있다. 구현 코드class Graph{ private int _nodeCount; private List[] _adj; public Graph(int nodeCount) { _nodeCount = nodeCount; _adj = new List[nodeCount]; for (int i = 0; i ().. 2024. 5. 10. 이전 1 다음
