전체 글

Floyd 알고리즘 I 문제: 가중치 포함 그래프의 각 정점에서 다른 모든 정점까지의 최단거리 를 계산하라. 입력: 가중치 포함, 방향성 그래프 와 그 그래프에서의 정점의 수 . 출력: 최단거리의 길이가 포함된 배열 알고리즘 void floyd(int n, const number W[][], number D[][]) { int i, j, k; D = W; for(k=1; k

최적 이진 탐색트리 (Optimal BST) 이진 탐색 트리 루트의 왼쪽 서브트리에 있는 원소의 키 값은 루트보다 작고, 루트의 오른쪽 서브트리에 있는 원소의 키 값은 루트보다 큰 이진 트리 최적 이진 탐색 트리 트리 내의 키와 각 키가 탐색될 확률이 주어져 있을 때 그 트리의 평균 탐색 비용, 즉, 평균 비교 횟수를 계산하고 이를 최소화하는 탐색 트리를 구축하는 문제 키 값이 일 경우, 는 이진 탐색 트리의 i부터 j 까지의 노드에 대한 최소 평균 탐색 시간 점화식 알고리즘 OptimalBST(p[], r[], n) { for (i ← 1; i ≤ n; i ← i + 1) do { A[i,i] ← p[i]; r[i,i] ← i; } for (h ← 1; h < n; h ← h + 1) do { for ..

연쇄 행렬 곱셈 (Matrix-chain Multiplication) i × j 행렬과 j × k행렬을 곱하기 위해서는 일반적으로 i × j × k번 만큼의 기본적인 곱셈이 필요하다. 연쇄적으로 행렬을 곱할 때, 어떤 행렬곱셈을 먼저 수행하느냐에 따라서 필요한 기본적인 곱셈의 횟수가 달라지게 된다. 예를 들어서, 다음 연쇄행렬곱셈을 생각해 보자: A1 × A2 × A3 A1의 크기는 10 × 100이고, A2의 크기는 100 × 5이고, A3의 크기는 5 × 50라고하자. A1 × A2를 먼저 계산한다면, 기본적인 곱셈의 총 횟수는 7,500회 A2 × A3를 먼저 계산한다면, 기본적인 곱셈의 총 횟수는 75,000회 따라서, 연쇄적으로 행렬을 곱할 때 기본적인 곱셈의 횟수가 가장 적게 되는 최적의 순서..

스트링 편집거리 (Levenshtein Distance) 두 스트링의 유사도를 측정하기 위해 사용 Levenshtein Distance(LD)라고도 함 원래의 스트링을 𝑆(source), 편집하고자 하는 목표 스트링을 𝑇(target), 각각의 문자열의 길이를 𝑚,𝑛 𝛿_𝐼는 삽입 연산의 비용 𝛿_𝐷는 삭제 연산의 비용 𝛿_S는 교환 연산의 비용 편집 거리 : 𝑆를 𝑇로 변환하는데 필요한 삽입,삭제,대치연산의 최소 비용 𝑆 = “test”, 𝑇=“test” → LD(𝑆, 𝑇) = 0 𝑆 = “test”, 𝑇=“tent” → LD(𝑆, 𝑇) = 1 편집 거리가 커질수록, 두 스트링의 유사도는 낮아지게 됨 𝐷[𝑖][𝑗]를 𝑆=𝑠1𝑠2 ...𝑠𝑗와 𝑇=𝑡1𝑡2 ...𝑡𝑖 사이의 편집 거리라고 할 때, 𝐷[𝑖]..

0-1 Knapsack Problem 문제 : 라고 할 때, 를 만족하면서 가 최대가 되도록 가 되는 를 결정하는 문제이다. 무작정 (탐욕적) 알고리즘 개의 물건에 대해서 모든 부분집합을 다 고려한다. 그러나 불행하게도 크기가 인 집합의 부분집합의 수는 개 이다. 동적계획적인 접근 방법 𝑖> 0이고 𝑤>0일 때, 전체 무게가 𝑤가 넘지 않도록 𝑖번째 까지의 항목 중에서 얻어진 최고의 이익(optional profit)을 𝑃[𝑖][𝑤]라고 하면, 와 같다. 이때, 𝑃[𝑖 − 1][𝑤]는 𝑖번째 항목을 포함시키지 않는 경우의 최고 이익이고, 𝑝𝑖 +𝑃[𝑖−1][𝑤−𝑤𝑖]는 𝑖번째 항목을 포함시키는 경우의 최고 이익이다. 코드 실습은 아래 github 링크 참고해 주세요. https://github.com/o..

Graph 현상이나 사물을 정점(vertex)과 간선(edge)으로 표현한 것 Graph G = (V, E) V : 정점 집합 E : 간선 집합 두 정점이 간선으로 연결되어 있으면 인접하다고 한다. 인접 = adjacent 간선은 두 정점의 관계를 나타낸다. 그래프 용어 정점(vertex, node), 이음선(edge, arc) 방향 그래프(directed graph) 가중치(weight), 가중치 포함 그래프(weighted graph) 경로(path), 단순경로(simple path) - 같은 정점을 두번 지나지 않음 순환(cycle) - 한 정점에서 다시 그 정점으로 돌아오는 경로 순환 그래프(cyclic graph) vs 비순환 그래프(acyclic graph) 길이(length) 그래프의 표현 ..