[자료구조 및 알고리즘] Dynamic Programming (4)

최대 공백 정사각형

 

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

 

DP Idea

 

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

• LES(x,y) = 0 : (x,y)가 비어있지 않은 경우
• LES(x,y) = 1 : 첫번째 행 또는 열의 (x,y)가 비어있는 경우, base
• LES(x,y) = min(LES(x-1,y-1), LES(x,y-1), LES(x-1,y)) + 1 : 나머지 픽셀 (x,y)가 비어있는 경우, step, 하나라도 작으면 작은 사이즈의 정사각형을 가지고 계산해야함

 

최대 공백 직사각형

 

문제 정의: 주어진 N x N크기의 흑백 이미지에서 검은 점을 포함하지 않는 가장 큰 빈 직사각형을 찾는 문제

 

Idea

 

..

 

동전 거스름돈

 

문제 정의: N원의 거스름 돈을 돌려줄 때, 최소 개수의 동전을 사용하여 거스름 돈을 돌려주는 방법을 구해보자

예시: 1, 4, 6원의 동전이 있을 때, 8원을 거슬러줘야 하는 상황에서 정답은

• case1: Greedy: 6, 1, 1 → 3개
• case2: 4, 4 → 2개

 

이는 단순하게 풀 수 있는 문제가 아님을 보여준다. 참고로 greedy하게 풀려면 동전의 종류가 각각 2배이상 차이가 나야한다.

 

DP Idea

 

C(n)를 크기 Di인 동전으로 n원을 거슬러 줄때의 동전 개수라고 가정하자, C(n)는 아래 값들 중 가장 작은 값이다.

• C(n-Di) + 1 : Di원을 거슬러준 경우 동전 하나 추가, i는 동전 종류 index

 

Longest Increasing Subsequence, LIS

 

문제 정의: N개의 요소가 list에 담겨있을때, 가장 길이가 긴 증가하는 부분배열의 길이를 찾는 문제, 이때 부분배열은 반드시 연속하지 않아도 된다.

 

N^2 is easy by using DP

 

DP Idea

 

LIS(i)를 i번째 값에서 끝나는 최장 길이 증가 부분배열의 길이라고 가정하자. 그렇다면 LIS(i)는 다음과 같다.

• j ≤ i 이고 Array[j] ≤ Array[i] 인 모든 j에 대해,  LIS(i) = max{LIS(j)} + 1

LIS(j)의 max값을 구하기 위해서는 이전의 값들을 모두 봐야하기 때문에 N의 시간복잡도를 갖는다.

따라서 총 O(N^2)의 시간복잡도를 갖는다

 

DP Optimization

 

기억해야하는 LIS값만 기억하면 된다.

2024.07.03 - [[JAVA]/자바[JAVA] 백준] - BOJ(백준 온라인 저지) 2568번 with 자바[JAVA]

BOJ(백준 온라인 저지) 2568번 with 자바[JAVA]

 

따라서 시간복잡도 O(NlogN)에 수행가능하다.

 

금화모으기 ver.1

 

문제 정의: 주어진 격자모양 보드가 있고, 각 칸에 임의의 금화가 있을때, 왼쪽 아래에서 출발해 오른쪽 위로가는 최단거리들 중, 최대로 모을 수 있는 금화의 개수를 찾아보자

 

DP Idea

 

GC(x,y)를 (x,y)에서 경로가 끝나는 최단 거리들 중, 최대로 모을 수 있는 금화의 개수라고 하자. 그렇다면 GC(x,y)는 다음과 같다

• GC(x,y) = max{GC(x-1,y), GC(x,y-1)} + coin(x,y), coin(x,y) = 1if there is a coin at (x,y)

 

금화모으기 ver.2

 

문제 정의: 주어진 격자모양 보드가 있고, 각 칸에 임의의 금화가 있을때, 두 agent가 각각 왼쪽 아래에서 출발해 오른쪽 위로 가고, 오른쪽 아래에서 출발해 왼쪽 위로가는 최단거리중, 최대로 모을 수 있는 금화의 개수를 찾아보자. 단 한 agent가 금화를 모았다면 다른 agent는 모을 수 없다.

 

DP를 적용하려면, 독립적인 기준으로 DP table을 만들어야한다.

