분할정복 (3) 썸네일형 리스트형 백준 1030 프렉탈 평면 (파이썬) https://www.acmicpc.net/status?from_problem=1&problem_id=1030 채점 현황 www.acmicpc.net 문제 풀이 문제 이해를 시도하다가 도저히 안되어서 블로그를 참고했지만...이해하는데 오래 걸린 문제이다. 푸는데 이해를 하는데 고생을 한 만큼 글로 정리하고자 한다. 이 문제는 분할정복을 이용해서 푸는 문제로 재귀를 이용해서 풀었다. 문제를 푸는 순서는 다음과 같다. 입력값들을 받는다. 전체 프렉탈을 구성해 놓고 출력을 하는 것이 아닌 문제에서 원하는 지점에 대해서 검사를 한다. (전체 프렉탈을 구성할 경우 최대 2^30 * 2^30 인 프렉탈이 나오고 메모리 공간이 부족한 것은 물론 시간 복잡도 적인 측면에서 보아도 얻을 이점이 존재하지 않기 때문이다.).. [백준] 2630 색종이 만들기(JAVA) https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 풀이 필자는 문제를 처음보고 분할 정복과 재귀를 이용하면 쉽게 풀릴것 같다는 생각을 하였다. 이번에는 두개의 코드를 포스팅 할것이다. 우선 첫번째 코드는 내가 짠 코드이고 두번째는 다른 사람들이 짠 코드이다. 첫번째 코드는 우선 처음 메소드에 들어가면 해당사이즈 만큼의 색종이가 하나의 색으로 되어있는지 확인하고 만약 여기서 하나의 색으로만 되어있으면 그자리에서 바로 함수.. [백준] 1074 백준 (JAVA) https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 풀이 이 문제는 처음에는 재귀를 이용한 분할 정복 문제이다. 여기서 중요한 점은 n이 조금만 커져도 배열의 크기가 엄청 커진다는 점이다. 그렇기에 우리는 불필요한 위치까지 탐색할 필요가 없다. 여기서 중요한 점은 전체 배열의 크기를 줄인다는것에 있다. 즉 문제에서 주어지는 r, c는 가만히 두되 전체 배열의 크기를 점점 줄여 나가면서 (r,c)가 위치한 사분면에 따라 분할하고 재귀적으로 .. 이전 1 다음
