이번챕터에서는 branch-and-bound 알고리즘에 대해 정리할 예정이다. 목차는 다음과 같다. Branch-and-Bound algorithm 0/1 Knapsack Problem using DFS using BFS (Breath-First Search) using BFS (Best-First Search) BFS, DFS 개념은 아래 게시물에 정리되어있다. https://wanna-developer02.tistory.com/54 [알고리즘] CHAP 5. Backtracking Algorithm (백트래킹 알고리즘) - Monte Carlo Algo- 이번 챕터에서는 백트래킹 알고리즘에 대해 정리하려고 한다. 목차는 다음과 같다. Backtracking Algorithm (백트래킹) DFS BFS..

이번 챕터에서는 백트래킹 알고리즘에 대해 정리하려고 한다. 목차는 다음과 같다. Backtracking Algorithm (백트래킹) DFS BFS Monte Carlo Algorithm (몬테카를로 알고리즘) Solve problem 1. N Queens Problem 2. Sum-of-Subsets Problem 3. Graph Coloring Problem 4. Hamiltonian Circuits Problem 1. Backtracking Algorithm (백트래킹 알고리즘) 백트래킹 알고리즘은 어떤 조건을 가진 문제의 해결책을 찾기위해 탐색하는 알고리즘 중 하나이다. 모든 경우의 수를 탐색하긴 하지만, 완전탐색 알고리즘과 달리 어떤 조건을 가지고 있으므로 배제되는 경우들이 많아 효율이 더 높다..

이번 게시글은 탐욕 알고리즘의 마지막 알고리즘으로 다익스트라 알고리즘을 정리할 예정이다. 목차는 다음과 같다. Dijkstra's algorithm (다익스트라 알고리즘) 탐욕알고리즘은 아래 게시글에 설명되어있다. https://wanna-developer02.tistory.com/51 [알고리즘] CHAP 4. The Greedy Approach (탐욕알고리즘) - Prim's alg (프림알고리즘) 이번 챕터에서는 탐욕알고리즘과 이를 이용하는 프림, 크루스칼, 다익스트라 알고리즘을 정리해보려고 한다. 한 게시물에 정리하기에는 내용이 너무 많아서 나눠서 정리할 예정이다. 목차는 다 wanna-developer02.tistory.com 1. Dijkstra 알고리즘 다익스트라 알고리즘은 가중치그래프에서 ..

지난 게시글에 이어 이번에는 Greedy Approach 중에서 Kruskal 알고리즘에 대해 정리하려고 한다. 목차는 다음과 같다 Kruskal 알고리즘 접근방식 코드 시간복잡도 Greedy Approach와 프림 알고리즘은 아래 링크를 참고하도록 하자! https://wanna-developer02.tistory.com/51 [알고리즘] CHAP 4. The Greedy Approach (탐욕알고리즘) - Prim's alg (프림알고리즘) 이번 챕터에서는 탐욕알고리즘과 이를 이용하는 프림, 크루스칼, 다익스트라 알고리즘을 정리해보려고 한다. 한 게시물에 정리하기에는 내용이 너무 많아서 나눠서 정리할 예정이다. 목차는 다 wanna-developer02.tistory.com 1. Kruskal alg..

이번 챕터에서는 탐욕알고리즘과 이를 이용하는 프림, 크루스칼, 다익스트라 알고리즘을 정리해보려고 한다. 한 게시물에 정리하기에는 내용이 너무 많아서 나눠서 정리할 예정이다. 목차는 다음과 같다. Greedy Approach (GA, 탐욕 알고리즘) Minimum Spanning Tree (MST, 최소 신장 트리) GA - 1. Prim's algorithm (프림 알고리즘) 1. Greedy Approach (탐욕 알고리즘) 동적 프로그래밍이 작게 쪼개고 재귀를 통해 작은 것들부터 해결해나가는 기법이었다면, 탐욕 알고리즘은 작게 나누지 않고 그때그때 탐욕스러운 (가장 이익이 되는) 선택을 해나가는 알고리즘이다. 접근 방식은 다음과 같다. 선택 과정 가장 가까운 노드들 중에서 현재 고려사항을 최고로 만족..

