[알고리즘] DP (Dynamic Programming)

 

📚 DP(동적계획법)란?

 

큰 문제를 작은 문제로 나누어 푸는 것인데 이때 하나의 문제는 한 번만 풀어야 합니다.

 

동적 계획법에 대해 설명하기 딱 좋은 예시가 있는데 그것은 피보나치수열입니다.

 

 

📚 피보나치 수열이란?

 

 

 

수학에서, 피보나치 수(영어: Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. 처음 여섯 항은 각각 1, 1, 2, 3, 5, 8이다.

 

 

❓ 그러면 피보나치수열의 몇 번째 항을 바로 알 수 있는 코드를 짜려면 어떻게 해야 할까요?

 

피보나치의 규칙을 살펴보면 된다.

첫 번째와 두 번째는 무조건 1이고

다음 항부터는

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

이 반복된다.

 

우리는 이것을 재귀 함수로 쉽게 구현할 수 있다.

 

📝 피보나치 수열 코드(feat : python)

 

input = 20

# Fibo(N) = Fibo(N - 1) + Fibo(N - 2)
# Fibo(1) = Fibo(2) = 1
def fibo_recursion(n):

    if n == 1 or n == 2: return 1
    return fibo_recursion(n - 1) + fibo_recursion(n - 2)


print(fibo_recursion(input))  # 6765

 

 

그런데 문제가 하나 있다.

입력값을 20을 주면 1초안에 6765에 답을 내놓지만

입력값을 100을 주면 콘솔 창에 아무것도 안 뜨는 것을 볼 수 있다.

 

이는 동작을 안 하는 것이 아니고 무한 루프를 도는 것도 아니다.

연산량이 엄청 많아 아무리 빠른 컴퓨터라도 시간이 오래 걸려 아직 결과가 안 나온 것이다.

 

겨우 100을 넣었는데도 왜 이렇게 오래 걸리나 한 번 생각해보자

 

📖 DP의 원리

 

 

다음 사진은 피보나치의 7번째 인덱스를 구하기 위해 함수 스택을 정리한 것이다.

f(6)을 하면 재귀 함수에 의해 f(5)와 f(4)가 호출된다.

또 f(5)는 f(4)와 f(3)를 호출시킨다.

 

근데 이 사진을 보면 똑같은 연산이 많다는 것을 느껴진다.

 

f(1)을 한 번 연산하면 그 결과를 어디엔가 저장하고

그 후에는 f(1)이 호출될 때마다 연산하지 않고 그 결과를 불러와서 바로 반환할 수 없는가?

 

이럴 때 사용되는 것이 DP 동적 계획법이다.

똑같은 연산이 많으면 그것의 결과를 어디엔가 저장해서 다음 연산 때 연산을 스킵하고

그 결과를 바로 주는 것이다.

 

이러한 방법은 메모이제이션(Memoiztion)이라 하고 많은 응용 프로그램 또는 시스템, 애플리케이션에 속도를 빠르게 하기 위해 쓰인다.

 

 

그럼 아까 피보나치수열을 DP로 풀어보는 과정을 알아보자

 

📋 DP로 피보나치 수열을 푸는 과정

 

 

1. 메모용 데이터를 만든다. 처음 값인 Fibo(1), Fibo(2)는 각각 1씩 넣어서 저장한다.
2. Fibo(n) 을 구할 때 만약 메모에 그 값이 있다면 바로 반환한다.
3. Fibo(n) 을 처음 구했다면 메모에 그 값을 기록한다.

 

 

input = 100

memo = [-1] * (input+1)
memo[0] = 0
memo[1] = memo[2] = 1

# 1. 만약 메모에 있으면 그 값을 바로 반환하고
# 2. 없으면 아까 수식대로 구한다.
# 3. 그리고 그 값을 다시 메모에 기록한다.

def fibo_dynamic_programming(n, fibo_memo):

    if fibo_memo[n] != -1 : return fibo_memo[n]
    fibo_memo[n] = fibo_dynamic_programming(n - 1, fibo_memo) + fibo_dynamic_programming(n - 2, fibo_memo)
    return fibo_memo[n]


print(fibo_dynamic_programming(input, memo))
# 354224848179261915075 가 나와야 한다!

 

이 코드로 실행하면

아까 한참 오래 걸렸던 100을 다시 입력하면 바로 값이 나오는 것을 알 수 있다.

 

 

 

📝 DP관련 알고리즘 문제 풀어보기

 

 

일단 규칙을 찾아보자

 

좌석 [1] 을 옮기는 경우의 수  [1] -> 1가지
좌석 [1,2] 을 옮기는 경우의 수 [1,2], [2,1] -> 2가지
좌석 [1,2,3] 을 옮기는 경우의 수 [1,2,3], [1,3,2], [2,1,3] -> 3가지
좌석 [1,2,3,4] 을 옮기는 경우의 수 [1,2,3,4], [1,2,4,3], [2,1,3,4], [2,1,4,3], [1,3,2,4] -> 5가지
좌석 [1,2,3,4,5] 을 옮기는 경우의 수 [1,2,3,4,5], [1,2,3,5,4], [2,1,3,4,5], [2,1,3,5,4], [1,2,4,3,5], [2,1,4,3,5], [2,1,3,4,5], [1,3,2,4,5] -> 8가지

 

1 -> 2 -> (1 + 2) -> (2 + 3) -> (3 + 5) -> ...  약간 증감하는 수가 피보나치와 닮았다고 생각이 든다.

첫 번째 두 번째 항은 1,2 로 고정하고 그때부터 n항은 (n-1) + (n - 2)의 결과를 불러오면 된다

당연히 동적 계획법 방법을 써서 계산한 결과들을 저장하고 나중에 반영해야 한다

 

 

근데 이 문제에선 변수가 하나 있다.

바로 VIP 좌석이다.

VIP는 고정석이라 생각하고 나머지 일반석을 생각해서 구하면 된다.

 

예로 들면

VIP 가 4,7 이고 좌석은 총 9개 있다면

[1,2,3] 4 [5,6] 7 [8,9]

[1,2,3] 이 배치될 수 있는 경우의 수 * [5,6] 이 배치 될 수 있는 경우의 수 * [8,9] 가 배치 될 수 있는 경우의 수 =

3*2*2 = 12이다

 

 

seat_count = 9
vip_seat_array = [4, 7]
number_of_cases_where_a_person_can_sit = {
    1:1,
    2:2,
}
def Fibo(n):
    if n in number_of_cases_where_a_person_can_sit:
        return number_of_cases_where_a_person_can_sit[n]
    if len(list(filter(lambda k : k in number_of_cases_where_a_person_can_sit.keys(), [n - 1, n - 2]))) > 1:
        number_of_cases_where_a_person_can_sit[n] = number_of_cases_where_a_person_can_sit[n - 1] + number_of_cases_where_a_person_can_sit[n - 2]
    return Fibo(n - 1) + Fibo(n - 2)

def get_all_ways_of_theater_seat(total_count, fixed_seat_array):

    array = []
    result = 1
    count = 0
    for i in range (total_count):
        array.append(i + 1)

    while array:
        if array.pop(0) in fixed_seat_array:
            result *= Fibo(count)
            count = 0
        else :
            count += 1
    if count != 0:
        result *= Fibo(count)

    return result


# 12가 출력되어야 합니다!
print(get_all_ways_of_theater_seat(seat_count, vip_seat_array))