분할 정복4 [Baekjoon] 1780번: 종이의 개수 https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 문제 해결 과정 착안 이전 포스트에서의 분할 정복(divide and conquer) 알고리즘 문제와 해결 방법이 유사하여 해당 코드를 변형하여 문제를 해결하였다. 정사각형 모양의 색종이가 균일한 색깔을 가지고 있는지 판단하여, 그렇지 않다면 가로를 3등분, 세로를 3등분한 다음, 동일한 크기의 9 개의 작은 색종이에 대해 다시 균일한 색깔을 가지는지 판단하는 과정을 반복하여 문제를 해.. 2023. 7. 5. [Baekjoon] 1992번: 쿼드 트리 https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 문제 해결 과정 착안 주어진 데이터가 0 또는 1의 값으로 균일한지 판단하고, 균일하지 않다면 주어진 데이터를 4 개의 균등한 영역으로 나눈 다음 각각의 영역이 다시 0 또는 1의 값으로 균일한지 판단하는 분할 정복(divide and conquer) 알고리즘의 코드를 작성하여 문제를 해결하고자 했다. 구현 주어진 영역이 0 또는 1의 값으로 균일한 상태인지 판단하는 함수를 구현하여 .. 2023. 7. 4. [Baekjoon] 2630번: 색종이 만들기 https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 문제 해결 과정 착안 분할 정복(divide and conquer) 알고리즘을 통해 정사각형 모양의 색종이가 균일한 색깔을 가지는지 확인하고, 균일한 색으로 이루어져 있지 않다면 동일한 크기의 4 개의 작은 색종이로 나누어가며 색종이 내부의 색깔이 일정한지 확인하는 과정을 반복하여 해결하고자 하였다. 구현 배열의 인덱스를 좌표와 같이 사용하여 색종이의 좌상단 좌표와 한 .. 2023. 6. 29. [Baekjoon] 4779번: 칸토어 집합 https://www.acmicpc.net/problem/4779 4779번: 칸토어 집합 칸토어 집합은 0과 1사이의 실수로 이루어진 집합으로, 구간 [0, 1]에서 시작해서 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만든다. 전체 집합이 유한이라고 가정하고, www.acmicpc.net 문제 해결 과정 착안 주어진 문제에서의 배열을 3등분하여 왼쪽, 가운데, 오른쪽 부분 배열로 나누고 이때 왼쪽과 오른쪽의 부분 배열에 대해서 같은 과정을 반복적으로 수행하여 최종 답을 얻을 수 있다. 즉, 부분 문제들의 해를 합하여 최종 해를 구할 수 있는 문제이므로 분할 정복(divide and conquer) 알고리즘을 구현하여 문제를 해결하고자 하였다. 인수로 전달되는 배열의 길이가 1이 될.. 2023. 5. 21. 이전 1 다음