이번 챕터에서는 그래프에 대해 알아보고, 그래프를 이용해 최단거리를 구하는 Floyd algorithm (플로이드 알고리즘)도 살펴보려고 한다. 목차는 아래와 같다. 그래프 이론 플로이드 알고리즘 최단경로 구하기 - Floyd vs Brute-force 1. 그래프이론 (Graph Theory) 정말정말 x100!! 중요한 부분이다. 그래프 부분을 해놔야 이후에 나오는 다른 문제들을 해결할 수 있다! 그래프는 여러 개의 점(정점)들이 간선으로 연결된 구조를 나타낸다. 즉 그래프는 정점(V)와 간선(E)로 구성된다. G = (V, E) 그래프 종류 그래프는 가중치 존재의 여부, 방향 존재의 여부에 따라 종류가 다양하다. 가중치그래프 (weighted graph) : 간선에 값(가중치)이 존재한다면 그 그래..

이번 챕터에서는 Dynamic Programming에 대해 작성할 예정이다. 목차는 다음과 같다. 동적 프로그래밍 ? Dynamic Programming vs Divide-and-conquer (feat. 피보나치) 1. Dynamic Programming이란? 진짜 동적으로 프로그래밍을 하는게 아니고, 큰 문제를 작은문제로 나누어 푸는 방법을 말한다. Divide-and-Conquer처럼 문제를 하나 이상의 작은 인스턴스로 분할해 접근하지만, Divide-and-Conquer와 달리 Bottom-up approach를 사용한다. Bottom-up approach는 작은 인스턴트들을 먼저 해결해가는 접근법을 의미한다. Bottom-up approach는 다음과 같은 순으로 진행한다. 재귀적 속성 설정 작..

이번 게시글에서는 divide and conquer의 마지막으로 Master Theorem 에 대해 다뤄볼 예정이다. 목차는 다음과 같다. Master Theorem? divide and conquer에 대한 내용은 아래 링크에서 볼 수 있다. https://wanna-developer02.tistory.com/46 [알고리즘] CHAP 1. Divide and Conquer (분할정복) - mergesort 이번 챕터에서는 divide and conquer에 대해 다뤄볼 예정이다. 목차는 다음과 같다. 분할정복 알고리즘? 예시 - merge sort 그럼 시작! 1. Divide-and-Conquer ? 분할정복은 본격적인 알고리즘 수업의 첫 시간에 wanna-developer02.tistory.com..

지난 챕터에는 divide and conquer에 대해 다루어 보았다. 이번 챕터에서는 그 중에서도 퀵정렬에 대한 내용을 다루어 볼 예정이다. 목차는 다음과 같다. Quicksort? divide and conquer에 대한 내용은 아래 링크에 작성하였다! https://wanna-developer02.tistory.com/46 [알고리즘] CHAP 1. Divide and Conquer (분할정복) - mergesort 이번 챕터에서는 divide and conquer에 대해 다뤄볼 예정이다. 목차는 다음과 같다. 분할정복 알고리즘? 예시 - merge sort 그럼 시작! 1. Divide-and-Conquer ? 분할정복은 본격적인 알고리즘 수업의 첫 시간에 wanna-developer02.tist..

이번 챕터에서는 divide and conquer에 대해 다뤄볼 예정이다. 목차는 다음과 같다. 분할정복 알고리즘? 예시 - merge sort 그럼 시작! 1. Divide-and-Conquer ? 분할정복은 본격적인 알고리즘 수업의 첫 시간에 배운 알고리즘이다. 그만큼 기초적인 부분이라고 할 수 있다. 분할정복이란 하나의 문제를 작은 여러개의 문제로 쪼갠 후 재귀적으로 각 문제를 해결한 후 이를 다시 합쳐 원래 문제를 해결하는 방법이다. 이에 대한 접근은 다음과 같이 할 수 있다. STEP 1) Divide 답을 얻을 수 있을 때까지 한 문제를 2개 이상의 작은 문제로 나눈다. STEP 2) Conquer 길이가 충분히 짧아지면 답을 바로 구할 수 있다. STEP 3) Combine 작은 문제를 해결..