다이나믹 프로그래밍 DP 테이블 만들기 전략

반복되는 부분 문제를 가진 경우 시간 복잡도를 줄일 수 있는 방법에는 

• 재귀에서 memoization
• dp 테이블 만들기

두 가지 방법이 있다.

 

재귀는 예외 케이스만 잘 처리해주고 이미 계산된 값이면 리턴해주면 된다.

재귀의 관점은 어느 정도 익숙해졌지만 항상 재귀로 풀다 보니 dp 테이블 만드는 방식이 감이 안 왔다.

 

DP 테이블 만들 때 유용한 사고 전략 몇 가지를 생각해봤다. 문제들을 풀어보며 확인한 패턴이다.

보통 dp 테이블을 만들 때는 처음 인덱스부터 하나씩만 훑으면서 테이블을 갱신해간다.

 

1. 해당 인덱스를 포함하거나 포함하지 않거나

어찌 보면 2번과 같은 맥락으로 생각할 수 있지만 직관적으로 1번 표현이 좀 더 자연스러울 때가 있다.

 

2. 해당 인덱스부터 / 해당 인덱스까지

'해당 인덱스부터'는 앞에서부터 훑으면서 테이블을 만들 때 사용된다.

"해당 인덱스까지"는 마지막 원소부터 앞으로 오면서 테이블을 만들 때 사용된다.

 

대부분의 문제는 앞에서부터 훑으면 풀 수 있다. 하지만 직관적으로 아이디어를 떠올릴 때 뒤에서부터 훑는 게 자연스러울 때가 있어서 "해당 인덱스까지"도 고려해보는 게 좋다.

 

3. 이차원 행렬의 경우

• 왼쪽 열, 위 행
• 같은 행 , 왼쪽 열
• 위 행, 같은 열

3가지 전부 혹은 일부를 살핀다.

 

4. state machine 그리기

2번 방식으로 풀리지 않으면 쉽지 않은 문제이다. 공학도라면 유한 상태 머신을 수업 시간에 본 적이 있을 것이다. 모든 경우를 다 고려해서 state machine을 그려본 다음 dp 식을 유도해내야 한다.