반응형 분할정복 썸네일형 리스트형 [분할 정복] L-트로미노(L-Tromino) 타일링 1. 트로미노란? 트로미노(Tromino)란, n=3인 폴리오미노(polyomino)로, 크기가 같은 정사각형 3개를 변끼리 붙여 만든 다각형이다. 따라서 다음과 같이 두 개의 트로미노가 존재할 수 있다. 2. $2^n$ x $2^n$ L-트로미노 타일링 이제, 이 트로미노중에서 일자형이 아닌 L 모양의 트로미노를 한 변의 길이가 $2^n$인 정사각형에 배치하는 것이 목표이다. 결론부터 말하자면, L-트로미노는 1x1 한 칸을 제외하고, 한 변의 길이가 $2^n$인 정사각형을 항상 채울 수 있다. 증명은 다음과 같이 수학적 귀납법으로 가능하다. [정리] $2^n$ X $2^n$ 크기의 정사각형에 1x1 한 칸을 제외하고 항상 L-트로미노로 모두 채울 수 있다. [증명] 1. n = 1일 때 n = 1인 .. [BOJ 1725] 히스토그램 1725번 (히스토그램) 위의 문제는 분할 정복 알고리즘을 이용해서 해결할 수 있다. 분할 정복은 주어진 문제를 부분 문제들로 나누어 푸는 것이기 때문에 이 문제 또한 히스토그램을 나누어 푸는 것이 핵심이다. 따라서 주어진 n개의 막대그래프를 절반으로 나누게 되면 결국 찾고자 하는 가장 큰 직사각형은 다음 세가지중 하나에 속하게 된다. 1. 왼쪽 부분 문제에서 가장 큰 직사각형이 존재하는 경우 2. 오른쪽 부분 문제에서 가장 큰 직사각형이 존재하는 경우 3. 가장 큰 직사각형이 왼쪽 부분 문제와 오른쪽 부분 문제에 걸쳐 있는 경우 1번과 2번의 경우에는 재귀 호출을 이용하면 되고, 3번의 경우만 특별히 고려한다면 답을 구할 수 있을 것이다. 문제에서 출력이 20억을 넘지 않는다고 하였으니, 변수 자료형을.. [BOJ 1992] 쿼드트리 1992번 (쿼드트리) 위와 같이 문제가 주어져 있다. 주어진 크기 안의 숫자가 모두 0이거나 모두 1이어야 하고, 만약 이를 만족하지 않는다면 다시 사각형을 4등분하기 때문에 재귀함수를 이용해야 한다는 생각을 할 수 있다. 따라서 분할정복으로 아래와 같이 코드를 작성하면 된다. quadtree라는 재귀함수를 작성하여, 해당 사각형내의 숫자가 모두 같은 경우에는 그 숫자를 출력하고, 같지 않다면 ( 괄호를 출력하고, 4등분한 사각형에 각각 재귀함수를 호출해준다. 이전 1 다음
