[백준] z
분할정복
재귀
백준
medium
문제
한수는 2차원 배열 (항상 2^N * 2^N 크기이다)을 Z모양으로 탐색하려고 한다. 예를 들어, 2*2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.
N이 주어졌을 때, (r, c)를 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 N r c가 주어진다. N은 15보다 작거나 같은 자연수이고, r과 c는 0보다 크거나 같고, 2^N-1보다 작거나 같은 정수이다
2 3 1
출력
첫째 줄에 문제의 정답을 출력한다.
11
분할정복
문제를 잘 읽어보면, 2*2 배열이 아닌경우 2^(N-1) 로 나눈 다음에 재귀적으로 방문한다. 라고 명시되어 있다.
여기서 힌트를 얻어, 총 N*N 배열에서 2*2가 될때까지, 2^(N-1)로 계속 나눠야 한다는 것을 알 수 있다.
분할정복이란
문제를 작은 N개의 문제로 분리하고, 각각 해결하면서 원래의 문제를 해결하는 전략으로 일반적으로 재귀함수로 구현한다. Memorization 기법을 사용하지 않는다.
def split(n, x, y):
global result
if n == 2: # 2*2 배열이 될 때만, 체크한다.
# (r,c) 좌표를 방문하면 끝
# 좌우상하 재귀호출
split(n/2, x, y)
split(n/2, x, y + n/2)
split(n/2, x + n/2, y)
split(n/2, x + n/2, y+ n/2)
split(2 ** N, 0, 0)
개선된 코드
위처럼 구현하면 백준사이트에서 시간초과가 뜬다.
왜냐하면, 찾고자하는 좌표 (r,c) 를 만날때까지, 모두 방문하기 때문이다.
- 1/2로 왼쪽상단 부터 계속 쪼개고, 좌표를 만날때까지 루프를 돈다.
- 왼쪽상단 재귀가 모두 끝나면 오른쪽 상단 재귀를 시작한다.
이렇게 하면, 최악의경우=좌표가 맨 오른쪽하단에 있는 경우 불필요한 루프와 재귀가 수행되는 것이다.
사이트에 보면 여러가지 개선포인트가 있는데, 나는 무엇보다도 재귀를 호출하는게 heavy하다 생각했다. 따라서 찾고자 하는 좌표가 split 후의 영역에 좌표값이 있는지 확인을 먼저하고, 재귀호출을 하는 방법으로 개선했다.
pivot = int(n/2)
if r < x+pivot and c < y+pivot:
split(pivot, x, y)
else:
result += pivot ** 2
if r < x+pivot and (c > y+pivot or c == y+pivot):
split(pivot, x, y + pivot)
else:
result += pivot ** 2
if (r > x+pivot or r == x+pivot) and c < y+pivot:
split(pivot, x + pivot, y)
else:
result += pivot ** 2
if (r > x+pivot or r == x+pivot) and (c > y+pivot or c == y+pivot):
split(pivot, x + pivot, y + pivot)
else:
result += pivot ** 2