트리 동적 계획법: 다지 트리 배낭 문제와 최대 경로 합
다지 트리 배낭 문제 (Multi-ary Tree Knapsack Problem)
이전에는 이진 트리를 기반으로 한 문제를 다루었지만, 이제는 난이도를 높여 다지 트리(multi-ary tree) 구조에 적용되는 동적 계획법(DP)을 살펴보겠습니다. 다지 트리는 각 노드가 여러 자식 노드를 가질 수 있는 형태입니다. 이 경우, 단순한 이진 트리 DP 방식으로는 해결하기 어렵습니다. 대신, 배낭 문제(kn ...
7월 28일 08:58에 게시됨
무가중 그래프 탐색 알고리즘: 깊이 우선(DFS)과 너비 우선(BFS)
그래프는 많은 애플리케이션에서 중요한 데이터 구조이며, 이를 효율적으로 탐색하는 것은 매우 중요합니다. 가중치가 없는 그래프의 경우, 방향성이 있거나 없음에 관계없이 두 가지 주요 알고리즘이 돋보입니다: 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS). 이 두 방법 모두 두 노드 사이에 경로가 존재하는지 여부를 판단하고 해당 경로를 재구성할 수 있습니다. 특히, ...
7월 28일 06:55에 게시됨