8.1 동적 계획법_도입

1. 동적 계획법

• 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다.
• 주어진 문제를 더 작은 문제로 나눈 뒤 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 답을 계산한다.
• 이 중 어떤 문제는 다른 두 개 이상의 부분 문제를 푸는데 사용될 수 있기 때문에 답을 여러번 계산하는 대신 한 번만 계산하고 그 결과를 재활용하여 속도를 향상시킬 수 있다.

 

• 캐시(Cache) : 이미 계산한 값을 저장해두는 메모리의 장소
• 중복되는 부분 문제(Overlapping Subproblems) : 두 번 이상 계산되는 부분 문제

---

2. 메모이제이션(Memoization)

• 동적 계획법에서 함수의 결과를 저장하는 장소(캐시, Cache)를 마련해 두고, 한 번 계산한 값을 저장해 뒀다 재활용하는 최적화 기법
• 주어진 입력에 따라 항상 정해진 출력이 주어지는 수학의 함수와 달리 프로그래밍에서의 함수는 여러 요인(전역 변수, 함수 호출 횟수 등)에 따라 매번 다른 결과를 반환할 수 있다.
• 메모이제이션 기법은 참조적 투명성을 지닌 함수의 경우에만 적용할 수 있다.
•  
• 참조적 투명성 : 함수의 반환 값이 입력 값만으로 결정되는지의 여부
• 참조적 투명성 함수 : 입력이 고정되어 있을 때 그 결과가 항상 같은 함수

(1) 구현 패턴

• 항상 기저 사례를 제일 먼저 처리한다. (입력이 범위를 벗어난 경우 등)
• 캐시를 먼저 함수의 반환 값으로 사용될 수 없는 값으로 초기화 한다.(함수가 항상 0이상의 수를 반환한다면 -1로 초기화 한다.)

(2) 시간 복잡도 분석

• 메모이제이션의 주먹구구식 시간 복잡도 분석 방법
• (존재하는 부분 문제의 수) * (한 부분 문제를 풀 때 필요한 반복문의 수행 횟수)
• 이 식은 수행 시간의 상한을 간단히 계산할 수 있는 방법일 뿐 항상 정확하지는 않다.

---

3. 예제 : 외발 뛰기

문제 출처 : algospot.com :: JUMPGAME

algospot.com :: JUMPGAME

(1) 재귀 호출에서 시작하기

1) 완전 탐색 알고리즘 만들기

• 동적 계획법 알고리즘을 만드는 첫 단계는 문제를 재귀적으로 해결하는 완전 탐색 알고리즘을 만드는 것
• jump(r, c) = (r, c)에서 시작해서 맨 마지막 칸까지 도달할 수 있는지 여부를 참/거짓으로 반환
• (r, c)의 값을 jumpSize라고 하면, 아래쪽으로 뛸 경우 jump(r + jumpSize, c) 오른쪽으로 뛸 경우를 jump(r, c + jumpSize)로 표현할 수 있다.
• 이를 재귀적으로 표현하면 다음과 같다.
• jump(r, c) = jump(r + jumpSize, c) || jump(r, c + jumpSize)

2) 점화식을 구현한 코드

def jump(r, c):
    # 기저 사례 1 : 보드판 바깥으로 넘어가는 경우
    if r >= n or c >= n:
        return False

    # 기저 사례 2 : 보드판 마지막 칸(목적지)에 도달하는 경우
    if r == n-1 and c == n-1:
        return True

    jumpSize = board[r][c]

    return jump(r + jumpSize, c) or jump(r, c + jumpSize)

3) 발생할 수 있는 문제점

• 답이 없지만(맨 마지막 칸에 도달할 수 없지만) n이 엄청 커서 탐색을 계속 하는 경우가 있다.
• 수 많은 경로를 일일이 탐색하기 때문에 제한 시간을 초과할 수 있다.
• 또한 수많은 부분 경로들을 중복해서 다시 검사하는 경우가 많다.

(2) 동적 계획법으로 구현하기

1) 메모이제이션

• 먼저 jump() 함수는 주어진 입력에 정해진 답을 반환하는 참조적 투명 함수이기 때문에 메모이제이션 기법 적용이 가능하다.
• 재귀 호출이 진행되면서 (r + jumSize, c) 혹은 (r, c+jumSize) 위치에서 마지막 칸 까지 도달할 수 있는지 여부를 저장하고 이를 다른 부분 문제에서 사용하므로 중복된 연산을 없앨 수 있다.
• 참을 1, 거짓을 0으로 반환하기로 한다면 n * n 크기의 캐쉬를 -1로 초기화하여 사용할 수 있다.

2) 동적 계획법으로 구현한 코드

# 부분 문제의 결과값을 저장한다.
cache = [[-1] * n for _ in range(n)] # 메모이제이션을 위한 2차원 리스트

def jump2(r, c):
    # 기저사례 1
    if r >= n or c >= n:
        return 0 # False

    # 기저사례 2
    if r == n-1 and c == n-1:
        return 1 # True

    # 메모이제이션
    result = cache[r][c]

    # 기존에 부분 문제를 해결한 경우 그 결과값을 그대로 반환
    if result != -1:
        return result

    # 부분 문제를 해결한 적이 없다면 문제를 새롭게 해결
    jumpSize = board[r][c]

    # 메모이제이션 cache에 저장
    cache[r][c] = jump2(r + jumpSize, c) or jump2(r, c + jumpSize)

    return cache[r][c]

---

github 1 : Algorithmic_Problem_Soving_Strategies/code8_4.py at main · LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies (github.com)

LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies

github 2 : Algorithmic_Problem_Soving_Strategies/code8_5.py at main · LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies (github.com)

LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies