[이것이 취업을 위한 코딩 테스트다 with 파이썬] 6-1강(다이나믹 프로그래밍, 개미전사, 1로만들기)

다이나믹 프로그래밍(동적 계획법)

다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다.

이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다.

다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탑다운(하향식)과 보텀업(상향식))으로 구성된다.

시간복잡도를 획기적으로 줄일 수 있다!

 

프로그래밍 분야에서 동적이란 어떤 의미일까? 

자료 구조에서 동적 할당(Dynamic Allocation)은

'프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법'을 의미한다.

반면에 다이나믹 프로그래밍에서 '다이나믹'은 별다른 의미 없이 사용된 단어다.

 

다이나믹 프로그래밍은 문제가 다음의 조건을 만족할 때 사용한다.

1. 최적 부분 구조 : 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다

2. 중복되는 문제 : 동일한 작은 문제를 반복적으로 해결해야 한다.

특정 번째의 피보나치 수열을 구하고자 할 때 앞의 두 개 값을 더한 것이다.

시작항의 값을 알고 있으면 다른 값을 알 수 있다.

 

수열은 시퀀스라고 표현

f(4)피보나치 수를 알기 위해서는 f(3)과 f(2)의 값을 알고 있어야 한다.

# 피보나치 함수(Fibonacci Function)을 재귀함수로 구현
def fibo(x):
    if x == 1 or x == 2:
        return 1
    return fibo(x - 1) + fibo(x - 2)

print(fibo(4))
# 3

이처럼 피보나치 수열의 점화식을 재귀 함수를 사용해 만들 수는 있지만,

단순히 매번 계산하도록 하면 문제를 효율적으로 해결할 수 없다.

---

탑다운(하향식)방식

배열 이름을 캐싱, 메모, 테이블, DP, D라고 설정한다

# 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 리스트 초기화
d = [0] * 100 # 0부터 99까지의 인덱스를 가진다

# 피보나치 함수(Fibonacci Function)를 재귀함수로 구현 (탑다운 다이나믹 프로그래밍)
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))

# 218922995834555169026

<보텀업(상향식) : 단순히 반복문을 이용하여 소스코드를 작성하는 경우 작은 문제부터 차근차근 답을 도출한다.>

# 보텀업(반복적)
# 단순히 반복문을 이용하여 소스코드를 작성하는 경우 작은 문제부터 차근차근 답을 도출한다


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

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

# 피보나치 함수(Fibonacci Function) 반복문으로 구현(보텀업 다이나믹 프로그래밍)
for i in range(3, n + 1): # 3번째부터 n번째까지
    d[i] = d[i - 1] + d[i - 2]

print(d[n])
# 218922995834555169026

---

위의 그림을 코드로 표현한 것이다.

# 메모이제이션을 이용하는 경우 피보나치 수열 함수의 시간 복잡도는 O(N)이다

d = [0] * 100

def fibo(x):
    print('f(' + str(x) + ')', end = ' ')
    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]

fibo(6)
# f(6) f(5) f(4) f(3) f(2) f(1) f(2) f(3) f(4)

 

퀵 정렬은 정렬을 수행할 때 정렬한 리스트를 분할하며 전체적으로 정렬이 될 수 있도록 한다.

이는 분할 정복 알고리즘으로 분류된다.

 

---

개미전사

최적 부분 구조가 성립하며, 점화식을 통해 확인할 수 있다.

# 정수 N을 입력 받기
n = int(input())
# 모든 식량 정보 입력 받기
array = list(map(int, input().split()))

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100 # 식량창고의 개수 N이 최대 100까지 주어졌기 때문에 *100을 해준다.

# 다이나믹 프로그래밍(Dynamic Programming) 진행 (보텀업)
d[0] = array[0]
d[1] = max(array[0], array[1]) # 첫번째 두번째 중 더 큰 값 고르면 된다
for i in range(2, n):
    d[i] = max(d[i - 1], d[i - 2] + array[i])

# 계산된 결과 출력
print(d[n - 1])
# 8

---

1로 만들기

# 정수 X를 입력 받기
x = int(input())

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

# 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
for i in range(2, x + 1):
    # 현재의 수에서 1을 빼는 경우
    d[i] = d[i - 1] + 1
    # 현재의 수가 2로 나누어 떨어지는 경우
    if i % 2 == 0:
        d[i] = min(d[i], d[i // 2] + 1)
    # 현재의 수가 3으로 나누어 떨어지는 경우
    if i % 3 == 0:
        d[i] = min(d[i], d[i // 3] + 1)
    # 현재의 수가 5로 나누어 떨어지는 경우
    if i % 5 == 0:
        d[i] = min(d[i], d[i // 5] + 1)

print(d[x])
# 3

c++에서는 / 한번만 해도 몫이 나온다.