이 포스팅에서는 문제를 풀 때 알아본 파이썬의 꼬리재귀를 정리해두었다.

1074 Z

문제 링크

3개 째 풀고 있는 분할정복 문제라서 간단할 줄 알았다.

처음에 생각했던 로직대로

1. 전체 판에서 4분할 중 어디에 속하는지 알아내기
2. 해당 분할에 맞게 znum 더해줌
3. 해당 분할 (작은 칸)으로 재귀

이 방법이 맞았지만, 세부사항에서 오래 애를 먹었다. 이런 작은 것에 막힐 땐 정말 답답하다 -_-

아래는 정답 코드

# 1074 Z

rst = 0

def getZNum(N, r, c, znum):
    offset = 2**(N-1)
    # print("offset, znum", offset, znum)
    # print("r c", r, c)
    if offset == 1:
        if r<1 and c==1:
            znum += 1
        elif r==1 and c<1:
            znum += 2
        elif r==1 and c==1:
            znum += 3
        global rst
        rst = znum
        return

    if r<offset and c<offset:
        getZNum(N-1, r, c, znum)
    elif r<offset and c>=offset:
        znum += offset**2
        getZNum(N-1, r, c-offset, znum)
    elif r>=offset and c<offset:
        znum += 2 * offset**2
        getZNum(N-1, r-offset, c, znum)
    else:
        znum += 3 * offset**2
        getZNum(N-1, r-offset, c-offset, znum)
    

# main

N, r, c = map(int, input().split())
getZNum(N, r, c, 0)
print(rst)

• 4분할 시, 범위는 어떻게 되는가?

  • 처음엔 offset보다 클 때, 작을 때로 구분하여 생각했으나, 이렇게 하면 offset과 같을 때에는 적용되지 않는다.
  • 부등호를 쓸 때 놓치는 게 없는지 확인한다.

• 파이썬의 꼬리재귀 문제, 재귀 None 문제

  • 원래 return 부분 코드는 아래와 같았다.

    return znum

    이렇게 하니 함수의 리턴값이 None이라고 출력된다. 그래서 전역변수의 값을 수정하는 방법으로 바꿨다.

  • depth가 쌓이면서 이어지는 재귀를 꼬리 재귀라고 하는데, 몇 언어에서는 컴파일러 단계에서 꼬리 재귀를 최적화해준다. n-1단계의 함수를를 호출하면서, n단계의 함수를 스택에서 정리해준다는 뜻이다.

  • 파이썬에서는 꼬리 재귀 최적화를 지원하지 않기 때문에, 스택이 계속 쌓인다. 메모리를 차지하기 때문에 (기본값) 재귀도 depth 999까지만 가능하다.

  • 마찬가지로, 가장 안쪽의 재귀에서 znum의 값을 리턴하여도, 그 바깥의 함수에서 리턴되는 None 값이 overwrite 되어서 결국엔 None값이 getZNum의 리턴값이 된다.

• offset = 1인 상태

  if offset == 1:
          if r<1 and c==1:
              znum += 1
          elif r==1 and c<1:
              znum += 2
          elif r==1 and c==1:
              znum += 3

  • 이 부분에서 offset이 1이기 때문에, offset과 비교하는 대신 1과 비교해주었다.
  • 이 시점에서 r이나 c가 가질 수 있는 값은 0 아니면 1이다.