LCS / ALL Pair Shortest Path / 타일링

LCS

• 두개의 DNA 순서열 있을 때, 이 두개가 얼마나 비슷한가를 측정할 것입니다. 디엔에 순서열 ACGT 이루어진 문자열 두개 디앤에이 순서열 비슷한 정도는 LCS 로 판별할 수 있음. 공통된 부분 서열 중 가장 긴 것을 의미한다. 
  
  LCS., LIS
  공통 부분 문자열 이라고 말할 수 있따. 2개는 다른 의미를 가지고 있기 때문에 구분해야 한다.

 

All Pair Shortest Path

• 모든 정점 1부터 엔까지의 수로 표현 되어지는 가중치가 있는 방향 그래프.
  두 정점에서 가는 최단 경로의 길이를 구하는 프로그램 작성.
  
  테케 티
  정점 개수 간선의 개수.