divide and conquer4 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. 분할정복(Divide and Conquer) 분할 정복 알고리즘은 말 그대로 분할하고 정복하는 알고리즘이다. 먼저 문제를 나눌 수 없을 때까지 나누어 각각을 풀고 다시 합병하여 문제의 답을 얻는다. 어떻게 푸는가? Divide : 문제가 분할이 가능한 경우 두 개 이상의 문제로 나눈다. (가장 중요!!!) Conquer : 나눠진 문제가 여전히 분할이 가능하면, 또 Divide를 수행하고, 그렇지 않으면 문제를 푼다. 문제의 크기를 최대로 줄이게 되면 바로 답을 구할 수준이 됨, 이게 재귀 함수를 이용해서 문제를 풀 때의 기저 사례와 같음, 그래서 분할 정복은 재귀 호출과 궁합이 잘 맞음 Combine : Conquer 한 문제들을 통합해서 원래 문제의 답을 얻는다. 위 그래프가 분할정복 알고리즘의 대략적인 모습이다. 가장 많이 볼 수 있는 문제인.. 2022. 3. 11. 이전 1 다음
