알고리즘

Knapsack Problem에는 두 가지 종류가 있다.Fractional Knapsack Problem 0/1 Knapsack ProblemFractional Knapsack Problem 의 경우에는 그리디로 해결할 수 있다. 하지만 0/1 Knapsack Prob

문자열 매칭 문자열이 주어졌을 때 특정한 패턴과 매칭되는 위치를 찾는 것을 말한다. Brute Force 알고리즘 먼저 가장 단순한 방법을 떠올리자면, 모든 문자열의 위치에 대해 패턴을 하나하나 다 비교해보는 방법이다. 문자열의 길이를 N 패턴의 길이를 M 이라고

DAG Directed Acyclic Graph 로, 방향이 있고 사이클이 없는 그래프를 말한다. DAG 에서 최단 경로를 찾기 위해 Topological Sorting(위상 정렬)을 이용할 수 있다. Topological Sorting DAG 에서는 사이클이 없기

DAG에서 최단경로를 찾기 위해서는 먼저 위상정렬을 수행하여 topological order를 찾아야 한다.위상 정렬을 하는 방법은 아래 포스트에 정리해놓았다.https://velog.io/@hyeon3356/DAG-%EC%97%90%EC%84%9C-Short

Spanning Tree 최소한의 간선을 사용하여 그래프 내의 모든 정점을 이어준 트리이다. 신장트리 라고도 한다. 특징 하나의 그래프에 여러 개의 Spanning Tree를 가질 수 있다. 노드가 N개 있다면 간선은 N-1개 이다. Minimum Spanning