재귀는 자기 자신을 참조하거나 호출하는 것을 의미하는데, 그런 방식으로 만든 함수를 재귀함수라고 합니다.
이번에 Z 라는 문제를 재귀함수로 풀었는데, 재귀의 특징을 어떻게 이용했는지 어떻게 이 문제에 접근했는지 설명하겠습니다.
문제
한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.
N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.
다음 예는 22 × 22 크기의 배열을 방문한 순서이다.
N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.
다음은 N=3일 때의 예이다.
입력
첫째 줄에 정수 N, r, c가 주어진다.
출력
r행 c열을 몇 번째로 방문했는지 출력한다.
제한
1 ≤ N ≤ 15
0 ≤ r, c < 2N
문제풀이 과정
자 , 우리는 이제 r행 c열이 몇번째인지 찾아야한다.
그리고 시작은 0번으로 시작한다. 그럼 우리는 어떻게 몇번째있는지 찾을 수 있을까?
우선 문제에 이렇게 접근했다.
이렇게 행열이 있을 때, 우선 rc 의 위치에 접근하려고 했다.
어떻게 접근할까...고민을 많이해봤는데
자 이 정사각형은 2의 n제곱 x 2의 n 제곱으로 생성된다
예를들어 n 값이 2면
2^2 x 2^2 = 4 x 4
즉 4x4 박스가 생성된거다!
n값이 1이면
2^1 x 2^1 = 2 x 2
2x2 박스가 생성된다.
n값이 3이면
2^3 x 2^3 = 8 * 8 박스가 생성된다.
그럼 이 n 값에 따라 정확히 2의 제곱만큼 늘어나거나 줄어드는걸 확인할 수 있다.
그럼 뭘 할 수있냐!!!!!
수가 2의 제곱일 때 절반은 2^(n-1) 제곱으로 정확히 절반값을 구할수있다.
16이면 8.. 8이면 4... 4면 2.. 2면 1..
그럼 우리는 이거를 4사분면으로 나눌 수 있는거야
1사분면 2사분면 3사분면 4사분면
그렇게 위치를 찾아서 들어가다보면!!! 혹시 순서를 찾을 수 있지 않을까?
다시 이 이미지로 들어와서
이 r >= 2^(n-1) 이면서 c < 2^(n-1) 이기 때문에 1 2 3 4 로 나눴을 때 2 위치에 있는것이다.
그럼 조건을 따져볼까
if r < half and c < half: 1
elif r < half and c >= half: 2
elif r >= half and c < half: 3
elif r >= half and c >= half: 4이렇게 볼 수 있다.
여기서 큰 값 비교를 할 때 >= 연산자를 사용하는 이유는 점이 아닌 행열의 index 번호이기 때문에 >= 으로 비교를 해줘야 정확한 비교를 할 수 있다. 만약 >= 이 아니라 > 로 하면 안된다.
근데 여기서 막혔다.
아니 그래 행열 [ r, c ] 의 위치에 따라서 사분면을 나눈건 알겠어.
그래서 이걸로 순서를 어떻게 구하는데???? 재귀함수에 인자를 어떻게 넣어줘야하는데?
진짜 모르겠어서 챗지피티를 돌려봤다.
def solution():
n, r, c = map(int, input().split())
def z(n, r, c):
if n == 0:
return 0
half = 2**(n-1)
if r < half and c < half:
return z(n-1, r, c)
elif r < half and c >= half:
return half*half + z(n-1, r, c-half)
elif r >= half and c < half:
return 2*half*half + z(n-1, r-half, c)
else:
return 3*half*half + z(n-1, r-half, c-half)
print(z(n, r, c))
solution()우선 1 2 3 4 분면을 찾아서 나누는 것까진 동일했다.
이 코드가 왜 이렇게 되는지 설명하겠다.
-
모든 사분면 공통
--> 재귀호출에 n-1 을 넣어준다. 사각형의 크기를 절반으로 줄이는것 -
1사분면인 경우
--> 특별한 처리가 없다. 왜냐하면 제1사분면에 있기 때문에 사각형으로 줄일 필요가 없다.
-
2사분면인 경우
--> 인자에 half x half 을 더해주고 c - half 한 값을 넣어준다.
-
3사분면인 경우
--> 인자에 2 x half x half 를 더 해주고 r - half 한 값을 넣어준다.
- 4사분면인 경우
--> 인자에 3 x half x half 를 더 해주고 c - half , r - half 한 값을 넣어준다.
여기서 half 는 절반이다.
정사각형의 크기가 2^n x 2^n 일 때 절반은 2^(n-1) 인건 알거다.
왜 half x half + z(n,r,c-half)가 존재하는 걸까?
우린 이게 재귀함수란 것을 기억해야한다.
이 네모를 가장 작게 쪼개면 어떻게될까?
최종적으로 가장 작은 사분면을 판별할 수 있는 지점은 n 이 1인 지점일 것이다.
n = 1 일 때,
half = 2^(n-1) = 1
이 half * half 는 뭐냐면 넓이다. 4분면으로 나눴을 때 각 사분면이 가지는 넓이다. 그리고 이게 순서다.
지금 r,c 의 위치가
- 4분면에 있다는 것은 1,2,3 분면을 지나왔다는 것이다.
- 3분면에 있다는 것은 1,2 분면을 지나왔다는 것이다.
- 2분면에 있다는 것은 1분면을 지나왔다는 것이다.
- 1분면에 있다는 것은 지나온 구간이 없다는 것이다.
그래서 half 를 하나 빼준다는건 사분면을 하나 뺀다는것이라서
나중에 뺀 half 를 돌려주면서 순서를 더해주는 것이다.
뭔 소린지 모르겠다고?
사실 나도 더 명확하게 설명하고 싶지만 이게 내 한계다..
일단 가장 중요한 개념은
- 4분면으로 나눠서 계산해야 한다는것.
- 4분면의 넓이가 곧 순서라는 것.
- 뺀 half 만큼이 순서에 더해져야 한다는 것이다.
그래도 최대한 이해할수있게 그림을 만들어서 덧붙였는데 이해가 되었으면 좋겠다.
이해가 안되는데 알고싶다면 개인적으로 연락주시면 제가 직접 만나서 설명하겠다.
