To Developer

다익스트라 알고리즘은 시작점에서 다른 모든 정점으로의 최단거리를 구하는 방법이다. 이 방식은 동적 계획법에 기반하여, 다음과 같은 발상에서 시작된다. P에서 R로 가는 최단경로에 사이에 정점 Q가 있다. 이때 이 경로는 마찬가지로 P에서 Q로 가는 최단경로이다. 즉, P->Q까지의 최단경로에, Q->R로 가는 최단경로를 붙여, P->Q->R의 최단경로가 만들어진다. 서론은 여기까지, 알고리즘의 구조를 알아보자. 순서는 이러하다. 시작점을 정한다. 모든 정점을 미방문집합에 넣는다. 시작점으로부터의 거리를 초기화한다. 시작점은 0, 다른 모든 정점은 무한대 미방문집합 중 최단 거리의 정점을 선택한다. 해당 정점을 미방문집합에서 빼고, 현재위치로 한다. 현재위치와 연결된 간선을 따라, 최단 거리를 갱신한다. ..

어떤 항목을 포함할까 말까로 고민하는 문제들의 원형은 대부분 배낭 문제다. 나중에 다시 볼 수 있도록 기록을 남기기 위해, 한번 정리해보고자 한다. 배낭 문제란? 간단하게 말하면, 한 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다. 배낭문제는 짐을 쪼갤 수 있는 경우와 짐을 쪼갤 수 없는 경우 두 가지로 나눌 수 있는데, 이 글에선 짐을 쪼갤 수 없는 경우의 배낭문제인 0-1 배낭문제(0-1 Knapsack Problem)를 다룬다. (넣지 않는 것을 0, 넣는 것을 1로 생각하여 0-1 배낭 문제라고 부른다.) 가방의 무게 제한이 7kg이고, 물건의 무게와 가치가 다..

연쇄 행렬 곱셈 알고리즘 두 개 이상의 행렬을 곱할 때, 최소 곱셈 횟수를 구하는 문제 행렬 곱셈이 뭔지부터 알아보자. 행렬 곱셈(matrix multiplication)은 두 개의 행렬에서 한 개의 행렬을 만들어내는 이항연산이다. 이 때 첫째 행렬의 열 갯수와 둘째 행렬의 행 갯수가 동일해야한다. 곱셈의 결과 새롭게 만들어진 행렬은 행렬곱(matrix product)라 하며, 첫째 행렬의 행 갯수와 둘째 행렬의 열 갯수를 가진다. 행렬 A와 B의 곱은 간단히 AB로 나타낸다. 위 그림을 보면, 행렬 A의 크기는 l * m 이고, B의 크기는 m * n 이다. 그리고 이 두 행렬의 행렬곱 AB(그림에서 C) 는 l * n의 크기를 갖는다. 행렬곱 AB(4 * 3)의 i번째 행, j번째 열 성분은 (이하 ..