[Algorithm] 🚩[백준] 2167 (Feat. DP, 동적계획법)

> 동적계획법 (Dynamic Programming)

한 번 계산된 문제는 다시 계산하지 않도록 한다.

• 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법
• 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산X
• 사용 조건

1. 최적 부분 구조(Optimal Substructure) : 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결 할 수 있다.
2. 중복되는 부분 문제(Overlapping Subproblem) : 동일한 작은 문제를 반복적으로 해결해야 한다.

• 대표적인 예시 : 피보나치 수열
  피보나치 수열의 재귀적 풀이는 O(2^n)이고, 단순 반복 풀이는 O(N) 이다.
  재귀 함수로 해결하면, 중복되는 부분 문제가 발생한다. 이는 다이나믹 프로그래밍으로 해결할 수 있다.

1. Memoization (Top-Down, 하향식) : 큰 문제를 해결하기 위해서 작은 문제들을 재귀적으로 호출하여 큰 문제에 대한 답을 얻음

• 한 번 계산한 결과를 메모리 공간에 메모
• 같은 문제를 다시 호출하면 메모했던 결과 가져오기
• 값을 기록해 놓는다는 점에서 캐싱(Caching)이라고도 함

# Memoization (Top-Down, 하향식)

# 한 번 계산된 결과를 메모이제이션 하기 위한 리스트 초기화
d = [0]*100 

# 피보나치 함수를 재귀함수로 구현(탑다운 다이나믹 프로그래밍)
def fibo(x):
   	# 종료 조건(1 혹은 2일 때 1을 반환)
    if x == 1 or x == 2:
    	return 1
    # 이미 계산한 적 있는 문제라면 그대로 반환
    if d[x] != 0:
    	return d[x]
    # 만약 계산한 적이 없다면 점화식에 따라서 피보나치 결과 반환
    d[x] = fibo(x-1) + fibo(x-2)
    return d[x]

print(fibo(99))

💡 2. Tabulation (Bottom-up, 상향식) : 단순 반복문 이용

• 다이나믹 프로그래밍의 전형적인 형태

# Tabulation (Bottom-up, 상향식)

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100

# 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
d[1] = 1
d[2] = 1
n = 99

# 피보나치 함수 반복문으로 구현
for i in range(3, n+1):
	d[i] = d[i - 1] + d[i - 2]
    
print(d[n])

---

<처음 시도>

n, m = map(int, input().split())
tot = [list(map(int, input().split())) for _ in range(n)]
k = int(input())


def solution(tot):
    i, j, x, y = map(int, input().split())
    sum = 0
    for a in range(i, x+1):
        for b in range(j, y+1):
            sum += tot[a-1][b-1]

    return sum


for _ in range(k):
    print(solution(tot))

시간 제한 2초이고 시간 복잡도 O(N^2)인 것 같은데 왜 시간초과가 생길까?
-> 아.. 함수를 호출하니까 시간 복잡도가 O(N^3)이겠구나.. 큰 착각을..

<재시도>

n, m = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(n)]

# 누적합 테이블 만들기
dp = [[0]*(m+1) for _ in range(n+1)]
for a in range(1, n+1):
    for b in range(1, m+1):
        dp[a][b] = lst[a-1][b-1] + dp[a][b-1] + dp[a-1][b] - dp[a-1][b-1]

k = int(input())
for _ in range(k):
    i, j, x, y = map(int, input().split())
    print(dp[x][y] - dp[x][j-1] - dp[i-1][y] + dp[i-1][j-1])

이해하는데 참고한 자료