DP = DFS + 백트래킹 ?

백준 14501 퇴사 문제

• 백준 14501 문제를 풀기 위해서 여러 접근법을 생각해보다가 생긴 궁금증

궁금증 발견

• 문제를 보고 나는 크게 2가지의 접근법을 생각해낼 수 있었다. 첫 번째는 dp, 두 번째는 DFS
• dp는 top down 방식으로 재귀호출을 이용하여 완전탐색하며 이미 구했던 결과값은 return 하여 중복을 넘어가는 원리였다.
• 하지만 DFS 도 생각해보니 재귀호출을 이용하여 완전탐색 하는데 여기에 중복된 부분은 넘어가는 백트래킹 기법을 적용하면 dp와 동일한 원리였다.
• 원리는 비슷한 것 같은데 이름은 다르고... 개념이 머릿속에서 정리되지 않았다. 따라서 내가 받아들이기 쉽게 정리를 해보았다.

나만의 정리

• 브루트포스 - 가능한 모든 경우의 수를 구하는 기법을 통칭함 = 완전탐색 (순차탐색, DFS, 비트마스킹)
• DFS - 그래프를 탐색하는 방법 중 하나로 재귀호출을 이용하는 완전탐색 기법 (브루트포스 ⊃ DFS)
• 백트래킹 - DFS를 이용하여 재귀호출 완전탐색중에 불필요한 부분은 건너뛰는 기법

• Dynamic Programming 이란

  재귀호출을 이용해서 문제를 해결하는 도중 최적 부분 구조가 나타나면서 중복된 연산을 수행하게 될 때 중복된 부분을 제거하는 기법

  - 여기서 재귀호출은 DFS 의 문제해결 원리
  - 중복된 부분을 제거하는 것은 백트래킹 원리
  

• 만약 Top down dp 재귀호출이 완전탐색을 수행하면, DP = DFS + 백트래킹 이라고 볼 수 있음
• 아래 코드에서 topdown 함수명을 dfs로 바꾸고 if -elif - if 부분을 백트래킹 부분이라고 보면된다.

import sys
import math

def topdown(day):

    # 정확히 마지막 날의 경우
    if day-1 == n:      
        return 0

    # 퇴사일을 넘어가는 경우
    elif day > n:
        return -math.inf
    
    if dp[day] != -1:
        return dp[day]
    
    # day를 기준으로 일을 하지 않고 바로 다음날로 가거나, 일을 하고 일한 날짜만큼 뒤로 가거나
    dp[day] = max(topdown(day+1), topdown(day+T[day])+P[day])
    return dp[day]
    
n = int(sys.stdin.readline())
T = [0] 
P = [0]
dp = [-1] * (n+1)

for _ in range(n):
    t,p = map(int,sys.stdin.readline().rstrip().split())
    T.append(t)
    P.append(p)

print(topdown(1))

• 하지만 Bottom up dp 방식일 때는 동일하지 않다.