countingalaxy

7.6 팬미팅

문제 가장 멤버가 많은 아이돌 그룹으로 기네스 북에 올라 있는 혼성 팝 그룹 하이퍼 시니어가 데뷔 10주년 기념 팬미팅을 개최했습니다. 팬미팅의 한 순서로, 멤버들과 참가한 팬들이 포옹을 하는 행사를 갖기로 했습니다. 하이퍼시니어의 멤버들은 우선 무대에 일렬로 섭니다. 팬미팅에 참가한 M명의 핸들은 줄을 서서 맨 오른쪽 멤버에서부터 시작해 한 명씩 왼쪽으로 움직이며 멤버들과 하나씩 포옹을 합니다. 모든 팬들은 동시에 한 명씩 움직입니다. 남성 멤버와 남성 팬이 만났을 때는 포옹 대신 악수를 합니다. 줄을 선 멤버들과 팬들의 성별이 각각 주어질 때 팬미팅이 진행되는 과정에서 하이퍼시니어의 모든 멤버가 동시에 포옹을 하는 일이 몇 번이나 있는지 계산하는 프로그램을 작성하시오. 입력 첫 줄에 테스트 케이스의 ..

7.4 울타리 잘라내기

문제 너비가 같은 N개의 나무 판자를 붙여 세운 울타리가 있습니다. 시간이 지남에 따라 판자들이 부러지거나 망가져 높이가 다 달라진 관계로 울타리를 통째로 교체하기로 했습니다. 이때 버리는 울타리의 일부를 직사각형으로 잘라내 재활용하고 싶습니다. 울타리를 구성하는 각 판자의 높이가 주어질 때, 잘라낼 수 있는 직사각형의 최대 크기를 계산하는 프로그램을 작성하세요. 단, 직사각형을 비스듬히 잘라낼 수는 없습니다. 판자의 너비는 모두 1이라고 가정합니다. 시간 및 메모리 제한 프로그램은 1초 안에 실행되어야 하며, 64MB 이하의 메모리를 사용해야 합니다. 입력 첫 줄에 테스트 케이스의 개수 C(C

7.2 쿼드 트리 뒤집기

대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 기법 중 하나 —> 쿼드 트리 (quad tree) 주어진 공간을 항상 4개로 분할해 재귀적으로 표현하기 때문에 쿼드 트리라는 이름이 붙음. 문제 쿼드 트리로 압축된 흑백 그림이 주어졌을 때, 이 그림을 상하로 뒤집은 그림을 쿼드 트리 압축해서 출력하는 프로그램을 작성하세요. 시간 및 메모리 제한 프로그램은 1초 안에 실행되어야 하며, 64MB 이하의 메모리를 사용해야 ㅎ바니다. 입력 첫 줄에 테스트 케이스의 개수 C(C는 50보다 작거나 같음)가 주어집니다. 그 후 C줄에 하나씩 쿼드 트리로 압축한 그림이 주어집니다. 모든 문자열의 길이는 1,000 이하이며, 원본 그림의 크기는 2^20 * 2^20 을 넘지 않습니다. 출력 각 테스트 케..

종만북 ch07 분할정복 - 카라츠바 알고리즘

7.1 도입 분할 정복(Divide & Conquer) : 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산 분할 정복이 일반적인 재귀 호출과 다른 점 : 문제를 한 조각과 나머지 전체로 나누는 대신 거의 같은 크기의 부분 문제로 나눈다. 분할 정복을 사용하는 알고리즘들이 공통적으로 가지는 세 가지의 구성 요소 divide : 문제를 더 작은 문제로 분할하는 과정 merge : 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정 base case : 더이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제 분할 정복을 적용해 문제를 해결하기 위해 요구되는 문제의 특성 문제를 둘 이상의 부분..

programmars 가장 큰 수

programmars 여행경로