1. 문제 설명 (1) 팬미팅에 참가한 M명의 팬들은 줄을 서서 맨 오른쪽 멤버에서부터 시작해 한 명씩 왼쪽으로 움직이며 포옹합니다. (2) 아래의 그림은 행사 과정 일부를 보여줍니다. a~c는 세 명의 하이퍼시니어 멤버이고, 0~4는 다섯 명의 팬들입니다. (3) 하지만 하이퍼시니의 남성 멤버들이 남성 팬과 포옹하기가 민망하다고 여겨서, 남성 팬과는 포옹 대신 악수를 합니다. (4) 줄을 선 멤버들과 팬들의 성별이 각각 주어질 때 팬미팅이 진행되는 과정에서 하이퍼시니어의 모든 멤버가 동시에 포옹 하는 일이 몇 번이나 있는지 계산하는 프로그램을 만드시오. 2. 입출력 조건 및 예제 입력 조건 (1) 멤버들의 성별과 팬들의 성별을 각각 나타내는 두 줄의 문자열로 구성한다. (2) M은 남자, F는 여자를 ..

1. 문제 설명 (1) 카라츠바 알고리즘은 정수 두 수를 절반으로 쪼개는 것으로부터 시작됩니다. (2) 다음 문제 설명은 아래의 그림을 보고 이해합니다. ( 이때, 카라츠바는 a x b를 네 개의 조각을 이용해 표현하면 위와 같이 표현할 수 있습니다. ( 이 방법에서는 두 큰 정수를 한 번 곱하는 대신 네 번 곱합니다. ) ( 이때, 10의 거듭제곱은 시프트 연산으로 구현하므로 곰셈으로 치지 않습니다. ) ( 이해를 돕기 위해 아래의 사진을 참고하세요. ) ( 그러나, 위 방법대로 네 번 곱하는 시간 복잡도를 구해보면 결국 O(N^2)이 됩니다. ) ( O(N^2) = 덧셈과 시프트 연산(O(N)) x 2/n길이 조각들의 곱셈 네 번 by 마스터 정리 ) ( 여기서 카라츠바가 발견한 것은 아래와 같이 네..

( 여기서 설명하는 알고리즘은 카라츠바를 쓰기 이전의 알고리즘을 설명합니다. ) ( 그러므로, 분할 정복을 사용하는 카라츠바 알고리즘은 아래의 사이트로 이동하길 바랍니다. ) 카라츠바의 빠른 곱셈 알고리즘(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