[ 알고리즘 ] Dynamic Programming : LCS, 최대 공백 정사각형, 금화모으기

1. 최장 공통 부분 서열 (LCS)

 

subsequence는 떨어져 있을 수  있고 substring는 연속되어야 한다.

정확히 말하자면 subsequence은  주어진 서열에서 일부 문자를 삭제한 후에 남은 문자들로 만들 서열을 의미한다.

 

LCS은  X와 Y가 주어질 때 X와 Y의 공통 부분 서열 중 가장 긴 것을 의미한다.

 

1.2. idea

 

LCS(i, j)를 Xi와 Yj의 LCS길이라고 하자. 

우리가 구해야할 길이는 LCS(m,n)이다.

 

• i=0 or j=0  → LCS(i,j) =0
• Xi = Yj  → LCS(i,j) = LCS(i-1,j-1)+1
• Xi ≠ Yj  → LCS(i,j) = max{LCS(i,j-1),LCS(i-1,j)}

 

2. 최대 공백 정사각형

 

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

 

2.1 idea

LES(x, y)를  (x,y)를 우측하단 꼭짓점으로 하는 최대 정사각형의 크기라고 하자.

• (x,y)가 비어있지 않은 경우 → LES(x,y)=0
• 첫번째 행 또는 열의 (x, y)가 비어있는 경우 → LES(x,y)=1
• (x,y)가 비어 있다면 → LES(x,y)=min (LES(x-1,y-1), LES(x,y-1), LES(x-1,y)) + 1

min인 이유 : 모두 k-1 이상이어야 k가 성립하므로 가장작은 것을 기준으로 보면 됨.

 

 

3. 금화 모으기 

 

EXIT에 도착할때까지 최고로 먹을 수 있는 금화의 개수를 구하는 것이 이 문제의 정의이다. 

3.1 idea

 

Cell(i,j)를 현재 위치에서 도착할때까지 도을 수 있응 최대 금화 개수라고 정의를하자.

Cell(i,j) = max{Cell(i-1,j), Cell(i,j-1)} + Coin(i,j)