백준 1074 : Z

문제링크

접근

재귀

• 재귀라고 써있기도 하고, 구조 자체가 큰 Z 안에 작은 Z가 들어가서 재귀로 접근하기로 함
• 색종이 자르기 등 다른 재귀와 유사함
• 재귀 함수 인자로 범위를 나타내는 인자를 주고, 안쪽 재귀에서는 범위를 줄여가면 될 듯
• 베이스 케이스는 범위가 좁아져서 최종 1일 때
  • 범위는 가로, 세로가 같이 줄어드므로 둘 중에 하나만 검사하면 됨

수학적 계산

• R,C가 있는 위치를 기준으로 앞쪽의 구역의 숫자 배치는 상관이 없고 맨 오른쪽 아래 귀퉁이 숫자만 중요함
• 각 범위별로 시작하는 숫자도 정해져 있음
• 결국에는 재귀적으로 범위를 줄여나가는 것이 편함

트라이

1. 재귀, 시뮬레이션

N,R,C = map(int, input().split())

M = [[0]*(2**N) for _ in range(2**N)]

k=0
def recur(a,b,c,d):

    if(a==b): #
        global k
        M[c][a]=k
        k+=1
        return
    coHalf = (a+b)//2
    roHalf = (c+d)//2
    recur(a,coHalf,c,roHalf)
    recur(coHalf+1,b,c,roHalf)
    recur(a,coHalf,roHalf+1,d)
    recur(coHalf+1,b,roHalf+1,d)

recur(0,(2**N)-1,0,(2**N)-1)
print(M[R][C])

• 실제 Z를 돌면서 Matrix에 숫자를 기록

메모리 초과

• matrix의 용량은 int형의 사이즈 * 가로 * 세로 = 4 * 2^15 *2^15 = 4,294,967,296 = 4GB가 나옴

2. 재귀만 하면서 숫자를 기록

N,R,C = map(int, input().split())

k=0
def recur(a,b,c,d):
    global k
    if(a==b):
        if(a==C and c==R):
            print(k)
            return
        k+=1
        return
    coHalf = (a+b)//2
    roHalf = (c+d)//2

    recur(a,coHalf,c,roHalf)
    recur(coHalf+1,b,c,roHalf)
    recur(a,coHalf,roHalf+1,d)
    recur(coHalf+1,b,roHalf+1,d)

recur(0,(2**N)-1,0,(2**N)-1)

• 직접 기록하지 않고 k로 현재 기록하는 추적함.
  • k가 유지되야하기 때문에 포인터로 함수 안쪽에서도 갱신해야하는데, 파이썬에서는 지원하지 않으므로 global 키워드를 이용하여 접근

시간 초과

• 범위는 절약됐지만, 여전히 모든 범위를 돌고 있어서 시간 복잡도가 높음
  • 2^15*2^15 = 1,073,741,824 → 10억
  • 1억에 1초라고 생각해도 10초 이상 걸림

3.재귀, 숫자기록, 수학적 계산 (정답)

N,R,C = map(int, input().split())

k=0
def recur(a,b,c,d):
    global k
    if(a==b):
        if(a==C and c==R):
            print(k)
            return
        k+=1
        return
    if(not (a<=C<=b and c<=R<=d)): # 범위 계산 추가
        k+=(b-a+1)**2
        return
    coHalf = (a+b)//2
    roHalf = (c+d)//2

    recur(a,coHalf,c,roHalf)
    recur(coHalf+1,b,c,roHalf)
    recur(a,coHalf,roHalf+1,d)
    recur(coHalf+1,b,roHalf+1,d)

recur(0,(2**N)-1,0,(2**N)-1)

• 현재 검사하지 않는 범위의 값은 순서가 중요하지 않음. 또 미리 계산이 가능함
• 재귀를 들어가서 해당 범위에 R,C가 포함되지 않으면 모든 범위를 다돌지 않고 마지막 값만 계산
• 예상 시간 복잡도 계산
  • 2^N이 반절로 줄어들면서 N이 0이 될때까지 반복함
  • 각 단계별로 R,C가 들어있지 않은 나머지 범위는 상수시간으로 해결됨
  • 시간복잡도 O(N) 으로 예상
    • 1억번 연산에 1초가 걸린다 했을 때
    • N이 15까지이므로 15/100000000 = 0.00015밀리초 = 150나노초
    • 오버헤드에 영향을 받는 정도 - 백준 결과 44ms

더 깔끔한 코드

N,R,C = map(int, input().split())

k=0
def recur(a,c,n):
    global k
    if(n==0):
        if(a==C and c==R):
            print(k)
            return
        k+=1
        return
    rng = 2**n
    half = rng//2
    if(not (a<=C<a+rng and c<=R<c+rng)):
        k+=rng*rng
        return
    recur(a,c,n-1)
    recur(a+half,c,n-1)
    recur(a,c+half,n-1)
    recur(a+half,c+half,n-1)

recur(0,0,N)

• 기존 코드는 범위의 끝지점도 인자로 지정해주었는데, 현재 몇단계(N)를 확인하고 있는지에 따라 범위가 정해지므로, 범위의 끝부분을 시작지점과 단계를 통해 함수 내부에서 계산할 수 있다.
• 따라서 인자에, 가로.세로의 시작과 단계만 넘겨서 다시 작성하였다.

반복문

• 모든 재귀는 반복문으로 변환할 수 있다.

1. while문을 돌면서, 네개의 범위별로 R,C가 들어있는지 체크
2. R,C가 들어있는 범위라면 해당 범위의 시작 숫자를 수학적으로 계산해서 k에 추가

• 좀 더 코드를 짜기 쉽게 하려면, 범위가 꼭 전체 매트릭스에 대한 상대적 위치가 될 필요는 없다는 점에 착안해서, while문으로 다시 돌아가기 전에 R,C 값을 조정해 다음 반복의 범위의 0,0에서 재검사를 하는 것처럼 코드를 작성할 수 있다.