Hirschberg's Trick(BOJ 18438)

점화식 : $DP[i][j]=min(DP[i−1][j],DP[i][j−1])+C[i][j]$
Naive Complexity: $O(nm)$ memory usage
Optimized COmplexity: $O(n+m)$ memory usage

Hirschburg's Trick은 대회에 많이 출제되거나 유용한 알고리즘은 아니다. 시간 복잡도를 최적화하는 것이 아니라 공간 복잡도를 최적화하기 때문이다.

하지만 아이디어 자체는 상당히 흥미롭기 때문에 공부해 볼만한 알고리즘이라고 생각한다.
( solved.ac 티어도 올릴 수 있다)

LCS 5

LCS 알고리즘은 시간복잡도 O(N M), 공간복잡도 O(N M)을 필요로 한다고 알고 있다. 한번 그 방법을 살펴보자.

0	(0)	C(1)	A(2)	P(3)	C(4)	A(5)	K(6)
(0)	0	0(left)	0(left)	0(left)	0(left)	0(left)	0(left)
A(1)	0(up)	0(up)	1(wow!)	1(left)	1(left)	1(wow!)	1(left)
C(2)	0(up)	1(wow!)	1(up)	1(up)	2(wow!)	2(left)	2(left)
A(3)	0(up)	1(up)	2(wow!)	2(left)	2(up)	3(wow!)	3(left)
Y(4)	0(up)	1(up)	2(up)	2(up)	2(up)	3(up)	3(left)
K(5)	0(up)	1(up)	2(up)	2(up)	2(up)	3(up)	4(wow!)
P(6)	0(up)	1(up)	2(up)	3(wow!)	3(left)	3(left)	4(up)

이게 우리가 아는 방법이다.
여기서 우리는 3행에 주목해보자.
3행은

A(3)	0(up)	1(up)	2(wow!)	2(left)	2(up)	3(wow!)	3(left)
color	a	b	c	d	e	f	g

이렇게 생겼고 각각을 a~g에 해당하는 색으로 칠한다고 생각하자.
이 때, 우리는 토글링을 이용하여 다음 행의 색 또한 구할 수 있다.

4행

Y(4)	0(up)	1(up)	2(up)	2(up)	2(up)	3(up)	3(left)
color	a	b	c	d	e	f	f

5행

K(5)	0(up)	1(up)	2(up)	2(up)	2(up)	3(up)	4(wow!)
color	a	b	c	d	e	f	f

6행

P(6)	0(up)	1(up)	2(up)	3(wow!)	3(left)	3(left)	4(up)
color	a	b	c	c	c	c	f

이 때, 우리는 (6,6)이 f임을 이용하여 LCS 경로가 3행에서 (3,5)를 지난다는 것을 알수있다.
( 시간복잡도 $O(NM)$, 공간복잡도 = $O(N)$ )

그렇다면 이제는 같은 연산을 (0,0)~(3,5), (3,5)~(6,6) 에 대해
반복할 수 있을 것이다.

0	(0)	C(1)	A(2)	P(3)	C(4)	A(5)
(0)	0	0(left)	0(left)	0(left)	0(left)	0(left)
A(1)	0(up)	0(up)	1(wow!)	1(left)	1(left)	1(wow!)
C(2)	0(up)	1(wow!)	1(up)	1(up)	2(wow!)	2(left)
A(3)	0(up)	1(up)	2(wow!)	2(left)	2(up)	3(wow!)

와

C(4)	A(5)
3(wow!)	3(left)
3(up)	3(left)
3(up)	4(wow!)
3(left)	4(up)

에서 위 연산을 계속 반복할 수 있을 것이다.
이를 통해서 LCS 문제를 시간복잡도는 유지하면서, 공간복잡도 $O(n)$만에 해결할 수 있다.

추천 문제
편집 거리(Hard)