[Python] 백준 풀기 9184 - 신나는 함수 실행

파이썬 백준 9148번

실버3

https://www.acmicpc.net/problem/9184

9184번: 신나는 함수 실행

 

 

 

문제 보기

재귀 함수를 사용하면 입력값이 같은 상황에서 반복되는 계산을 지속적으로 하기 때문에 속도가 많이 느려진다.

이를 해결하기 위해 동일한 입력값에 대한 계산의 결과는 미리 저장해 두고 필요할 때 불러와 속도를 현저히 상승시킨다.

 

 

 

문제 풀기

이전에 풀었던 24416번 (알고리즘 수업 - 피보나치 수 1) 문제를 통해 반복되는 계산 결과를 저장하여 동일한 계산을 이미 기록된 결괏값을 반환하여 빠르게 푼다는 것을 이해하였다. 이번 문제를 통해 "메모이제이션 (memoization)" 이란 단어와 함께 동적 프로그램 방법을 알 수 있었다.

 

문제에서 제시한 알고리즘은 재귀 함수의 형태이며 이대로 코드를 작성할 경우 예제 입력 "10 4 6" 까지는 결과를 반환하였지만 "50 50 50" 에서는 뻗어 버리는 결과를 가져왔다. 참고로 백준 문제들은 온라인 파이썬을 통해 해결하고 있다.

 

코드가 작동하면서 계산한 결과가 있다면 그 저장을 하기 위해 다수의 array 로 dp 를 초기화시켜주고 (a, b, c) 에 따라 각각 dp[a][b][c] 에 저장되도록 한다.

 

dp 초기화는 None 으로 하고 다중 array 는 if 조건

    if a <= 0 or b <= 0 or c <= 0
    if a > 20 or b > 20 or c > 20

에 의해 21 로 지정되었다

 

함수 fnW(a, b, c) 가 작동하는 동한 이미 계산한 값은

    if dp[a][b][c]:
        return dp[a][b][c]

로 바로 저장 및 통과시키고

 

계산된 값이 없다면

    if a < b  < c:
        dp[a][b][c] = fnW(a, b, c-1) + fnW(a, b-1, c-1) - fnW(a, b-1, c)
    else:
        dp[a][b][c] = fnW(a-1, b, c) + fnW(a-1, b-1, c) + fnW(a-1, b, c-1) - fnW(a-1, b-1, c-1)

로 계산하여 return 시킨다.

 

 

 

코드 보기

import sys
inputdata = sys.stdin.readline

def fnW (a, b, c):
    if a <= 0 or b <= 0 or c <= 0:
        return 1
    elif a > 20 or b > 20 or c > 20:
        return fnW(20, 20, 20)
        
    if dp[a][b][c]:
        return dp[a][b][c]
    
    if a < b  < c:
        dp[a][b][c] = fnW(a, b, c-1) + fnW(a, b-1, c-1) - fnW(a, b-1, c)
    else:
        dp[a][b][c] = fnW(a-1, b, c) + fnW(a-1, b-1, c) + fnW(a-1, b, c-1) - fnW(a-1, b-1, c-1)
    return dp[a][b][c]


max_dp = 21
dp = [[[None for _ in range(max_dp)] for _ in range(max_dp)] for _ in range(max_dp)]

while True:
    a, b, c = map(int, inputdata().split())
    
    if a == -1 and b == -1 and c == -1:
        break
    
    result = fnW(a, b, c)
    print(f'w({a}, {b}, {c}) = {result}')

 

 

 

추가 하기

1.

dp 가 작동하고 저장하는 모습을 보기 위해 max_dp 를 4 로 제한을 두고 입력값 (3, 3, 3) 일 때를 확인해 보았다.

(보기 편하게 줄 바꿈 및 띄어쓰기하였음.)

[
[   [None, None, None, None],   [None, None, None, None],   [None, None, None, None],   [None, None, None, None]   ], 
[   [None, None, None, None],   [None, 2, 2, 2],   [None, 2, 2, 2],   [None, 2, 2, 2]   ], 
[   [None, None, None, None],   [None, None, None, None],   [None, None, 4, 4],   [None, None, 4, 4]   ], 
[   [None, None, None, None],   [None, None, None, None],   [None, None, None, None],   [None, None, None, 8]   ]
]

 

w(3, 3, 3) = 8

 

 

2.

재귀 함수를 쓸때와 다이나믹 프로그램을 쓸때 시간적 차이.

온라인 파이썬의 특성인지 백준의 시간 계산의 특성인지 작동 시간의 차이가 커서 절대적 시간은 신뢰하지 않는다.

상대적으로 두 시간의 차이만 비례적으로 알아보았다.

(50, 50, 50) 은 재귀 함수를 사용할때 시간초과로 결과가 나오지 않아 빼고 돌림.

 

재귀함수 사용할 때, 0.134 sec

 

다이내믹 프로그램 사용할 때, 0.026 sec

 

 

 

참고 하기

메모이제이션 - 위키백과, 우리 모두의 백과사전