분할정복

문제를 읽고 이해하기 한수는 2차원 배열 (항상 2^N * 2^N 크기이다)을 Z모양으로 탐색하려고 한다. 예를 들어, 2*2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, 2차원 배열의 크기가 2^N * 2^N라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 4등분 한 후에 (크기가 같은 2^(N-1)로) 재귀적으로 순서대로 방문한다. 다음 예는 2^2 * 2^2 크기의 배열을 방문한 순서이다. N이 주어졌을 때, (r, c)를 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오. 다음 그림은 N=3일 때의 예이다. 입력 첫째 줄에 N r c가 주어진다. N은 15보다 작거나 같은 자연수이고, r과 c는 0보다 크거나 같고, 2^N-1보다 작거나 같..

문제를 읽고 이해하기 흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다. 주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다 위 그림에서 왼쪽의 영상은 오른쪽의 배열과 같이 숫자로 주어지..

분할 정복이란? 분할 정복(Divide and Conquer)이란 알고리즘 디자인 패러다임 중 하나로, 주어진 문제를 둘 이상의 부분 문제로 나눈 후, 각 문제에 대한 답을 재귀를 통해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산해내는 알고리즘입니다. 일반적인 재귀와 다른 점 분할 정복은 일반적인 재귀와 다르게 부분 문제를 나눌 때 '거의 같은 크기의 부분 문제'로 나눈다는 점입니다. 반면에 일반적인 재귀는 하나의 조각과 나머지 전체로 나눕니다. 분할 정복의 구성 요소 - 문제를 더 작은 문제로 분할하는 자연스러운 방법 - 각 문제에 대한 답을 원래 문제에 대한 답으로 병합하는 효율적인 방법 + 더이상 분할하지 않고 바로 풀 수 있는 매우 작은 문제