극꼼이 이야기 (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개 중 중복을 허용하지..

1. 백트래킹이란? 2. 백트래킹 예시(N-Queen) 1. 백트래킹이란? : 제약된 조건을 가진 문제에서 답을 찾기 위한 방법. - DFS 방식으로 확인(https://geukggom.tistory.com/66). - 모든 경우의 수를 상태 공간 트리를 통해 표현해 탐색. Promising : 해당 루트가 제약된 조건에 맞는지 확인 Pruning : 가지치기. Promising단계에서 조건에 맞지 않으면 바로 다른 루트로 가서 탐색 시간 절약. * 상태 공간 트리(State Space Tree) : 문제 해결 과정의 중간 상태를 Node로 나타낸 트리 2. 백트래킹 예시 백트래킹의 대표적인 문제 예시로는 N-Queen 문제가 있습니다. * N-Queen : 크기가 N * N인 체스판 위에 퀸 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. 힙이란? : ..

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)이란? : 문제를 가장 작은 사례로 나누고, 각각을 푼 다음(하향식 접근법) 합병하여 문제의 답을 얻는 알고리즘입니다. 일반적으로 재귀함수로 주로 구현(재귀함수를 사용하지 않고, 스택이나 큐를 사용하기도 ..