목록CS/알고리즘 (8)

영벨롭 개발 일지

[알고리즘]MST 최소 신장 트리 알고리즘 - Kruskal & Prim

[ Spanning Tree ] Spanning Tree(신장 트리)는 그래프 내의 모든 정점을 포함하는 트리입니다. 그래프의 n 개의 정점을 모두 연결하는 최소 간선의 수는 (n-1) 개이고, 이때 이루어진 그래프를 최소 연결 부분 그래프, 즉 Spanning Tree라고 합니다. 즉, 그래프에서 일부 간선을 선택해서 만든 트리입니다. - Spanning Tree 특징 DFS, BFS를 이용하여 그래프의 신장 트리를 찾을 수 있다. 하나의 그래프에는 많은 신장 트리가 존재할 수 있다. 신장 트리는 모든 정점들이 연결되어 있어야 한다. 신장 트리는 사이클을 포함해서는 안된다. 신장 트리는 n 개의 정점과 (n-1) 개의 간선으로 이루어져 있다. [ MST 최소 신장 트리 ] 최소 신장 트리(MST, mi..
CS/알고리즘 2022. 6. 9. 16:04
[알고리즘]그리디 알고리즘 Greedy Algorithm

[ 그리디 알고리즘 Greedy algorithm ] 그리디 알고리즘(greedy algorithm)은 매 단계에서 '가장 좋아보이는' 해답을 선택하는 알고리즘으로 지역적인 최적의 해결 방법으로부터 전역적인 최적의 해결 방법을 구성하는 방식입니다. 즉, 당장 눈 앞에 보이는 최적의 상황만을 쫓는 가장 단순한 형태의 알고리즘입니다. 때문에 욕심쟁이 또는 탐욕 알고리즘이라고 불리기도 합니다. ★ 그리디 알고리즘을 사용하기 적합한지 판단하는 기준 1. 최적 부분 구조(optimal substructure) 속성 : 주어진 문제 P에 대한 최적의 솔루션이 P의 부분 문제들의 최적의 솔루션으로 구성될 경우, 문제 P가 최적의 부분 구조를 갖는다고 말합니다. 2. 그리디 선택(greedy choice) 속성 : 주..
CS/알고리즘 2022. 5. 10. 13:13
[알고리즘]분할정복을 이용한 정렬 알고리즘 - 병합 정렬 & 쾌속 정렬

[ 분할 정복 ] 분할 정복 (divide-and-conquer) 접근 방법은 주어진 문제의 규모가 클 때 문제를 작은 부분 문제로 나눠서 해결하는 방식입니다. 부분 문제로 나누는 작업을 반복하여 그 해답을 찾고, 다시 그 해답을 합쳐서 처음 문제에 대한 해답을 유도하는 것입니다. 분할 정복 알고리즘의 세 단계 1. 분할(divide) : 주어진 문제를 동일한 방식으로 해결할 수 있는 여러 부분 문제로 나눕니다. 2. 정복(conquer) : 각 부분 문제에 대한 해답을 구합니다. 3. 결합(combine) : 각 부분 문제의 해답을 결합하여 전체 문제에 대한 해답을 구합니다. 일반적인 정렬 알고리즘(bubble sort, insertion sort, selection sort)은 한 쌍식 비교하여 정렬..
CS/알고리즘 2022. 5. 6. 17:45
[알고리즘]이진 탐색 Binary Search 알고리즘

[ 선형 탐색 Linear Search ] 선형 탐색은 배열의 첫 번째 원소부터 차례대로 전체 원소를 방문하면서 해당 원소가 검색하려는 원소와 같은지 확인하는 방법입니다. 이 방법의 장점은 입력 시퀀스의 정렬 여부와 상관없이 항상 잘 동작한다는 점입니다. 하지만 이 방법은 효율적이지 않으며, 주어진 배열이 정렬되어 있어도 그 점을 전혀 활용하지 못합니다. 선형 탐색 알고리즘의 시간 복잡도는 O(N)입니다. int linear_search(int N, vector arr) { for(int i = 0; i < arr.size(); i++){ if(arr[i] == N) return i; } return -1; } [ 이진 탐색 Binary Search ] 선형 탐색과 달리 이진 탐색은 정렬된 배열에서만 동..
CS/알고리즘 2022. 5. 4. 14:27
[알고리즘]브루트 포스 알고리즘, Brute Force Algorithm

브루트 포스(Brute Force) 알고리즘 Brute 짐승, 동물 Force 힘 브루트 포스 알고리즘은 단어 뜻에서 유추할 수 있듯이 무식하게 모든 경우에 대해 모두 직접 탐색하는 완전탐색 알고리즘입니다. 가능한 모든 경우의 수를 모두 탐색하면서 원하는 결과를 도출합니다. 때문에 예외 없이 100% 학률로 정답을 얻을 수 있습니다. 브루트 포스의 종류 브루트 포스 알고리즘은 크게 두 가지 종류로 나뉠 수 있습니다. 1. 선형 구조: 순차 탐색 2. 비선형 구조: DFS, BFS, 백트래킹 https://iridescent-zeal.tistory.com/25?category=1261295 [알고리즘]그래프 탐색하기: BFS & DFS 그래프의 특정 정점에서 시작하여 나머지 모든 정점을 방문하는 문제를 그..
CS/알고리즘 2022. 3. 18. 15:39
[알고리즘]랜덤 미로 생성 알고리즘: 엘러(Eller)의 알고리즘

DFS나 BFS와 같은 여러 탐색 알고리즘들로 미로를 탐색할 수 있었죠? 오늘은 미로를 직접 만들어보겠습니다. 미로를 만드는 알고리즘에는 여러가지가 있는데 그 중 Eller's Algorithm 엘러의 알고리즘을 살펴보겠습니다. 랜덤 미로 생성 알고리즘 Eller's Algorithm 엘러의 알고리즘은 미로를 한 행 씩 차례로 생성해나가는 방법입니다. 가장 빠르게 미로를 생성하는 알고리즘 중 하나이다. 미로의 크기가 N이라면 시간복잡도는 O(N)으로, 미로를 선형시간 안에 만드는 엄청난 성능의 알고리즘입니다. 생성 과정 3x5 크기의 미로를 생성하는 과정은 다음과 같습니다. 1. 미로의 첫 번째 행을 초기화합니다. 이때 첫 번째 행에 속한 5개의 칸을 서로 다른 집합에 속하게 합니다. 2. 현재 행에서 ..
CS/알고리즘 2022. 3. 7. 17:54
이전 Prev 1 2 Next 다음