[중간고사] 4. Dynamic Programming

예상문제 1. Divide and Conquer과 Dynamic Programming의 차이점을 서술하시오.

	Divide and Conquer	Dynamic Programming
공통점	큰 문제를 작게	큰 문제를 작게
차이점	- Top-down 접근 방식 - 상호 관련이 없는 경우에 효율적 근데 관련 있으면 비효율적	- Bottom-up -  재 컴퓨팅 xx -> 저장 + look it up 그러니까 관련 있는 거할 때 효율적
예시	Merge Sort, Quick Sort	Longest Common Subsequence, Matrix Chain Multiplication

 

예상문제 2. LCS(Longest Common Subsequence)

시간복잡도: O(mn)

- 여기서 m과 n은 각각 두 문자열의 길이를 나타냄

- 두 문자열의 길이에 비례하여 작동하기 때문에, 문자열의 길이가 증가할수록 연산량도 증가

 

 

LCS Pseudo Code

LCS[0][] = 0
LCS[][0] = 0

Start from LCS[1][1]
Compare X[i] and Y[j]
    If X[i] = Y[j] # 같으면
        LCS[i][j] = LCS[i-1, j-1] + 1 # 역슬래쉬 + 1   
        Point an arrow to LCS[i][j] # 내 자리 저장
    Else # 다르면 
        LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1]) # 왼쪽 옆과 위 중 큰 수로
        Point an arrow to max(LCS[i-1][j], LCS[i][j-1]) # 그 친구의 시초를 찾는 거임

 

LCS Back Pointer Sudo Code

i <- n, j <-m

while Mij > 0
	print Bij
        (i, j) <- Bij - (1, 1)

 

Example

#1. Determine an LCS of  <T, H, O, R, N, Y> and <E, N, T, R, O, P, Y> 

 

Example

#2. Determine an LCS of <1, 0, 0, 1, 0, 1, 0, 1> and <0, 1, 0, 1, 1, 0, 1, 1, 0>

---

LCS "M" part	LCS "B" part
같아? 역슬(래시) + 1	내 위치 저장
달라? 위 옆 중 큰놈	큰놈의 위치를 저장 (옆 위치 or 위 위치)
	두 값이 같을 때 (옆 위치)

 

최종 답 구하기!

위치 ← 값 - (1, 1)

(i, j)  ← Bij - (1, 1)