LIS는 list의 각 칸을 기준으로, 동전 거스름돈에서는 거슬러줘야하는 돈을 기준으로...

 

따라서 이는 두 agent가 겹치는 칸을 기준으로 DP table을 만든다.

하지만 이때, 두 agent가 겹치는 칸의 개수가 여러 개가 될 수 있다.

 

이를 증명해보자.

 

Prove if it can be more than one cell

 

만약, 겹치는 칸의 개수가 3개라고 해보자.

 

두 agent의 경로가 겹친다는 것은,

한 agent가 이미 갔던 길을 다시 간다는 의미이다.

 

이는 겹치는 칸의 개수만큼 중복해서 금화를 모은다는 것이고,

당연히 겹치는 칸의 개수가 줄면 줄수록, 더욱 많은 칸을 찾아다닐 수 있게된다.

 

따라서 겹치는 칸이 없을 수는 없으니,

가장 많이 금화를 모으는 경로는 두 agent의 경로가 한 칸만 겹쳐야한다.

 

DP Idea

 

GC2(x,y)를 (x,y)에서 두 agent가 겹치는 경우 모을 수 있는 최대 금화의 개수라고 하자. 그리고 GC(x,y)를 다시 다음과 같이 정의하자

• GC(x,y) = GC1(0,0,x,y) 이는 (0,0)에서 (x,y)로 이동하는 agent의 최대 모을 수 있는 금화의 개수

그렇다면 GC2(x,y)는 다음과 같이 구할 수 있다.

• GC2(x,y) = {GC1(0,0,x,y) + GC1(x,y,n,n) + GC1(n,0,x,y) + GC1(x,y,0,n)}

 

금화모으기 ver.3

 

문제 정의: 금화모으기 ver.2에 음수 금화가 있는 경우에, 두 agent가 모을 수 있는 최대 금화 개수를 찾아보자.

 

음수 금화가 있는 경우는 반드시 두 agent가 겹치는 칸의 개수가 한 개일 필요는 없다.

음수 금화가 많다면 이미 한 번 지나간 경로를 다시 지나가는 것이 음수 금화를 만나지 않게 하는 방법이기 때문이다.

 

겹치는 칸이 ㄱ자 모양일 수는 없고,

반드시 일자 모양이어야한다.

 

겹치는 칸을 겹치는 블럭이라고 한다면,

겹치는 블럭의 길이를 하나씩 늘려가면서 금화가 최대가 될 수 있도록 하면된다.

 

DP Idea

 

임의의 y좌표 y에서,

x좌표가 a부터 b까지의 겹치는 블럭인 경우 최대로 모을 수 있는 금화의 개수를 GC3(y,a,b)라고 하자.

그렇다면 a와 b가 달라지면서 GC3의 값이 달라지는 것을 확인할 수 있는데,

 

만약 b의 값이 b+1이 된다면,

오른쪽 아래에서 출발해, 왼쪽 위로 가는 agent는 (y,b)아래의 점들은 지나가지 못하는 대신, (y,b+1)을 지나갈 수 있다.

그렇다면 (y,b)아래의 점들을 통해 얻을 수 있는 금화의 개수와 (y,b+1)을 통해 얻을 수 있는 금화의 개수를 비교하면,

 

겹치는 블럭이 (y,a)에서 (y,b)의 블럭일 때와 (y,a)에서 (y,b+1)일때의 GC3값의 증감을 알 수 있고,

2024.11.01 - [[학교 수업]/[학교 수업] 자료구조 및 알고리즘] - [자료구조 및 알고리즘] Dynamic Programming (2)

[자료구조 및 알고리즘] Dynamic Programming (2)

에 있는 연속되는 최대 부분 배열 알고리즘을 통해 O(N)에 GC3값이 최대가 되는 겹치는 블럭을 찾을 수 있다.

 

따라서 모든 y에 대해서 O(N)이 걸리므로,

겹치는 블럭을 찾는데에는 O(N^2)의 시간복잡도가 소모된다.

 

겹치는 블럭을 찾았으면,

GC2()의 값을 구하듯, 네 부분으로 나누어서 GC1()을 수행하면 GC3()를 알 수 있다.