극꼼이 이야기 (GG_Tales)

1. 최단 경로 문제란? : 가장 짧은 경로 내의 두 노드를 찾는 문제입니다. 변마다 가중치가 있는데, 가중치의 합이 최소가 되도록 경로를 찾아야 합니다. 2. 우선순위 큐 : 일반적인 큐(Queue)가 FIFO(First In First Out)구조였던 것에 비해, 우선순위 큐는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조입니다. 너비우선탐색(BFS)과 유사하며, 현재 가장 짧은 거리를 가진 노드 정보를 먼저 꺼내오는 방식으로, 최단 경로 문제를 푸는데 최적화 되어 있는 방법입니다. 저는 MinHeap 방식을 사용해 우선순위 큐를 구현할 것입니다. * Heap : https://geukggom.tistory.com/163 [C# 기초] #21. 힙(Heap) 1. 힙이란? : ..

1. IComparer, IComparable 인터페이스 : 개체의 값을 비교하기 위한 인터페이스. .NET 프레임워크에서 제공하는 객체의 선후 관계를 정의하는 인터페이스입니다. 2. IComparer, IComparable의 차이점 : 둘 다 개체의 값을 비교하는 인터페이스인데요, 사용 방법은 거의 비슷한데 차이점을 둔다면, IComparable은 현재의 개체를 같은 타입의 다른 개체와 비교(같은 타입끼리 비교)한다면 IComparer는 두 개의 서로 다른 개체를 비교(제 3자와 비교하는 것)한다는 것입니다. 3. IComparable IComparable 인터페이스에는 CompareTo()라는 메서드만 정의되어 있습니다. CompareTo() 메서드를 정의해두면, Array.Sort()메서드를 사용했..

1. 탐욕 알고리즘이란? : 매순간 최적이라고 생각되는 값을 선택하는 알고리즘입니다. 이렇게만 설명을 들으면 이해하기 어려울 수 있는데요, 아래 예시를 통해 어떤건지 더 자세히 알아봅시다. 2. 탐욕 알고리즘 예시 동전을 거슬러주는 함수를 만들어봅시다. coinList에는 큰 액수의 동전부터 들어가 있습니다. 탐욕 알고리즘은 아래와 같이 큰 액수의 동전부터 몇개 거슬러줄지 개수를 정합니다. public void coinFunc(int pric, List coinList) { int totalCount = 0; int nowPrice = pric; for (int i = 0; i < coinList.Count; i++) { int nowCount = nowPrice / coinList[i]; nowPric..

1. 순차 탐색 (Sequential Search) 데이터들을 하나씩 비교해서 원하는 데이터를 찾는 방법입니다. public int searchIndex(int data, List list) { if (list.Count == 0) return -1; for (int i = 0; i < list.Count; i++) { if (list[i] == data) //원하는 데이터를 찾음 return i; //단, 같은 데이터가 여러개 있어도 제일 앞에 있는 데이터의 index 리턴 } return -1; //원하는 데이터가 없을 경우 } 2. 이진 탐색(Binary Search) 데이터를 둘로 나누고, 둘 중 원하는 데이터가 있을만한 곳을 찾는 방법입니다. 순차 탐색과는 다르게 데이터들이 이미 정렬을 마친 상..

1. 퀵정렬이란? 데이터들 중 한 숫자를 기준점(pivot)으로 정하고, 기준점보다 작은 데이터는 왼쪽으로, 큰 데이터는 오른쪽으로 분류하여 정렬합니다. 재귀용법을 이용해 작은 단위까지 쪼개어 정렬한 후 합치는 방식입니다. 2. 퀵정렬의 구현 병합정렬을 배우고 나니 퀵정렬은 조금 더 쉬웠습니다. public List quickSort(List list) { if (list.Count = list[i]) left_List.Add(list[i]); else right_List.Add(list[i]); } left_List = quickSort(left_List); right_List = quickSort(right_List); left_List.Add(pivot); left_List.AddRange(righ..

이전 포스팅에서 분할 정복에는 병합 정렬과 퀵 정렬이 있다 언급했었는데요, 오늘은 병합 정렬에 대해 공부해봅니다. https://geukggom.tistory.com/169 1. 병합 정렬이란? : 분할 정복 방식의 알고리즘이며, 재귀용법을 이용한 정렬 알고리즘입니다. 병합정렬의 방식을 단계별로 설명하면 다음과 같습니다. 1) 배열을 반으로 쪼갭니다. 2) 1) 과정을 재귀용법을 이용해 반복합니다. 3) 쪼개진 두 배열들을 합병 정렬을 이용해 합치며 정렬합니다. 움짤로 보시면 더 이해가 쉽습니다. 2. 병합 정렬 구현 위에서 설명한 단계별로 구현해보겠습니다. 1) 배열을 반으로 쪼갭니다. int cutNum = list.Count / 2; List leftList = list.ToList(); List ..

1. 동적 계획법(Dynamic Programming(DP))이란? : 처음 계산된 값을 저장(Memoization)하고, 이 값으로 상위 문제를 풀어 나가는 방식(상향식 접근법)입니다. * Memoization(메모이제이션) : 프로그램 실행 시 이전에 계산한 값을 저장하고, 이를 이용해 중복 계산을 하지 않고 전체 실행 속도를 빠르게 하는 기술. * 상향식 접근법 : 가장 최하위의 해답을 구한 후, 이를 저장해 해당 결과값으로 상위 문제를 푸는 방식 2. 분할 정복(Divide and Conquer)이란? : 문제를 가장 작은 사례로 나누고, 각각을 푼 다음(하향식 접근법) 합병하여 문제의 답을 얻는 알고리즘입니다. 일반적으로 재귀함수로 주로 구현(재귀함수를 사용하지 않고, 스택이나 큐를 사용하기도 ..

1. Nnullable 타입이란? : Null을 가질 수 없는 타입(int, bool 처럼 값을 가지는 타입)이 Null을 가질 수 있게 해주는 타입입니다. * 참조 타입은 Null 체크가 가능함. 2. Nullable 타입의 용도 저는 이 타입을 Heap을 공부할 때 처음 사용해 보았습니다. https://geukggom.tistory.com/163 Heap에서는 리스트의 0번 인덱스 데이터 값을 사용하지 않기 때문에 null을 집어넣었는데요, 이때 List 타입을 사용했습니다. Nullable 타입은 타입명 다음에 ?를 붙여 사용합니다. (ex) int?, bool? HasValue메서드를 아래와 같이 사용하면 값이 있는지 없는지 확인할 수 있습니다. int?[] arr = new int?[3]; a..

1. 삽입 정렬이란? : 두번째 인덱스부터 시작해서, 앞으로 이동하면서 다른 인덱스들과 값을 비교해서 자신의 위치에 맞는 곳에 삽입하는 방식의 정렬 알고리즘. 2. 삽입 정렬 구현 GitHub for문을 2번 사용했으므로 시간복잡도는 O(𝑛2)입니다. 최악의 경우에는 𝑛∗(𝑛−1)/2 번 반복해서 코드를 읽습니다. * 버블정렬, 선택정렬, 삽입 정렬 모두 동일한 시간복잡도를 가집니다.

1. 선택 정렬이란? : 데이터에서 최소값을 찾아 맨 앞으로 가져오고, 옮겨둔 데이터를 제외한 나머지 리스트를 같은 방법으로 교체하는 방식의 정렬 알고리즘. 2. 선택 정렬 구현 GitHub for문을 2번 사용했으므로 시간복잡도는 O(𝑛2)입니다. 최악의 경우에는 𝑛∗(𝑛−1)/2 번 반복해서 코드를 읽습니다.