Optimization Problem

문제를 해결하는 최적의 답(optimal solution)을 찾아야 하는 문제들을 말한다. optimal solution은 하나 혹은 그 이상이다.

보통 maximum 혹은 minmum value를 가지는 solution을 찾는 문제들이 주를 이룬다. 예를 들어 가장 빨리 도착하는 경로의 소요시간은 무엇이고 언제 주식을 사고 팔 때 수익이 가장 높은지 등이 있다. 여기서 소요 시간은 value, 경로는 solution이 된다. 그리고 후자는 수익이 value, 언제 사고 팔 때가 solution이 된다.

즉 value는 실제로 solution을 통해 나온 값을 말하며 solution은 해당 value를 구하기 위한 방법을 말한다.

DP (dynamic programming)

optimization problem을 해결하는 전략 중 하나이다. 이는 subproblem(s)의 optimal solution(s)을 활용해서 problem을 optimal solution을 찾는 방식을 말한다. 여기서 겹치는(overlapping) subproblems은 한 번만 계산하고 그 결과를 저장한 뒤 재사용하는 방식이다.

이 방식에는 두 가지 방식이 있다.

	Top-Down approach	Bottom-Up approach
구조	recursive	iterative
subproblem 결과 저장	memoization	tabulation
언제 선호되는지	subproblems의 일부만 계산해도 최종 optimal solution을 구할 수 있을 때	모든 subproblems을 계산해야 최종 optimal solutuion을 구할 수 있을 때

여기서 recursive방식은 function call의 결과를 저장해서 이 후 재사용 하는 방식을 말하고 iterative방식은 for문을 돌며 차근차근 데이터를 저장하는 방식을 말한다.

DOP를 사용한 알고리즘 설계 순서

1. 주어진 문제의 optimal solution이 구조적으로 어떤 특징을 가지는지 분석한다.
2. 재귀적인 형태로 optimal solution의 value를 구한다.
3. (주로) Bottom-Up 방식으로 optimal solution의 value를 구한다.
4. 지금까지 계산된 정보를 바탕으로 optimal solution을 구한다.

Climbing Stairs(계단 오르기)

정상까지 오르는데 n번의 스텝이 필요한 계단이 있습니다. 한 번에 한 스텝 혹은 두 스텝을 오를 수 있을 때, 계단의 정상까지 오르기 위해 몇 개의 유니크한 방법이 있는지 구하시오

이 문제는 optimization problem이며 총 몇 개의 유니크한 방법이 있는지 구한다는 것은 최대 몇 개의 유니크한 방법이 있는지를 물어보는것과 동일하기 때문이다.

그러면 어떻게 풀어야 할까?

해결법

Top-Down

n번의 스텝이 필요한 계단이다. 그리고 한 번에 한 스텝 혹은 두 스텝을 오를 수 있다. 그렇다면 n-1번째 오는 유니크한 방법들과 n-2번째 오는 유니크한 방법을 더한다면 될 것이다.

이를 점화식으로 표현해보면 f(n) = f(n-1) + f(n-2)로 표현이 가능하다.

이는 Top-Down 방식으로 구현이 가능하다. function들의 결과를 가지고 구하면 되기 때문이다.

def climb(n):
    return climb(n-1) + climb(n-2)

위의 재귀식 처럼 말이다.

하지만 이건 dp가 아니라 recursion만으로 푼 것이다. 이렇게 된다면 중복되서 호출되는 것이 많게 된다. 여기서 겹치는 subproblem들이 많다.

동일한 input에 대한 function call은 처음 한 번만 계산하고 메모한 뒤 이 결과를 재사용 하는 것이 아이디어에 시작이다.

memo = {}
def climb(n):
    if n in memo:
        return memo[n]
    if n<=2:
        return n
    memo[n] = climb(n-1) + climb(n-2)
    return climb(n-1) + climb(n-2)

memo는 저장 공간, n의 처리 결과가 있다면 바로 반환 아니면 재귀적으로 호출 한 뒤 업데이트 하는 방식이다. 이렇게 되면 중복되는 계산을 없앨 수 있다.

이 방식이 Top-Dwon방식의 DP이다.

그렇다면 바텀업은 어떻게 할까?

Bottom-Up

아래에서 차근차근 풀어나가다 보면 어느 순간 풀리게 되는 방식이다.

