극꼼이 이야기 (GG_Tales)

: 문제를 해결하기 위해 확인하는 모든 경우를 전부 탐색하는 방법. 주로 DFS를 이용 - 단점 : 전부 탐색하기에 시간 복잡도가 높음 - (ex) 백 트래킹 * N과 M 문제 : N개 중 중복을 허용하는지/아닌지 + M개를 순서있게 나열하는지/고르는지 1) N개 중 중복을 허용 + M개를 순서있게 나열 https://geukggom.tistory.com/3 [백준] 15651번 : N과 M (3) 문제 : https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해 geukggom.tistory.com 2) N개 중 중복을 허용하지..

저번 크루스칼 알고리즘 포스팅에 이어서, 최소 신장 트리를 찾는 대표 알고리즘인 프림 알고리즘에 대해 알아보겠습니다. * 크루스칼 알고리즘 https://geukggom.tistory.com/177 1. 프림 알고리즘이란? 2. 프림 알고리즘 구현 1. 프림 알고리즘이란? : 크루스칼 알고리즘과 마찬가지로 탐욕 알고리즘을 기반으로 하고 있습니다. 크루스칼 알고리즘과 차이점이 있다면, 크루스칼 알고리즘은 가중치가 가장 작은 간선부터 선택한다면, 프림 알고리즘은 특정 정점에서 시작해서 해당 정점에 연결된 가장 작은 가중치를 선택합니다. 2. 프림 알고리즘 구현 1) Edge 만들기 public class Edge : IComparable { public int weight; //가중치 public strin..

1. 최소 신장 트리 알고리즘 2. Disjoint Set (Union-Find, Union-by-Rank) 3. 크루스칼 알고리즘(Kruskal Algorithm) 1. 최소 신장 트리 알고리즘 : Minimum Spanning Tree(MST). * Spanning Tree : 그래프 내의 모든 정점을 포함하는 트리를 말합니다. 최소 신장 트리란 Spanning Tree 중 사용된 간선들의 가중치의 합이 최소인 트리입니다. 신장 트리에서 최소 신장 트리를 찾는 알고리즘에는 크루스칼 알고리즘, 프림 알고리즘이 있습니다. * 최소 신장 트리의 특징 1) 간선의 가중치의 합이 최소여야 함 2) n개의 정점을 가지는 그래프에 대해 반드시 (n-1)개의 간선만을 사용해야 함 3) 사이클이 포함되어서는 안 됨 ..

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

이전 포스팅에서 분할 정복에는 병합 정렬과 퀵 정렬이 있다 언급했었는데요, 오늘은 병합 정렬에 대해 공부해봅니다. 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. 선택 정렬이란? : 데이터에서 최소값을 찾아 맨 앞으로 가져오고, 옮겨둔 데이터를 제외한 나머지 리스트를 같은 방법으로 교체하는 방식의 정렬 알고리즘. 2. 선택 정렬 구현 GitHub for문을 2번 사용했으므로 시간복잡도는 O(𝑛2)입니다. 최악의 경우에는 𝑛∗(𝑛−1)/2 번 반복해서 코드를 읽습니다.