분할정복6 BOJ 1992 쿼드트리 문제 링크 : https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 요약 BOJ 1780 종이의 개수와 매우 유사한 문제 0, 1로 이루어진 N x N의 행렬이 있을 때 전체 영역이 모두 같은 값이라면 한 개로 압축하고, 그게 아니라면 가로 2, 세로 2 영역으로 4등분하여 각 영역이 모두 같은 값으로 이루어질 때까지 나누었을 때 압축한 결과를 괄호에 싸서 출력하는 문제. 풀이 전형적인 분할정복 문제!! 부분 행렬의 전부를 탐색했을 때 .. 2022. 3. 17. BOJ 1780 종이의 개수 문제 링크 : https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 요약 -1, 0, 1로 이루어진 N x N의 행렬이 있을 때 전체 영역이 모두 같은 값이라면 한 장만 사용해도 되고, 그게 아니라면 가로 3, 세로 3 영역으로 9등분하여 각 영역이 모두 같은 값으로 이루어질 때까지 나누었을 때 -1, 0, 1로만 채워진 종이의 각각의 개수를 구하는 문제. 풀이 전형적인 분할정복 문제!! 부분 행렬의 전부를 탐색했을 때 모두 같은 값이라면.. 2022. 3. 14. BOJ 1725 히스토그램 문제 링크 : https://www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 www.acmicpc.net 요약 히스토그램 안에서 색칠할 수 있는 직사각형의 최대 크기를 구하는 문제(한 막대그래프의 가로길이는 1로 봄) 풀이 BOJ 2104 부분배열 고르기 문제와 유사한 문제다. 분할 정복으로 해결할 수 있으며 부분 히스토그램의 시작점을 s, 끝점을 e, 그 중간값을 mid로 두었을 때 최대 넓이는 세 가지 중에 있다. s~mid 부분 배열중 최대 넓이, mi.. 2022. 3. 14. BOJ 2104 부분배열 고르기 문제링크 : https://www.acmicpc.net/problem/2104 2104번: 부분배열 고르기 크기가 N(1 ≤ N ≤ 100,000)인 1차원 배열 A[1], …, A[N]이 있다. 어떤 i, j(1 ≤ i ≤ j ≤ N)에 대한 점수는, (A[i] + … + A[j]) × min{A[i], …, A[j]}가 된다. 즉, i부터 j까지의 합에 i부터 j까지의 최솟값을 곱 www.acmicpc.net 요약 크기가 N의 1차워 배열의 부분배열의 합과 부분배열에서의 최솟값의 곱의 최대값을 구하는 문제 풀이 완전 탐색으로 해결하기에는 시간초과가 우려된다. 분할정복을 통해 해결해보았다. 두 부분으로 나눠서 왼쪽에서 가장 큰 점수를 갖는 부분 배열과 오른쪽에서 가장 큰 점수를 갖는 부분배열을 비교해준.. 2022. 3. 12. 이전 1 2 다음
