재귀 파이썬 문제 종이자르기 프로그래머스 코딩테스트 (5)

목차

서론

지난번엔 BFS에 대해서 알아보았다. DFS도 알아보아야 하지만.. 다음주에 문제 풀고 DFS할 예정임. 아무튼 오늘은 재귀에 대해서 알아본 뒤, 직접 문제를 몇개 더 풀어보고자 한다. 사실 재귀보단, DP가 더 자주 출제된다. 하지만 DP를 하기 위해서는 재귀를 충분히 알아야 된다고 한다. 그래서 재귀를 몇문제 더 풀어보고 다음주에 DP로 넘어갈것임.

---

간단한 재귀 이론

영상에서 본 재귀 이론을 간단하게 언급하고자 한다. 재귀와 반복문은 서로 왔다갔다할 수 있다고 한다. 다만 재귀는 보긴 좋지만 소모하는 시간이 많으므로 애지간하면 반복문에서 해결하라고 한다. 자신을 여러번 호출하는데 이게 굉장히 비효율적이기 때문이다. 이후 DP에서 해소할 수 있는 무언가를 하는데 이건 재귀에 익숙해진 뒤 들어가는게 맞다고 한다. + 재귀는 자기자신을 호출하며 종료하면 안된다. 때문에 베이스 컨디션을 항상 만들어야 한다. 베이스 컨디션이라하면 n=1이나 n=0같은 종료시점을 나타내는 컨디션이다. 문제가 귀납법적으로 해결이 가능해 보이면 재귀와 DP를 고려해보자! 

---

내 풀이(재귀 이용X)

프로그래머스 재귀를 서치하니 바로 나왔던 문제이다. 종이자르기 문제.레벨은 0인가 1에 속하는 하꼬 문제로, 나에게 딱 맞는 문제다 이걸 재귀로 풀 생각을 해봐야 겠다. 일단 재귀인걸 알고 들어갔음에도 난 아래와 같이 풀었다. 신기하게 저 식을 풀어 쓴 MN-1은 런타임 에러가 난다. 너무 간단해서 벌거벗겨진 기분이다.

 

def solution(M, N):
    answer = (M-1)*(N)+(N-1)
    return answer

 

 

 

 

내 풀이(재귀 이용)

재귀 풀이가 목표인 만큼 재귀로 함 풀어보고자 한다. 재귀적 사고라하면 바킹독 선생님께서는 귀납법적 사고라고 하였다. 그리고 그림을 그려보니 가로 세로 한 칸 씩 추가할 때마다 이전 것에서 {(1) + (M-1) + (N-1)} 이렇게 추가가 됐고(바로 이해가 안가면 그림을 그려보는걸 추천), 나는 이걸 M+N-1로 풀어서 리턴했다. 마지막으로 base condition을 저 두 값 중 작은 게 1을 만났을 때로 했다. 매번 min,max 값을 정의하는게 맞는지 싶지만 아무튼 밑에 있는 코드로 잘 돌아갔다.

 

def solution(M, N):
    if min(M,N) == 1:
        return max(M,N)-1
    return solution(M-1,N-1)+M+N-1

---

다른 사람 풀이(재귀 이용)

다른 사람의 코드도 찾아보았다. 종이에 가위질 한 번 할 때마다 잘린 종이에 1+A+B가 된다고 가정하고 A따로 B따로 구해서 리턴했다고 한다. 베이스 컨디션은 나와 똑같았다. 세로가 그대로라는 전제 하에 종이 조각 A는 M이 M - 1이 되고 나머지 종이 조각 B의 M은 위에서 자르고 남은 M - 1 만큼 자른 값이 된다고 한다.

def solution(M, N):
    M, N = min(M, N), max(M, N)
    if M == 1:
        return N-1
    return 1+solution(M-1, N)+solution(M-(M-1), N)

---

끝으로

재귀에 대해서 알아봤는데 꽤~힘든거 같다. DP가 목적인데 어째 여기서 고통 받는듯. 여기서 고통받다보면 DP는 좀 쉬울까도 싶다. 재귀 너무 머리아파요. 참고로 지난 BFS 포스팅을 보려면 여기로 가면 되겠다. 다음 포스팅에서는 여전히 재귀에 대한 문제를 풀어볼것임.