4OurFuture 님의 블로그

1. 개요**다이나믹 프로그래밍 (DP)**과 그리디 알고리즘은 모두 최적화 문제를 해결하는 알고리즘 설계 기법입니다. 두 기법 모두 문제를 더 작은 하위 문제로 나누어 해결한다는 공통점이 있습니다. 그러나 문제를 해결하는 접근 방식과 적용 가능한 문제 유형이 서로 다릅니다. 2. 공통점최적화 문제 해결두 알고리즘 모두 최적의 해결책을 찾는 최적화 문제에 사용됩니다.문제의 분할두 기법 모두 문제를 더 작은 하위 문제로 나누어 해결합니다.부분 문제두 기법 모두 하위 문제를 해결한 결과를 기반으로 전체 문제의 해결책을 도출합니다.재귀적 사고두 알고리즘 모두 재귀적으로 문제를 해결할 수 있습니다. 3. 차이점3.1. 문제 해결 접근 방식 다이나믹 프로그래밍 (DP)그리디 알고리즘하위 문제를 모두 해결하고, 그..

**우선순위 큐(Priority Queue)**는 일반적인 큐(Queue)와 비슷한 자료 구조이지만, 데이터의 우선순위에 따라 요소를 삽입하고 제거하는 특징을 가집니다. 즉, 큐에서 요소가 제거될 때 가장 높은 우선순위를 가진 요소가 먼저 나가는 구조입니다.1. 우선순위 큐의 특징우선순위 기반 요소 제거:일반적인 큐는 FIFO(First-In-First-Out) 방식으로, 먼저 들어온 데이터가 먼저 나가는 반면, 우선순위 큐는 각 요소에 우선순위를 부여하고, 가장 높은 우선순위를 가진 요소가 먼저 제거됩니다.삽입과 삭제 연산의 효율성:우선순위 큐는 효율적으로 삽입과 삭제 연산을 수행할 수 있도록 구현됩니다. 일반적으로 힙(Heap) 자료 구조를 사용하여 구현하는 경우가 많습니다.두 가지의 우선순위 큐 유..

최소 신장 트리(Minimum Spanning Tree, MST)는 가중치가 있는 연결된 그래프에서 모든 정점을 포함하며, 간선의 가중치 합이 최소가 되는 트리를 찾는 문제입니다. 네트워크 설계, 도로 건설, 통신 네트워크 등에서 자주 사용되며, 이 문제를 해결하기 위한 대표적인 알고리즘에는 Generic MST, Prim, 그리고 Kruskal 알고리즘이 있습니다. 이번 글에서는 MST의 개념과 각 알고리즘의 차이점 및 활용 방안에 대해 살펴보겠습니다.MST란 무엇인가?먼저, **MST(Minimum Spanning Tree)**의 개념을 살펴봅시다.**최소 신장 트리(MST)**는 그래프의 모든 정점을 연결하면서, 간선 가중치의 총합이 최소가 되는 트리를 의미합니다.**신장 트리(Spanning Tr..

BFS(너비 우선 탐색)와 DFS(깊이 우선 탐색)의 특징을 비교특징BFS(너비 우선 탐색)DFS(깊이 우선 탐색) 탐색 방식너비 우선 탐색깊이 우선 탐색구조큐(Queue) 사용스택(Stack) 또는 재귀 사용최단 경로가중치가 없는 경우 최단 경로 보장최단 경로 보장하지 않음메모리 사용O(V) (정점 수)O(V) (정점 수)시간 복잡도O(V + E) (정점과 간선 수)O(V + E) (정점과 간선 수)적용 분야최단 경로, 네트워크 탐색, 퍼즐 문제미로 찾기, 위상 정렬, 연결 요소 찾기방문 순서인접한 정점부터 탐색한 방향으로 깊게 탐색중복 경로동일한 정점 여러 번 방문 가능동일한 정점 여러 번 방문 가능전략레벨 단위로 탐색경로 단위로 탐색실제 적용 예시소셜 네트워크 분석, 웹 크롤러, GPS 내비게이션게..