나만의 길

https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 전형적인 분할정복 문제. 앞서 포스팅한 분할정복 문제와 크게 다르지 않습니다. 다만, 괄호를 열고 닫는 구현이 추가된 문제입니다. 이 부분만 해결해 준다면, 큰 어려움 없이 해결할 수 있었습니다. 문제는 모든 행렬이 동일한 값이 아니라면 4 분할이 되므로, 색종이 개수 구하는 문제와 동일합니다. ※ 고려사항 1. 입출력 구현 2. 분할정복 구현 + 괄호 1. 입출력 구현 2차원 배열을..

https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 문제의 형태를 보니, 전형적인 분할정복 문제입니다. 단순히 재귀로 구현하게 되면 메모리초과나 시간초과가 발생하니, 경우를 나누어서 접근하는 것이 중요합니다. 2630번 색종이 만들기와 사실상 동일한 문제라고 봐도 무방합니다. 같은 값을 가졌는지 판별 후, Divide and Conquer을 실행합니다. 함수가 종료되면, 횟수를 카운팅 하면 됩니다. ※ 고려사항 1. 입출력 형식 2. 분..

https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 분할정복 문제. 2^N x 2^N 사각형을 계속해서 4등분을 해서 해당하는 좌표의 값을 불러오는 문제입니다.여기서 Key포인트는 '모든작업을 하면 안된다' 입니다. Divide & Conquer 방식으로 해당 좌표에 포함되는 부분만 나누어서 문제를 해결해야 메모리초과없이 문제를 해결할 수 있습니다. 분할정복에 대한 개념이 확실히 잡히지 않은상태에서 단순 재귀로 구현해서, 계속된 메모리초과..