다이나믹 프로그래밍 (DP) - 접근 방법

DP의 기본적인 개념정리는 아래에 적어두었습니다.

다이나믹 프로그래밍 (Dynamic Programming)

 

 

 

접근방법

다양한 조건을 가진 dp 문제를 만나다 보니 dp문제를 만났을 때 어떻게 대처를 해야 하는가를 정리해서 적어보려고 합니다.

dp라는 거 자체가 "하위문제부터 차례로 구해나가서 최종적인 답을 도출해 내는 형태의 알고리즘"이라는 형식이 기본 전제조건이다 보니

dp는 크게 2가지 방법으로 문제를 풀 수 있다고 생각합니다.

1. 과거의 값으로 현재의 값을 구성하는 방식.
   
2. 현재의 값으로 미래를 구성하는 방식.

위와 같은 방식들을 풀어서 적어보자면

 

1.  과거의 값으로 현재의 값을 구성하는 방식.

"dp[i] = dp[i - 2] + dp[i - 1]" 

i의 값을 구하기 위해서 이전의 값들을 가져오는 방식. 

계산을 하는 기준을 현재의 값 ( i ) 로 잡고 이전의 값들을 가져다가 값을 구성하는 방식이 있다고 생각을 합니다.

 

 

2. 현재의 값으로 미래를 구성하는 방식.

"dp[i + 1] = dp[i - 1] + dp[i]"

i + 1의 값을 구하기 위해 현재의 값으로 미래의 값을 지정해 주는 방식.

1번과는 다르게 계산하려는 기준을 i + 1 즉 미래의 값으로 잡고 현재의 값 등을 가져다가 값을 구성하는 방식이 있다고 생각합니다.

 

 

1번 예제와 2번 예제에서 알 수 있듯이

"dp[i] = dp[i - 2] + dp[i - 1]"과 "dp[i + 1] = dp[i - 1] + dp[i]" 모두 피보나치의 수를 구하는 dp 점화식으로

최종적으로 피보나치수의 원하는 값을 가져오는 것은 1번과 2번 모두 가능하다고 생각이 들었습니다.

그래서 생각이 들었던 게
"dp문제에 상관없이 1번과 2번 모두 접근하는 방법에 차이이고 뭐가 맞다, 뭐가 틀리다, 결론적인 차이에서는 상관이 없는 건가?"

라는 생각이 들어 두 가지 방법 모두로 

2579번: 계단 오르기

위의 문제 풀이를 진행했었습니다.

두가지 모두로 풀이를 진행하다 보니 

[백준] 2579번 - 계단 오르기 (C++)

 

 

결론

위와 같은 결과가 나오게 되었는데 핵심만 정리를 해보자면

"그냥 제약조건이 없는 dp문제가 아닌 사전에 dp에 대한 제약조건이 걸려있다면 1번의 방법(과거의 값으로 현재의 값을 구성하는 방식.)

을 사용하는 것이 좋다."라는 결론을 가지게 되었습니다.

왜냐하면 현재의 값을 기준으로 미래의 값을 정의하는 것은 미래의 값이 어떻게 되고 제한조건이 미래에는 어떻게 작용이 될 것인지
미리 생각을 하고 접근을 해야 하는 경우가 필수적으로 필요하게 되는데 그 과정에서 추가적으로 계산해줘야 하는 식이 붙게 되고 코드의 복잡도가 올라가게 된다고 생각하였습니다.

그 방법과 다르게 과거의 값으로 현재의 값을 구성하는 방식은 이미 지나온 과정을 바탕으로 현재의 값을 생각하는 과정이기 때문에 지금을 바탕으로 생각하는 방식이라 2번 방법에 비해 훨씬 덜 복잡하고 직관적으로 문제의 접근을 할 수 있게 되는 거 같습니다.