C#/알고리즘 기초 익히기

DFS? BFS? DFS와 BFS는 그래프를 탐색하는 방법의 일종이다. 그래프란 정점들과 그 정점들을 연결하는 간선들로 이루어진 자료구조이다. DFS는 깊이우선탐색으로, 그래프를 최대한 깊이 탐색한 후 옆으로 이동하여 똑같이 탐색하는 방법이다. BFS는 너비우선탐색으로, 그래프를 옆에서 옆으로 탐색한 후 점점 밑으로 내려가며 탐색하는 방법이다. DFS 예시 https://school.programmers.co.kr/learn/courses/30/lessons/43165?language=csharp 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 위 문제는 ..

그리디 알고리즘이란? 그리디 알고리즘이란 우리말로 탐욕법, 탐욕 알고리즘, 욕심쟁이 알고리즘 등 여러가지 말로 불립니다. 이는 눈 앞에 있는 것이 더 좋아보이면 그것을 추구하는 알고리즘입니다. 대표적인 예시를 들어보겠습니다. : 상품에 대한 가격이 매개변수로 주어집니다. 그리고 서로 다른 금액의 동전이 들어있는 1차원 배열이 주어집니다. 상품을 주어진 배열의 동전으로 계산하려고 할 때 지불해야하는 동전의 개수의 최솟값을 리턴해야 합니다. void Start() { int[] coins = { 10, 500, 50, 100 }; Debug.Log(Greedy_Price(1990, coins)); } public int Greedy_Price(int price, int[] coins) { int answer..

동적 프로그래밍이란? 큰 문제를 작은 단위로 쪼개서 반복 분할하여 푸는 접근 방식입니다. 네 맞습니다. DFS와 같은 개념입니다. 기본적으로 DFS문제는 재귀함수를 사용해서 풀어가는 방식이 일반적입니다. 그럼 동적프로그래밍은 DFS와 같은 것인가?? 결론부터 말씀드리면, 답은 No입니다. 동적 프로그래밍은 작은 하위 문제의 해결 방법을 계산하여 저장하고, 이를 이용하여 큰 문제의 해결 방법을 도출합니다. DFS와 동적프로그래밍의 차이점!! 여기 숫자가 들어있는 정삼각형 구조가 있습니다. 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 리턴하는 문제입니다. 문제를 처음 접하게되면 기본적으로 DFS로 문제를 풀어야겠다는 생각이 들 것입니다. DFS로 접근하게 되면, 7+3+8+2+..

재귀 알고리즘이란? 재귀 알고리즘은 하나의 함수에서 자기 자신을 다시 호출하여 작업을 수행하는 알고리즘이다. 재귀 함수는 반복문(for, while문)으로도 충분히 대체 가능하다. 재귀 함수는 언제 사용할까? - 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우 - 반복문이 많이 중첩되거나 중첩 횟수를 예측하기 어려운 경우 - 변수의 사용을 줄여 메모리를 비교적 간소화하고 프로그램 오류가 발생할 가능성을 줄이고자 하는 경우 - 단, 재귀함수가 모든 경우에서 반복문보다 좋은 것은 아니다. 대표적인 예로는 피보나치 수열, 팩토리얼 계산, 탐색 트리의 순회 등이 있다. 재귀 알고리즘의 사용 1. 피보나치 수열 피보나치 수열이란, F(0) = 0 F(1) = 1 F(2) = F(0) + F(1) F(3)..

1. 순차탐색(Sequential Search) 찾고자 하는 값과 배열의 원소를 순서대로 비교해서 찾으면 해당 인덱스를 반환, 값이 없다면 -1 또는 null을 반환합니다. 시간복잡도 = O(n)번 public int SequentialSearch(int data, List list) { if (list.Count == 0) return -1; for (int i = 0; i < list.Count; i++) { if (list[i] == data) { return i; } } return -1; } 2, 이진탐색(Binary Search) 배열을 크기 순으로 정렬합니다. 정렬된 배열에서 정중앙에 위치한 값을 찾습니다. 찾고자 하는 값을 정중앙의 값과 비교해서 다음에 비교할 구간을 찾습니다. 위 과정을 ..

힙 정렬 내림차순을 기준으로 정렬. 완전 이진 트리의 일종으로 우선 순위 큐를 위하여 만들어진 자료구조. 최댓값, 최솟값을 쉽게 추출할 수 있는 구조. 내림차순 정렬을 위해서는 최대 힙을 구성, 오름차순 정렬을 위해서는 최소 힙을 구성하면 됨. 배열을 최대 힙으로 만듦(내림차순 정렬). 배열의 뒤부터 하나씩 저장. 삭제되는 원소들을 순서대로 정렬(오름차순 정렬). 힙 정렬 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; } } } } 장점 - 비교적 안정한 정렬 방법. - 배열 원소의 수가 적을 경우 유리한 방법. - 대부분의 원소가 이미 정렬되어 있는 경우 매우 효율적임..