백준 문제풀이(파이썬)/분할 정복

히스토그램에서 넓이가 가장 큰 직사각형을 구하는 문제이다. 최댓값이 될 수 있는 경우는 1. 경계의 왼쪽에서 너비 1의 직사각형이 최대인 경우 2. 경계의 오른쪽에서 너비 1의 직사각형이 최대인 경우 3.경계를 기준으로 붙어있는 직사각형이 최대인 경우로 세가지가 있다. 1번과 2번 경우는 너비가 1이 될 때까지 분할해서 1이면 높이를 return해주면 되지만, 3번 경우는 combine해줄 때 start부터 end까지 돌면서 최대의 직사각형을 구해줘야하기 때문에, 3번의 경우에 주목해서 코드를 짜야한다. start부터 end까지의 범위가 정해졌을 때 경계(mid)를 기준으로 맞닿아있는 직사각형은 각각 square[mid](왼쪽), square[mid+1](오른쪽)일 것이다. left와 right는 각각 ..

행렬의 제곱을 이용하여 피보나치수열을 구하는 문제이다. 피보나치 수를 구하는 방법 중에 DP를 이용하는 방법이 가장 효율적이라고 생각했었는데, 더 빠른 방법이 있다는 것이 신기했다. 일단 입력값이 매우 크기 때문에 O(N)의 알고리즘으로는 절대 풀 수 없음을 인지하고 있어야 한다. DP로 풀면 O(N)이기 때문에 다른 방법으로 풀어야 하는데, 앞에서 계속 풀었던 행렬을 이용하면 된다. 피보나치수열을 행렬을 이용하여 표현하면 밑의 식과 같다. 위의 식이 의미하는 것은 행렬 [[1,1], [1,0]]을 i번 제곱한 값에 행렬 [[1], [0]]을 곱하여 피보나치 수를 구할 수 있다는 것이다. 또한 제곱을 해줄 때 매번 1/2로 단축이 되기 때문에 시간 복잡도는 O(logN)이다. ##함수 선언 부분 MAX_..

이항 계수를 구하는 문제이다. 이항 계수 1과 이항 계수 2에서는 DP로 풀 수 있었지만, 이 문제의 입력 범위가 매우 크기때문에 같은 방식으로 풀면 시간 초과가 뜬다. 그러므로 문제 앞에 나와있는 페르마의 소정리를 이용하여 풀어보자. 정수 a와 p가 있고 a가 p의 배수가 아니면서 p가 소수(Prime number)일 때 다음이 성립한다. 수식을 풀이하면 a^p를 p로 나눈 나머지는 a를 p로 나눈 나머지가 된다는 뜻이다. 또한 양 변을 a로 나누면 다음 식을 유도할 수 있다. (n, k)%p -> (n!/k!(n-k)!)%p -> A=n!, B=k!(n-k)!로 치환 -> (A*B^(-1))%p -> ((A%p) * (B^(-1)%p))%p -> ((A%p) * (B^(p-2))%p)%p -> (A*..

파란색 사각형과 하얀색 사각형의 개수를 구하는 문제이다. 1/4로 계속해서 나누어 주면서 만약 나누어진 영역의 값이 모두 1이거나 모두 0 이면 카운트해주면 되겠다. 2차원 배열로 입력값을 받기 때문에 분할을 한 뒤 각 영역의 시작과 끝 인덱스가 중요할 것이다. merge sort 알고리즘을 짜 보면 대충 어떻게 풀 지 감이 온다. merge sort에서는 left와 right로 mid를 구해서 left부터 mid, mid+1부터 right까지 두 개로 분할해서 재귀 함수를 만들었다. 같은 원리로 이 문제에서는 두 개로 나누는 것이 아니라 네 개로 나눌 뿐이다. 그렇다면 어떻게 나누어야 할까? 시작 부분의 인덱스와 끝 부분의 인덱스를 안다면 그것을 꼭짓점으로 하는 사각형을 구할 수 있을 것이고, 모두 1..