forman

힙 정렬 내림차순을 기준으로 정렬. 완전 이진 트리의 일종으로 우선 순위 큐를 위하여 만들어진 자료구조. 최댓값, 최솟값을 쉽게 추출할 수 있는 구조. 내림차순 정렬을 위해서는 최대 힙을 구성, 오름차순 정렬을 위해서는 최소 힙을 구성하면 됨. 배열을 최대 힙으로 만듦(내림차순 정렬). 배열의 뒤부터 하나씩 저장. 삭제되는 원소들을 순서대로 정렬(오름차순 정렬). 힙 정렬 C# 코드 public void Heap_Sort(List list) { for (int i = (list .Count- 1)/2; i >= 0; i++) { My_Heap(list, i, list.Count); } for (int i = list.Count - 1; i > 0; i++) { int temp = list[0]; list..

병합 정렬 오름차순을 기준으로 정렬. 비교적 안정 정렬에 속하며, 분할 정복 알고리즘 중 하나. 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 봄. 정렬되지 않은 리스트를 낱개가 될 때까지 절반씩 반복적으로 두 부분 리스트로 나눔. 재귀함수를 통해 병합 정렬을 진행. 병합 정렬 C# 코드 public List DivideArr(List list) { if (list.Count leftIndex && rightList.Count > rightIndex) { if (leftList[leftIndex] leftIndex) { for (int i = leftIndex; i < leftList.Count; i++) { mergedList.Add(leftList[i]); } } else if (rightLis..

셸 정렬 오름차순을 기준으로 정렬. 삽입정렬을 보완한 알고리즘. 배열을 일정한 기준의 간격으로 분류(부분 리스트를 생성). 부분 리스트에서 삽입정렬을 수행. 이 과정을 간격이 1일때까지 반복 수행. 셸 정렬 C# 코드 public void Shell_Sort(int[] array) { //1.매개변수 배열의 크기의 절반만큼 갭을 만든다. int gap; for (int i = array.Length / 2; i > 0; i = i / 2) { gap = i; //갭이 짝수면 갭+1. ex)배열크기=11. 갭=5,3,1 if (gap % 2 == 0) { gap++; } for (int k = 0; k < gap; k++) { Shell_Insert_Sort(array, k, gap); } } } publ..

퀵 정렬 오름차순을 기준으로 정렬. 불안정 정렬에 속함. 매우 빠른 수행 속도를 자랑하는 방법. 기준이 되는 원소(Pivot)을 잡고 해당 원소보다 작은 값을 왼쪽, 큰 값을 오른쪽에 배치해주며 정렬하는 방법. 퀵 정렬 C# 코드 void SortQuick(int[] _arr, int _first, int _last) { if (_first < _last) { int pivot = GetPivot(_arr, _first, _last); SortQuick(_arr, _first, pivot - 1); SortQuick(_arr, pivot + 1, _last); } } int GetPivot(int[] _arr, int _first, int _last) { int pivot = _arr[_first]; i..

삽입 정렬 오름차순을 기준으로 정렬. 배열의 모든 원소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 해당 원소의 위치를 찾아 삽입하는 정렬. 삽입 정렬 C# 코드 public void Insert_Sort(int[] array) { int temp; for (int i = 1; i 0; k--) { if (array[k] < array[k - 1]) { temp = array[k]; array[k] = array[k - 1]; array[k - 1] = temp; } } } } 장점 - 비교적 안정한 정렬 방법. - 배열 원소의 수가 적을 경우 유리한 방법. - 대부분의 원소가 이미 정렬되어 있는 경우 매우 효율적임..

선택 정렬 오름차순을 기준으로 정렬. 배열의 최소값을 찾고, 그 값을 맨 앞에 위치한 원소와 교체. 맨 처음 위치를 뺀 나머지 원소들도 같은 방법으로 교체. 선택 정렬 C# 코드 public void Select_Sort(List _list) { int indexMin; int temp; for (int i = 0; i < _list.Count - 1; i++) { indexMin = i; for (int k = i + 1; k < _list.Count; k++) { if (_list[k] < _list[indexMin]) { indexMin = k; } } temp = _list[i]; _list[i] = _list[indexMin]; _list[indexMin] = temp; } 장점 - 자료 이동 ..

버블 정렬 오름차순을 기준으로 정렬. 서로 인접한 두 원소를 검사하여 정렬. 인접한 2개의 원소를 비교하여 크기 순으로 자리를 재배치. 버블 정렬 C# 코드 public void Bubble_Sort(int[] _list) { int temp; for (int i = _list.Length - 1; i > 0; i--) { for (int k = 0; k _list[k + 1]) { temp = _list[k]; _list[k] = _list[k + 1]; _list[k + 1] = temp; } } } } 장점 - 구현이 간단함. 단점 - 인접한 2개의 원소를 반복적으로 계속 교환해주기 때문에 원소의 수가 많아질수록 시간복잡도가 오래걸림.

참고 사이트: https://geukggom.tistory.com/8 [C# 기초] #19.Graph - Graph의 정의, 종류, 구현 방법 1. Graph란? 정점(vertex(V))과 그 정점을 연결하는 간선(edge(E)을 하나로 모아 놓은 자료구조. 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조입니다. G = (V, E) (ex) 지도, 지하철 노선도, 전기 geukggom.tistory.com 정점(vertex)과 그 정점을 연결하는 간선(edge)을 하나로 모아 놓은 자료구조이다. 그래프도 트리와 같이 라이브러리에서 제공되지 않기 때문에 직접 구조를 구현해야 한다. 1. 무방향 그래프 : 두 정점을 연결하는 간선에 방향이 없는 그래프. 두 정점 간 양 방향으로 이동 가능. 2. 방..

트리란? 트리는 비선형 자료구조이다. 비선형 자료구조란 배열, 리스트와 같이 인덱스(0,1,2,...)가 순서대로 나열된 선형 자료구조의 반대라고 생각하면 된다. 계층모델이다. 노드(node)들의 집합으로 구성되어 있다. 노드란 데이터를 일컫는다. 각 노드는 하나의 부모 노드(루트 노드)와 여러 개의 자식 노드를 가질 수 있다. 트리는 하나의 루트 노드에서 간선을 통해 다양한 노드를 방문, 탐색할 수 있는 구조를 가진다. 이진 트리(Binary Tree) 컴퓨터에서 사용되는 데이터 구조의 하나로, 루트가 있는 트리 구조에서 어떤 노드의 자식의 수가 최대 2개를 넘지 않는 트리를 말한다. 이진 트리의 순회: 이진 트리의 모든 노드를 특정한 순서대로 한 번씩 방문하는 것이다. 1. 전위순회(Pre-order..

▶ C# 자료구조 그래프를 공부하면서 한 번 풀어보았습니다. 1. 문제설명 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오. 2. 제한사항 ● 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다. ● 각 컴퓨터는 0부터 n-1인 정수로..