[2020모각코] 2회차 2020.12.30

 

분할정보(Divide and Conquer)이란

주어진 문제를 작은 사례로 나누고(Divide) 각각의 작은 문제들을 해결하여 정복(Conquer)하는 방법이다. 분할정복법은 문제의 사례를 2개 이상의 더 작은 사례로 나누어 문제를 해결한다.

 

이 문제의 핵심은 종이가 모두 같지 않다면 9개의 종이로 자르는 것과 각각의 종이가 어떤 수로 채워졌는지 확인하는 것이다.

n이 1인 경우 즉 더 이상 나누어지지 않는 경우 최소 크기의 종이가 되므로 종이의 갯수에 바로 더해주었다.

만약 n이 1이 아니라면 종이가 더 나누어 질 수 있으므로 같은 종이로 구성되었는지 확인해야 한다. 따라서 첫번째 종이와 다른 모든 종이를 비교하여 다른 종이가 있으면 체크 해 주었다. 다른 종이가 없는 경우 같은 종이로 이루어져 있기 때문에 맞는 종이의 숫자를 더해주었다.

만약 다른 종이가 있는 경우 해당 종이를 3*3의 종이로 다시 나누어 주면서 위의 과정을 반복해서 진행했다. 

이 문제는 큰 종이를 3*3의 작은 종이로 나누어(Divide) 작은 종이들의 문제를 해결하여 정복(Conquer)하는 문제이다. 

이 문제도 위의 문제와 같은 개념으로 해결하는 문제이다.

이 문제의 종이는 blue(1)와 white(0)로만 이루어 진다. 따라서 같은 종이인지 확인하는 과정에서 구성된 종이의 합계를 구하는 방식으로 해결하였다.

 

같은 유형의 문제를 풀어서인지 시간이 남아 한 문제를 더 풀어보기로 했다.

 

이 문제의 핵심은 분할정복을 이용하여 계산 시간을 최대한 줄이는 것이다.

재귀를 사용하여 문제를 해결하였다. 이 문제를 해결하기 위해선 제곱을 계산해주는 함수인 calc 함수의 호출이 최소로 이루어 져야 한다. 따라서 제곱을 해야하는 횟수인 b만큼 호출하는 것이 아니라 b를 2로 나누어(Divide)주면서 호출했다. 즉 b번의 문제를 b/2로 분할하여 해결하였다.