2학년 2학기 알고리즘 과제_1주차(백준_9184번:신나는 함수 실행)

1주차 과제 

 

문제

재귀 호출만 생각하면 신이 난다! 아닌가요?

다음과 같은 재귀함수 w(a, b, c)가 있다.

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)

 

위의 함수를 구현하는 것은 매우 쉽다. 하지만, 그대로 구현하면 값을 구하는데 매우 오랜 시간이 걸린다. (예를 들면, a=15, b=15, c=15)

a, b, c가 주어졌을 때, w(a, b, c)를 출력하는 프로그램을 작성하시오.

입력

입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다.

출력

입력으로 주어진 각각의 a, b, c에 대해서, w(a, b, c)를 출력한다.

 

 

📌 내 생각(풀이)

 

 

오랜만에 알고리즘을 풀어서 그런지 어떤식으로 풀어야할 지 감이오지 않았다.

일단 주어진 코드 자체를 분석해보면, 만약 a가 0이거나 음수이거나 b가 0이거나 음수이거나, c가0이거나 음수인, 셋 중 하나가 해당 경우에 속할 때  1을 반환하고, 

만약 a,b,c 중 하나라도 20이상이면 w(20,20,20)을 반환한다.

 

만약 a보다 b가 작고, b가 c보다 작은 둘다의 경우에 속할 경우, 

    w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, 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)

 

반환한다.

 

코드는 무슨 소리인지 이해가 가는데, 해당 문제를 제대로 이해하지 못한거 같다.

그래서 코드와 관련된 힌트를 얻고자 찾아보았다.

 

📌 코드 및 코드해석

  

def w(a, b, c):
    # a, b, c 중 하나라도 0 이하일 경우 1 반환하기
    if a <= 0 or b <= 0 or c <= 0:
        return 1
    
    # a, b, c 중 하나라도 20 초과일 경우 w(20, 20, 20) 호출하기
    if a > 20 or b > 20 or c > 20:
        return w(20, 20, 20)
    
    # 이미 계산된 값이 있을 경우에는 그 값을 반환하기
    if array[a][b][c]:
        return array[a][b][c]
    
    # a < b < c일 경우
    if a < b < c:
        array[a][b][c] = (w(a, b, c-1) +
                          w(a, b-1, c-1) -
                          w(a, b-1, c))
        return array[a][b][c]
    
    # a, b, c 가 모두 양수일 경우
    array[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 array[a][b][c]

# 21x21x21 크기의 3차원 리스트 초기화하기
array = [[[0 for _ in range(21)] for _ in range(21)] for _ in range(21)]

while True:
    # 사용자로부터 a, b, c 입력 
    a, b, c = map(int, input().split())
    
    # 입력이 -1 -1 -1인 경우 종료하기
    if a == -1 and b == -1 and c == -1:
        break
    
    # 계산된 값 출력
    print(f'w({a}, {b}, {c}) = {w(a, b, c)}')

 

 

이 코드는 세 개의 정수 a, b, c를 입력 받아 특정 조건에 따라 값을 계산하는 함수 w를 정의하고 있다.

이 함수는 주로 동적 프로그래밍(Dynamic Programming) 기법을 사용하여 재귀적으로 호출되는데, 여기서는 함수의 작동 방식을 단계별로 확인해야한다.

 

 

기본 조건을  처리하는 과정

• a, b, 또는 c가 0 이하인 경우에는 1을 반환한다.
• a, b, 또는 c가 20을 초과하는 경우에는 w(20, 20, 20)을 호출하여 상한값을 설정한다.

 

메모이제이션(Memoization):

• 만약 array[a][b][c]가 이미 계산되어 있으면 그 값을 반환하는데, 이를 통해 중복 계산을 피할 수 있다.

 

조건에 따라 나누기

• a < b < c인 경우, 함수는 아래와 같은 수식으로 값을 계산한다.  

w(a, b, c) = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)

 

• 그렇지 않으면, 아래의 수식으로 값을 계산한다.

w(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)

 

 

결과 저장하기

• 계산한 값을 array[a][b][c]에 저장하고 반환한다.

 

초기화 ,사용자 입력 받기

• array는 21x21x21 크기의 3차원 리스트로 초기화되어, w(a, b, c)의 값을 저장하는 데 사용됩니다.
• while 루프는 사용자로부터 입력을 계속 받아 처리하며, 입력이 -1 -1 -1인 경우에 종료됩니다.

 

이 코드는 주어진 세 개의 정수에 대해 특정 재귀적 관계를 통해 결과를 계산하는 함수를 구현하고, 메모이제이션을 통해 성능을 최적화한 문제이다.

 

 

 

재귀호출은 늘 뭔가 까다로운 것 같다.

또 문제를 오랜만에 풀어서 그런건지 감이 잘 잡히지 않았다.

해당 내용을 이해하고자 다른 자료들을 찾아보고 구글링도 시도했다.

일단 해당내용에 관해 이해를 위한 추가 공부를 더 해야할 것 같다.

1주차 첫 알고리즘 과제 끝!

 

 

[참고 자료]

https://velog.io/@noion0511/%EC%8B%A0%EB%82%98%EB%8A%94-%ED%95%A8%EC%88%98-%EC%8B%A4%ED%96%899184

[Python/Kotlin] 백준 9184번 : 신나는 함수 실행