반응형 자료구조 & 알고리즘/알고리즘10 DP(동적계획법) 복잡한 문제를 작은 문제루 나누고 해결한 결과를 저장해 두었다가 나중에 큰 문제의 결과하여 합하여 풀이하는 알고리즘알고리즘의 이름이 동적 계획법이라고 하지만 원리에 가까운 용어는 '기억하며 풀기'가 더욱 적합하다. dp의 조건(사용조건)최적 부분 구조문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성된 문제중복 부분 문제같은 작은 문제를 여러번 반복적으로 해결해야함dp에서는 이를 메모이제이션을 통해 저장해두고 결과를 합하여 큰 문제를 해결함 dp와 그리디의 비교최적 부분 문제를 풀어나간다는 점은 그리디 알고리즘과 같다.하지만 그리디 알고리즘은 항상 최적이라고 생각하는 것을 선택한 후 풀이를 진행해나가고,dp는 이를 저장시켜두고 전체 해를 구할 때 활용한다는 것이다.그리디 알고리즘에 해당되.. 2025. 6. 15. 크루스칼과 프림 (최소신장 트리) 신장트리(Spanning Tree)신장트리의 조건N개의 정점을 가지는 그래프에서 최소 N-1 개의 간선으로 연결되어 있다.그래프의 모든 정점을 포함한다.신장트리는 최소한의 간선으로 모든 정점을 연결한 트리이다.따라서 사이클이 존재하지 않는 특징이 있다. 최소 신장 트리(Minimum Spanning Tree)최소한의 간선으로 모든 정점을 연결하며, 이때 간선의 가중치의 합이 최소로 이루어진 트리 크루스칼 알고리즘크루스칼 알고리즘은 최소 신장 트리를 만들기 위한 알고리즘으로 그리디 알고리즘의 한 종류이다.매 순간 가중치가 가장 낮은 간선을 선택한다.이러한 그리디 알고리즘 방식은 로컬 최적해를 구하지만 전체 최적해를 보장하지 않는다.하지만, 크루스칼 알고리즘은 사이클이 존재하지 않는 조건을 통해 로컬 최적해.. 2025. 6. 15. 그리디 알고리즘(feat. 다익스트라) 그리디(탐욕) 알고리즘최적의 해를 구하는 데에 사용되는 근시안적인 방법이다.각 단계에서 최적이라고 판단하는 것을 선택해 나가는 방식으로 최종적인 해답에 도달하는 알고리즘이다.문제에 따라 최적해를 보장하기도 하지만, 일반적으로 근사 해를 구하는데 사용된다. 따라서 그리디 알고리즘을 사용하기 위해서는 부분 문제의 최적해가 전체 문제의 최적해를 보장하는 경우에 사용해야한다.실생활에서는 이러한 문제가 상당히 많이 있기 때문에 많은 문제에 적용될 수 있다. 그리디 알고리즘의 조건탐욕 선택 속성매 순간 가장 좋아보이는 선택을 해도 전체 최적해를 구할 수 있는 성질최적 부분 구조작은 부분 문제의 해로 전체 문제의 최적해를 구할 수 있는 성질그리디 알고리즘은 위의 두 성질을 만족해야한다.dp의 경우에도 최적 부분 구조.. 2025. 6. 15. [그래프 탐색] BFS와 DFS, 위상정렬 DFSDFS는 한 노드에서 시작하여 가능한 다음 분기로 넘어가기 전에 해당 분기를 모두 탐색하는 방법이다.이로인해 DFS는 주로 재귀를 통해 구현된다.주로 모든 노드를 탐색해야하는 경우 이 방법을 사용한다.구현은 간단하나, 속도는 너비 우선 탐색에 비해 느리다.DFS 구현시 중요한 부분은 어떤 노드를 방문했었는지 여부를 검사하는 것이다.이를 검사하지 않는다면 무한 루프에 빠질 가능성이 있다.백트래킹해가 될 수 없다고 판단되면, 왔던 길을 되돌아가 다른 길을 찾아가는 방식트리 탐색에서 불필요한 부분을 버리고 탐색을 최적화하기에 '트리 가지치기'라고 도 한다. BFSBFS(Breadth-First Search)는 루트 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방법이다.BFS는 주로 큐를 통해 구현된다... 2025. 6. 15. 이전 1 2 3 다음 반응형
