https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 문제 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다. (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다. 이와 같이 종이를 ..

https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 문제 흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다. 주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과..

이번 포스팅에서 다룰 알고리즘은 '분할 정복'이다. Divide and Conquer 이 알고리즘은 문자 그대로, 분해해서 해결하는 것을 메인 흐름으로 가져간다. 밑의 그림을 보면 이해될 것이다. * 실습 환경은 windows 10/ vscode에서 이뤄졌습니다. 📍 정의 한 번에 해결하기 어려운 문제(시간문제, 공간문제 등)를 잘게 쪼개고 각개 격파한 후, 하나의 답을 도출하는 알고리즘. 분할 정복 알고리즘은 다음 세 개의 프로세스를 가진다. 📍 Process (1) Divide : 문제를 정의하고, 잘게 쪼개는 과정이다. 이 단계에서 문제를 잘 쪼개야 손쉽게 문제를 해결할 수 있다. (2) Conquer : 잘게 쪼개진 문제를 해결할 시간이다. 분할 알고리즘의 문제는 쪼개도 사실상 같은 문제들이다. ..