그렇다면 초기부터 보자. 일단 초깃값을 셋팅한다. 그리고 아까 만들었던 점화식을 for문을 통해 아래에서부터 차근 차근 넣으면 끝이다.

def climb(n):
    tabular = {1:1, 2:2}
    for i in range(3, n+1):
        tabular[i] = tabular[i-1] + tabular[i-2]
    return tabular[n]

즉 tabulation이란 작은 subproblem부터 시작해서 최종 problem 결과를 도출할 때 까지 결과를 차례대로 기록하는 것을 말한다.

이렇게 되면 기존의 시간복잡도는 O(2^n)이지만 O(n)으로 줄게된다.

Maximum Subarray

정수 배열 nums에서 가장 큰 합계를 가지는 subarray를 찾아서 그 합계를 반환 하시오. 여기서 subarray는 연속된 부분 배열을 의미하며, 적어도 하나의 숫자를 가집니다.

예시 1: nums = [-2, 1, -3, 4, -1, 2, 1, -5 ,4] -> 6
예시 2: nums = [5, 4, -1, 7, 8] -> 19

이는 먼저 가장 큰 합계를 구해야 하기 때문에 optimization problem이라고 할 수 있다.

모든 경우를 다 확인해서 찾아보는 것은 비효율적이다.

하기에 앞서 용어정리를 먼저 하자.

배열에서 max sum을 가지는 subarray를 max subarray라고 하려한다.

i번째 정수가 추가되기 전의 배열에도 max subarray가 있었을 것이다.

해결법

그러면 일단 현재까지의 최대 합인 current_total(i)와 i번째 정수까지의 배열에서 max subarray의 합계를 total_max(i)라고 하자.

점화식은 아래와 같다.

• total_max(i) = max(total_max(i-1), cur_max(i))
• cur_max(i) = max(i_num + cur_max(i-1), i_num)

이는 탑다운보다는 바텀업이 좋다.

Bottom-Up

def maxSubArray(nums):
    total_max = [nums[0]] * len(nums)
    cur_max = [nums[0]] * len(nums)
    # 초기값 셋팅 
    for i in range(1, len(nums)):
        cur_max[i] = max(nums[i] + cur_max[i-1], nums[i])
        total_max[i] = max(total_max[i-1], cur_max[i])

    return total_max[len(nums) - 1]

말 그대로 리스트로 이전의 상태값을 유지하면서 값을 구할 수 있다. 위에서 점화식을 구해놨기 떄문이다.

하지만 안에 코드를 보면 n-1번째 값만을 사용한다는 것을 알 수 있다. 따라서 아래와 같이 최적화가 가능하다.

def maxSubArray(nums):
    total_max = nums[0]
    cur_max = nums[0]
    for i in range(1, len(nums)):
        cur_max = max(nums[i] + cur_max, nums[i])
        total_max = max(total_max, cur_max)
    return total_max

그러면 언제 DP를 사용할까?

1. optimization problem이 optimal substructure여야 한다.
2. optimization problem이 overlapping subproblems을 가져야 한다.

optimal substructure

optimization problem의 optimal solution이 subproblem(s)의 optimal solution(s)을 포함하는 구조일 때를 말한다.

앞에서 본 계단문제 처럼 구하려고 하는 값이 subproblem(s)들의 optimal solution(s)을 포함해야 한다. 아래와 같이 말이다.

f(n) = f(n-1) + f(n-2)

마찬가지로 위에서 한 max subarray문제도 마찬가지다. 이전의 최적 솔루션이 필요했다.

하지만 optimal substructure가 아닌데 맞다고 판단하는 것을 주의하자. 예를 들면 a->c 의 가장 먼 경로와 같은 문제를 구하는 것이 있다.

위의 문제가 optimal substructure가 아닌 이유는 중복 방문하는 경우가 생긴다.

즉 subproblem는 독립적이여야 하고 subproblem의 solution은 다른 subproblem solution에 영향을 줘선 안된다.

overlapping subproblems

재귀적 형태의 알고리즘이 동작할 때 동일한 subproblems을 여러 번 해결해야 한다면 이 optimization problem은 overlapping subproblems을 가진다고 표현한다.

이는 다시 말해 아까처럼 재귀적으로 돌릴 때 중복되는 함수가 나오는 것을 말한다.

출처 : 쉬운코드 , https://www.youtube.com/watch?v=GtqHli8HIqk