새싹프로그래머의 이야기

백준 알고리즘 10026번을 풀던 와중, 채점 과정에서 런타임 에서(RecursionError)가 발생했습니다.

발생한 이유를 알아보니 다음과 같습니다.

-파이썬에서 정한 최대 재귀 깊이보다 재귀가 너무 많이 발생할 경우.

즉, 설정된 값보다 재귀가 많이 발생할 경우 RecursionError가 발생함을 알게되었습니다.

해결 방법은 다음과 같습니다.

- 재귀를 사용하지 않는 방식으로 코드 구현하기. (재귀를 활용한 코드를 반복문을 통한 코드로 변경)

- 파이썬 sys 모듈에 있는 sys.setrecursionlimit()을 이용하여 최대 재귀 깊이를 변경해주기

sys.setrecursionlimit(10000)

해당 문제에서 나올 수 있는 최대 깊이인 10000으로 값을 설정해주어 문제를 해결하였습니다.

*재귀함수의 경우 코드를 효율적으로 짤 수 있다는 장점이 있지만 반대로 함수에서 함수를 호출하는(자신을 재참조) 방식이기 때문에 메모리를 많이 잡아먹고 함수가 return 될 경우 메모리상에서 이전 함수 위치로 이동하기 때문에 반복문보다 시간이 오래걸릴 수 있습니다.

장점과 단점이 공존하는 만큼, 무조건적인 재귀의 활용보다는 재귀의 특성을 바탕으로 상황에 맞춰 적절히 활용하면 더욱 좋은 코드가 나오지 않을까 생각합니다.

읽어주셔서 감사합니다.

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

문제: 해당 그림과 같이 정삼각형의 변의 길이가 구성될 때, 입력된 N의 값에 따라 파도반 수열에 따른 P(N) 값을 구하는 문제

풀이 방법: 다이나믹 프로그래밍

풀이 설명:

주어진 수열은 다음과 같습니다.

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

이 수열을 봤을 때, P(i) = P(i-2) + P(i-3) (i >= 4)인 규칙을 발견할 수 있었습니다.

이를 바탕으로 다이나믹 프로그래밍을 통해 문제를 풀었습니다.

풀이 코드:

import sys

t = int(sys.stdin.readline())

p = [0,1,1,1] + [0] * 97

for _ in range(t):
    n = int(sys.stdin.readline())
    if n > 3:
        for i in range(3,n+1):
            p[i] = p[i-3] + p[i-2]
    print(p[n])

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

문제: 최대 힙을 통해서 입력된 값이 0일 경우에는 힙 안의 최대 값을 출력한 후 해당 값을 제거, 자연수일 경우 배열에 자연수를 넣는 연산을 수행하는 프로그램 작성하기

풀이 방법: 최소 힙인 heapq을 priority를 설정하여 최대 힙처럼 활용하기

풀이 설명:

최소 힙인 heapq를 활용하는데, 값의 입력을 (priority(-value),value) 형태로 입력하여 최대 힙으로 활용하여 문제를 해결하였다.

풀어서 설명하자면,

heapq.heappush(1)

heapq.heappush(2) 를 수행하게 되면, heapq는 [1,2]가 되어

heapq.heappop(heap)을 수행하면 1,2 순서대로 나오게 된다.

하지만 push 할 때, (-1,1) ,(-2,2) 형태로 입력하고자하는 value의 음수 값을 priority 역할로 값을 넣어 입력하게되면 

heapq는  [(-2,2),(-1,1)] 된다. 

여기서, heapq.heappop(heap)을 수행하게 되면 최대 값을 가지고 있는 (-2,2) 부터 나오게 된다.

이 원리를 통해 pop을 수행할 경우 최대 값을 담은 요소부터 나오게 되는 최대 힙을 만들어 활용하였다.

풀이 코드:

import sys
import heapq

n = int(sys.stdin.readline())
heap =[]
for _ in range(n):
    val = int(sys.stdin.readline())
    if(val == 0):
        if(len(heap) == 0):
            print(0)
        else:
            print(heapq.heappop(heap)[1])
    else:
        heapq.heappush(heap,(-val,val))

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

문제: 주어진 숫자 n을 1,2,3의 숫자 합으로 나타내는 방법의 수 출력하기

풀이방법: 동적 계획법

풀이 설명: 

각 케이스 별로 봤을 때,

<n == 1> -> 1

(1)

<n==2> -> 2

(1,1) (2)

<n==3> -> 4

(1,1,1) (1,2) (2,1) (3)

<n==4> ->  7

(1,1,1,1) (1,1,2) (1,2,1) (2,1,1) (2,2) (1,3) (3,1)

각 케이스별로 나오는 결과 값을 봤을 때, f(n) = f(n-3) + f(n-2) + f(n-1) (n >= 4) 가 성립하는 것을 찾을 수 있었습니다.

이에, 동적 프로그래밍을 통해 코드를 구현하였습니다.

풀이 코드:

import sys

n = int(sys.stdin.readline())
array = []

for _ in range(n):
    array.append(int(sys.stdin.readline()))

dp = [1,2,4]

for i in range(3,max(array)):
    dp.append(sum(dp[i-3:i]))

for i in array:
    print(dp[i-1])

<초기 코드>

처음에는 문제에서 주어진대로 풀어보려고 했습니다.

문제 설명에서 나오는 숫자들이 순열과 일치한다고 생각하여 순열로 문제를 풀어보고자 하였습니다.

주어진 숫자로 만들 수 있는 1,2,3의 조합을 구하고, 이를 itertools의 permuations를 통해 나오는 결과 값의 갯수를 세면 정답을 구할 수 있을거라고 생각했습니다.(이때, permutation함수는 (1,1,2)의 각 1을 다른 개체로 보기 때문에 중간에 set 함수를 통해 결과 값에서 중복된 값을 제거해주었습니다.)

정답인 값들은 구할 수 있었지만 연산이 너무 많이 필요해서 시간초과가 발생하였습니다.

이에 , 다른 규칙을 찾고자 했고 위의 점화식으로 표현되는 규칙을 찾을 수 있어 '다이나믹 프로그래밍'으로 문제를 해결하였습니다

import sys

import itertools

n = int(sys.stdin.readline())

array = []

for _ in range(n):
    array.append(int(sys.stdin.readline()))

for i in range(n):

    cnt = 0

    num = array[i]

    for a in range(num, -1, -1):

        for b in range((num - a) // 2, -1, -1):

            for c in range((num - a - 2 * b) // 3, -1, -1):

                numArray = []

                numArray.append(['1'] * a)

                numArray.append(['2'] * b)

                numArray.append(['3'] * c)

                numArray = list(itertools.chain.from_iterable(numArray))

                if (1 * a + 2 * b + 3 * c == num):
                    cnt += len(list(set(list(itertools.permutations(numArray, a + b + c)))))

    print(cnt)