( 여기서 설명하는 알고리즘은 카라츠바를 쓰기 이전의 알고리즘을 설명합니다. ) ( 그러므로, 분할 정복을 사용하는 카라츠바 알고리즘은 아래의 사이트로 이동하길 바랍니다. ) 카라츠바의 빠른 곱셈 알고리즘(2) - O(N^lg3) (tistory.com) 카라츠바의 빠른 곱셈 알고리즘(2) - O(N^lg3) 1. 문제 설명 (1) 카라츠바 알고리즘은 정수 두 수를 절반으로 쪼개는 것으로부터 시작됩니다. (2) 다음 문제 설명은 아래의 그림을 보고 이해합니다. ( 이때, 카라츠바는 a x b를 네 개의 조각을 이 kind-coding.tistory.com 1. 문제 설명 (1) 카라츠바의 알고리즘은 두 개의 정수를 곱하는 일을 합니다. (2) 32비트 정수 둘을 곱할 때 쓰는 것이 아닌 수백 자리 또는 ..

1. 문제 설명 (1) 너비가 같은 N개의 나무 판자를 붙여 세운 울타리가 있습니다. (2) 시간이 지남에 따라 판자들이 망가져 높이가 다 달라져서 기존의 울타리 일부를 직사각형으로 잘라내 재활용하고 싶습니다. (3) 이때, 울타리를 구성하는 각 판자의 높이가 주어질 때, 잘라낼 수 있는 직사각형의 최대 크기를 계산하는 프로그램을 작성하세요. ( (b)는 (a)의 울타리에서 잘라낼 수 있는 많은 직사각형 중 가장 넓은 직사각형을 보여줍니다. ) ( 단, (c) 처럼 비스듬히 잘래날 수 없습니다. ) 2. 입출력 조건 및 예제 입력 조건 (1) 판자의 수 N(1

1. 문제 설명 (1) 대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(quad tree)가 있습니다. (2) 쿼드 트리는 주어진 공간을 4개로 항상 분할해 재귀적으로 표현하며, (2^N) X (2^N) 크기를 가집니다. (3) 쿼드 트리는 흑백 그림을 다음과 같은 과정을 거쳐 문자열로 압축합니다. - 이 그림의 픽셀이 모두 검은색이라면, 압축 결과는 b가 됩니다. - 이 그림의 픽셀이 모두 흰색이라면, 압축 결과는 w가 됩니다. - 모든 픽셀이 같은 색이 아니라면, 압축 결과는 x가 됩니다. - 이때, x는 하위 자식을 가질 수 있으며 아래와 같이 표현될 수 있습니다. (왼쪽 위 부분의 압축 결과)(오른쪽 위 부분의 압축 결과) (왼쪽 아래 부분의 압축 결과)(..

1. 문제 설명 (1) 크기가 N*N인 행렬 A가 주어진다. 이때, A^B를 구하는 프로그램을 작성한다. 2. 입출력 조건 및 예제 입력 조건 (1) 2