[파이썬/백준] 9184번 : 신나는 함수 실행

9184번 : 신나는 함수 실행

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

 

 

문제 설명

 

 

 

재귀 문제로 시간이 너무 오래 걸리는 것을 해결해야 한다. 

메모이제이션을 통해 해결해야 하므로 간단히 개념을 살펴보자. (아래 글을 바탕으로 작성하였습니다.)

메모이제이션(Memoization) 개념 및 예시, 재귀(recursion)

 

 

메모이제이션(memoization)은 dp(dynamic programming, 동적 프로그래밍) 알고리즘에서 핵심이 되는 기술로 중복 계산을 제거함으로써 프로그램의 전체적인 실행 속도를 빠르게, 성능을 향상할 수 있는 기법이다.

컴퓨터 프로그램이 동일한 계산을 반복적으로 해야할 때, 이전에 계산한 값을 메모리에 저장하여 중복적인 계산을 제거하여 전체적인 실행 속도를 빠르게 해주는 기법이다.

 

>> dp 관련 글 (바텀업)

2024.09.16 - [SWLUG/파이썬 (코딩테스트)] - [파이썬/백준] 1932번 정수 삼각형

 

 

재귀 함수의 대표적인 예제인 피보나치 수열 알고리즘을 예시로 메모이제이션을 쉽게 이해할 수 있다.
피보나치 수열은 첫째 및 둘째 항이 1이고, 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다.
-> 피보나치 수를 구하는 '재귀 함수' 알고리즘의 문제점은 엄청난 중복 호출이 발생한다는 점이다.
이는 fibo(n)의 값을 계산하고 저장해 놓으면 다음 계산에서 필요할 때 답만 가져와 사용하면 된다.

재귀 함수 사용

def fibo(n):
    if n<2:
        return n
    else:
        return fibo(n-1) + fibo(n-2)

 

 

메모이제이션 기법 사용

def fibo_memo(n):
    global memo            
    if n >= len(memo):
        memo.append(fibo_memo(n-1) + fibo_memo(n-2))
    return memo[n]
memo = [0, 1]

 

memo라는 리스트를 전역 변수로 사용하여, 함수 내부에서도 접근하고 값을 추가할 수 있게 한다.

memo 리스트는 이미 계산된 피보나치 수를 저장하는 리스트로, 길이는 현재까지 계산된 피보나치 수의 개수를 의미한다.

 

---

 

문제 분석

 

if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns:
    1

if a > 20 or b > 20 or c > 20, then w(a, b, c) returns:
    w(20, 20, 20)

if a < b and b < c, then w(a, b, c) returns:
    w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)

otherwise it returns:
    w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)

 

위의 코드에서 중복 문제를 해결하기 위해 메모이제이션 기법을 사용하도록 한다.

3차원 dp리스트를 만들어서 이미 계산한 문제는 다시 계산하는 것이 아닌, 값을 찾아서 리턴하도록 한다.

0부터 20까지로 dp 리스트의 범위를 제한해주고 모두 0으로 초기화한다.

 

무한루프를 사용하여 사용자에게 입력받고, 모두 -1일 경우 종료해준다.

그렇지 않을 경우, w(a, b, c)의 값을 계산한 후, 'w(a, b, c) = 결과' 형식으로 출력해준다.

 

 

최종 코드

import sys
input = sys.stdin.readline

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

dp = [[[0]*(21) for _ in range(21)] for _ in range(21)]

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

 

 

 

출력 코드에서 f-string(포매팅 문자열)을 사용하여 변수들의 값을 포함하여 출력하고 있다.

f-string은 파이썬 3.6부터 지원되는 문자열 포매팅 방법이다.

문자열 앞에 f를 붙이고, 그 안에 중괄호 {}를 사용하여 변수나 표현식의 결과를 삽입할 수 있다.

f"텍스트 {변수}"