Divide and Conquer

큰 문제를 쪼개서 푼 다음, 이를 다시 합쳐가며 최종 답을 구하는 방법크게 세 가지 파트로 나눌 수 있다.1) Divide: 말 그대로, 문제를 더 작은 sub-problems로 나눈다.2) Conquer: sub-problems를 해결할 때까지 recursive 하게

시간 제한: 1 초메모리 제한: 256 MB주어진 점으로 만들 수 있는 모든 쌍을 하나하나 조사한다면, 시간 복잡도는 O(n^2)이다.따라서, 더 빠른 알고리즘을 생각해야 한다.Divide and Conquer를 이용할 수 있을 것 같다.preprocess배열을 x좌표

시간 제한: 1초메모리 제한: 256MB예제를 보니, 기본 삼각형(N=3)으로 패턴이 이루어져 있다. 거꾸로 보면, 삼각형 전체를 출력하기 위해서, 파트를 세 개로 쪼개서 출력하면 된다. DAC로 풀 수 있을 것 같다.NxW char Array를 ' '로 초기화 한다.

시간 제한: 1초메모리 제한: 256MBNaive하게 B번 곱하면, 시간 복잡도는 O(B)이다. 대신에, A^B 는 A^(B/2)인 것을 이용하면, 시간을 줄일 수 있을 것이다.A^x를 구하기 위해, A^(x/2)를 구한다.A^(x/2)를 제곱하여 A^x를 구한다.x가

시간 제한: 5초메모리 제한: 128MBpostidx는 sub-tree의 root이다. 따라서, post를 거꾸로 순회하면, sub-tree의 root부터시작 해서 자손을 채울 수 있다. 그러나, 각 child의 좌우를 구분할 수 없고, 어디가 sub-tree의 끝인지

시간 제한: 2초메모리 제한: 128MB가능한 양 끝 i,j의 모든 경우는 n(n+1)/2 가지이다. 대신에, Divide and Conquer로, 좌우로 분할하여 각 구간에서 최대를 찾고, 구간을 합칠 때 경계선에서 만들어지는 경우만 조사하면, 시간 복잡도를 개선할