210706 동적 계획법(DP) 2- LCS ,OBST

LCS ( Longest Common Subsequence) - 최장 공통 부분수열, 문자열 를 DP로 해결

LCS의 예시)

목표: 부분수열이기에 중간에 맞지 않다면 문자 사이를 건너뛰어 공통되면서 가장 긴 문자열을 찾는 것

 

해결법 :

를 다시 정리하면

1.  문자열 X, 문자열 Y의 한 글자씩 비교
2.  두 문자가 같다면 LCS[i - 1][ j - 1 ] +1 
3.  두 문자가 다르다면 LCS[i - 1][ j ] 와 LCS[ i ][ j - 1 ] 중 큰 값 표시
4.  1 ~ 3 번 과정 반복

 

앞서 예로 들었던 malestrom 과 becalm 으로 과정을 보이면

 

한 단어를 기준으로 잡고 한 글자씩 잡고 위의 점화식대로 테이블을 채워나간다 

예를 들어 b를 기준으로 잡고 m,a,l,e....m 까지 검사 이 경우 문자가 같은 경우가 없으니 검사하는 칸의 왼쪽 칸과 위쪽 칸 값 중 큰 값을 채워 넣는다. 

주황색 글씨로 같은 문자가 존재하여 값이 증가하는 부분 중 하나를 보였고 위의 과정들을 거쳐 위 처럼 테이블을 채우면 오른쪽 가장 밑의 요소가 LCS 값이 된다.

 

OBST (Optimal Binary Search Tree)  : 최적 이진 검색 트리

최적 이진 검색 트리(OBST)는 이진 탐색 트리인데,
주어진 값의 가중치나 확률을 이용하여 평균 탐색하는 횟수를 최소로 만드는 이진 탐색 트리이다

반대로 말하면 가중치나 확률이 주어지지 않는다면 OBST 구성 못한다는 것

사용되는 예를 들면 문서에 있는 단어를 검색 할때 단어가 많이 중복되어 있는 경우 특정 단어에 대해서 검색 횟수가 많은데 어떤 단어는 검색이 거의 사용되지 않을 수 있기에 최적 이진 검색트리를 이용해 자주 검색하는 단어의 경우 접근이 편하게 위쪽에 배치하고 사용하지 않을수록 트리의 밑에 배치하는 것을 예로 들 수 있다.

 

해결법 :

BST(이진 검색 트리) 특성상 어떤 BST의 왼쪽, 오른쪽 서브트리가 각각 최적의 BST이어야 해당 BST도 최적

즉 i 번째 key 부터 j 번째 key 까지의 최적 BST 평균 검색 시간을 A[ i ][ j ] 이라 하고 루트가 k 번째 key일 때,

• 왼쪽 서브트리 탐색시간 : A[ 1 ][ k - 1 ]
• + 오른쪽 서브트리 탐색 시간 : A[ k + 1 ][ n ]
• + 루트 노드 탐색 시간 : 시그마 p_m 

이를 다시 표현하면