동적 계획법(DP)

메모이제이션 구현 패턴

아래의 함수를 메모이제이션으로 바꾸자.

# 반환 값은 항상 음이 아닌 정수
someObscureFunction(a, b);

• 항상 기저 사례를 제일 먼저 처리.
• 함수의 반환 값이 항상 0 이상이라는 점을 이용해 cahce[]를 모두 -1로 초기화.
  {반환 값이 음수일 수도 있다면 사용 불가.}
• return 이 cache[a][b]에 대한 참조형이라는 것 유의.
  {인덱스 순서에 대한 실수가 줄어든다.}

cache = [[-1] * 2500 for _ in range(2500)]

def someObscureFunction(a, b):
	# 기저 사례를 처리.
    if ...:
    	return ...
    # [a][b]에 대한 답을 구한 적이 있으면 반환.
    ret = cache[a][b]
    if ret != -1:
    	return ret
    # 답을 구하자.
    ....
    return ret

예제)

외발 뛰기.

input :

• n * n 크기의 격자 , 정수(1 <= 정수 <= 9)
• 각 칸에 정수만큼 아래쪽이나 오른쪽으로 이동.

output :

• 시작점에서 끝점으로 도달이 가능한가?

동적 계획법의 첫 단계 : 재귀호출에서 시작하자.

현재 문제의 기저 사례는 ? 현재 위치가 '끝' 점인가
그렇지 않다면, 아래 / 오른 쪽으로 이동할 때 여전히 격자 안에 위치한다면 재귀를 실행하자.

-->>
현재 문제의 기저 사례는 ? 현재 위치가 '끝' 점인가 와 격자 안에 존재하는가
두가지를 판별하고 언제나 재귀를 실행해라.

#격자의 길이
n
# 입력을 받았으면 1줄씩 넣으면 됨.
board[]
def jump(x, y):
    # 기저사례중 1. 현재 격자 안인지 판별.
    if x >= n or y >= n:
    	return False
    # 2. '끝'점인지 확인
    if y == n - 1 and x == n - 1:
    	return True
    jumpSize = board[x][y]
    return jump(x + jumpSize, y) or jump(x, y + jumpSize)

왜 or로 재귀를 실행하는 가?
-> 끝 점에 도달하는 지 판별만 하면 되기 때문. 그리고 리턴값이 boolean이기에 가능하다.

메모이제이션 적용.

우리는 있는지 없는지만 판별할 거기에 boolean값을 이용하는데 이를 리스트에 넣어서 이용할 것이니 '0'과 '1'을 이용해 나타낸다.

#격자의 길이
n
# 입력을 받았으면 1줄씩 넣으면 됨.
board[]

# 중복되는 계산 값들을 저장할 리스트.
cache = [[-1] * 100 for _ in range(100)]

def jump(x, y):
    # 기저사례중 1. 현재 격자 안인지 판별.
    if x >= n or y >= n:
    	return 0
    # 2. '끝'점인지 확인
    if y == n - 1 and x == n - 1:
    	return 1
        
    ret = cache[x][y]
    if cache != -1:
    	return ret
        
    jumpSize = board[x][y]
    
    return ret = (jump(x + jumpSize, y) or jump(x, y + jumpSize))