[TIL] DP 알고리즘적 접근법

지난주 일요일 pintos 공부를 하고 있는 극악의 지옥주로 바쁜 와중에도 알고리즘 스터디에 참여해준 전사들이 있다.

 

그 전사들과 DP 문제 하나로 서로 다른 접근법에 대해 토의하며 하루를 마쳤는데

 

아직 나는 DP 문제를 보면, 어떻게 접근 해야될지 몰라 손쓸 새도 없이 포기할 수 밖에 없었다.

 

 

그래서 의미 있게 pintos 2주차를 시작하기 전에

 

DP 알고리즘적 접근법에 대해 포스팅하며 머리를 환기하고자 한다.

 

---

 

BaekJun - #1309 : 동물원 (Dynamic Programming)

https://www.acmicpc.net/problem/1309

1309번: 동물원

 

 

이 문제는 DP 알고리즘을 통해 문제를 접근해야 한다.

 

사자는 우리를 찢어

 

 

2*n개의 우리가 있는데 그 안에 사자를 상하좌우로 붙어있지 않게 배치해야 한다.

 

이 문제는 어떻게 접근할까?

 

 

나는 항상 구현하는 것에 익숙해져 있는 나머지

 

문제의 법칙을 파악하는 것보다 문제의 예외를 찾아내 구현을 하는 것부터 생각하기 시작하곤 한다.

 

하지만 DP는 절대 구현으로는 풀리지 않는다.

 

점화식을 자기만의 방식으로 찾아내고, 그 점화식을 이용하여 타뷸레이션이나 메모이제이션을 사용해야 한다.

 

 

DP 문제 접근에 익숙한 팀원에게 물어보니

 

DP는 보통의 경우 bottom-up이 많아서 그 방식으로 접근해야 하는데,

 

먼저 n 상황의 값을 구하고 싶을 때, n의 의사결정에 영향을 미치는 요소와의 관계를 파악하고

 

초기 값을 통해 n의 값을 구하면 된다고 했다.

 

 

이 문제를 통해 그 방법이 어떻게 되는지 알아보자.

 

 

---

접근 순서

1. 구하고 싶은 값이 무엇인가? : 2*N 개의 우리 안에 사자를 배치하는 경우의 수

 

2. N번째 우리에 사자를 배치하는데 영향을 미치는 요소는 무엇인가? : n-1번째 우리 안에 사자를 배치하는 방법

 

3. 미치는 요소와 N번째 사이 관계를 수식으로 세워보시오.

 

 

 

'n번째 우리에 사자를 넣는 경우의 수' 를 F(n) 이라고 해보자.

 

그럼 다음과 같은 식을 세울 수 있다.

 

F(n) = 'n번째 우리에 사자를 안넣는 경우 = F(n,0)' + '왼쪽 우리에 넣는 경우 = F(n,L)' + '오른쪽 우리에 넣는 경우 = F(n,R)'

 

 

잘 생각해보면 n번째 우리에 사자를 안 넣는 경우는 F(n-1)에 영향을 주지 않는다.

 

따라서 f(n,0) = f(n-1) 과 같다.

 

 

그리고 간단히 생각하면

 

- f(n,L) = f(n-1,0) + f(n-1,R) 의 값을 가지게 되고

 

- f(n,R) = f(n-1,0) + f(n-1,L) 의 값을 가진다는 것을 확인할 수 있다.

 

따라서 'F(n) = F(n-1) + F(n-1,0) + F(n-1,R) + F(n-1,L) + F(n-1,0)' 라는 수식이 완성된다.

 

 

근데 이때, 중간 수식을 묶어 보면

 

'F(n) = F(n-1) + F(n-1,0) + F(n-1,R) + F(n-1,L) + F(n-1,0)'

 

빨간 색으로 표시한 값이 F(n-1)의 값과 동일하다는 것을

 

처음 F(n)을 구할 때의 규칙을 통해 알 수 있다.

 

 

그리고 맨 뒤의 F(n-1,0)은 F(n-2)와 같다.

 

따라서 최종적으로

 

'F(n) = F(n-1) + F(n-1) + F(n-2) = 2*F(n-1) + F(n-2)' 가 되는 것이다.

 

 

이 점화식을 찾았다면

 

Bottom-up 방식으로 n의 우리에서의 경우의 수를 찾을 수 있었다.

 

 

 

---

마치며

 

문제의 점화식을 세우는 것은 중요하다.

 

하지만 문제의 점화식을 세우기 위해서는 문제를 이해해야 하고,

 

동물원같은 문제를 이해하기 쉬운 규칙에서도 점화식을 구하는데에 어려움이 있을 수 있다.

 

 

실제로 나에게 많이 부족한 역량이고, 이 부분은 여러 DP를 많이 접근해서 모든 DP 문제의 접근 틀을 세우는 것이 중요할 것 같다.

 

 

이 방식에서는 N번째의 의사결정을 위해 연관되는 것이 무엇인지 파악하고,

 

그와의 관계를 원자단위로 쪼개 식을 세움으로써

 

전체 식을 도출해 낼 수 있었다.