[7주차] 동적계획법

- 동적계획법: 하나의 큰 문제를 여러 개의 공통되는 작은 문제로 나누어서 작은 문제의 정답들을 결합하여 알고리즘을 푸는 과정, 다이나믹 프로그래밍(DP)라고도 함 → 규칙을 찾는 문제

 

- 점화식: 수열에서 n번째 항을 이전에 나온 항들로 나타낸 공식

 

<동적계획법 접근 방법>

- Bottom Up: 작은 문제에서 큰 문제로 반복문 호출

- Top Down: 큰 문제에서 작은 문제로 재귀 호출

 

<동적계획법 활용>

- 피보나치 수열 - Bottom Up

def fib(n):
	fibList = [1, 1]
    for i in range(2, n+1):
    	fibList.append(fibList[i-2]+fibList[i-1])
    return fibList[-1]

 

- 피보나치 수열 - Top Down

def fib(n):
	if n == 0 or n == 1:
    	return 1
    else:
    	return fib(n-1) + fib(n-2)

- 문제점: 하나의 값을 구하기 위해 많은 양의 중복되는 연산 발생

 

- 메모이제이션: 앞에서 발생한 연산의 결과를 저장해두었다가 필요할 때 불러와서 중복된 연산을 방지함(배열, 해시를 활용하는 것이 핵심)

memo = {0:1, 1:1}

def fib(n):
	if n in memo:
    	return memo[n]
    else:
    	result = fib(n-1) + fib(n-2)
        memo[n] = result
        return result

 

 - 동적계획법 예시

data = [3, 4, 5, 6, 1, 2, 5]

이웃하지 않는 숫자들의 합의 최댓값은?

def solution(data):
	if len(data) == 1:
    	return data[0]
    result = [data[0], max(data[0], data[1])
    for i in range(2, len(data)):
    	result.append(max(result[i-1], result[i-2]+data[i])
    return result[-1]