Algorithm

2개의 N x N 행렬들을 곱하는 것일반적인 방법으로는 O(N^3) 의 시간이 걸린다일반적인 방법에서 더하기는 생각하지 않고 곱하기 횟수만 세면 N^3이고, N^2보다 빠를 수는 없다.Divide and Conquer로 가능하다정의에 따라 n×n 크기의 두 행렬을 곱하

divide and conquer 개념을 적용하여 곱셈의 시간복잡도를 낮춘 알고리즘

피보나치 숫자를 구하는 알고리즘을 Recursion, Memoization, Dynamic Programming으로 해볼 것이다.

Select Working Days

M1 x M2 x ... * MN행렬을 곱할 때 드는 최소 비용 찾기 문제

모든 가능한 노드의 쌍의 Shortest Path를 구하는 방법 - 노드 K를 거쳐가는 것과 아닌 것 중에서의 가장 짧은 경로를 찾는 Floyd Warshall 알고리즘이 있다.

Approximate string matching 는 비슷한 문자열을 비교하는 것이다. 그 중에서도 한 문자열을 다른 문자열로 만들기 위한 편집거리를 구하는 DP 알고리즘을 정리했다.

LCS에서는 연속적이지는 않더라도 공통 부분 중 가장 긴 길이를 구하는 것이 목적이다.

주어진 nxn 크기의 흑백 이미지에서 검은 점을 포함하지 않는 가장 큰 빈 정사각형을 구하는 문제이다.

특정한 종류의 동전이 있다고 했을 때, 동전을 최소 개수를 사용하여 거슬러주고자 한다. 이 문제도 DP를 사용하여 풀 수 있다.

바둑돌이 K개 있다. 두 사람이 번갈아가며 자신의 차례에 1개, 2개 돌을 가져갈 수 있을 때, 내가 해당 게임에서 이길 수 있는지를 미리 알 수 있다.

각 i에 대해, i에서 끝나는 LIS를 찾는 문제이다. 즉 자기 포함 나한테서 끝나는 가장 긴 Subsequence의 길이를 계산하게 된다.

그래프를 방문하는 여러 방식이 있다.

Cut vertex는 그래프에서 어떤 한 노드 s를 지우면 Disconnected Graph가 될 때 s를 Cut vertex라고 한다.

Topological Sort의 입력은 DAG(Directed Acyclic Graph)이다. 모든 Directed Edge가 왼쪽에서 오른쪽으로 향하도록 노드를 정렬한다.

Strongly Connected Component 란 노드들 중 가장 큰 서브 집합을 의미한다.