분할 정복 (4) 썸네일형 리스트형 [알고스팟] 팬 미팅 문제 링크 문제 정보문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)FANMEETING15000ms65536kb4020560 (13%)출제자출처분류YongrokRUN Programming Contest, Fall 2009보기문제가장 멤버가 많은 아이돌 그룹으로 기네스 북에 올라 있는 혼성 팝 그룹 하이퍼시니어가 데뷔 10주년 기념 팬 미팅을 개최했습니다. 팬 미팅의 한 순서로, 멤버들과 참가한 팬들이 포옹을 하는 행사를 갖기로 했습니다. 하이퍼시니어의 멤버들은 우선 무대에 일렬로 섭니다. 팬 미팅에 참가한 M명의 팬들은 줄을 서서 맨 오른쪽 멤버에서부터 시작해 한 명씩 왼쪽으로 움직이며 멤버들과 하나씩 포옹을 합니다. 모든 팬들은 동시에 한 명씩 움직입니다. 아래 그림은 행사 과정의 일부를 보여줍.. [알고스팟] 울타리 잘라내기 문제 링크 울타리 잘라내기문제답안 제출통계문제 정보문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)FENCE3000ms131072kb94872890 (30%)출제자출처분류JongMan알고리즘 문제 해결 전략보기문제너비가 같은 N개의 나무 판자를 붙여 세운 울타리가 있습니다. 시간이 지남에 따라 판자들이 부러지거나 망가져 높이가 다 달라진 관계로 울타리를 통째로 교체하기로 했습니다. 이 때 버리는 울타리의 일부를 직사각형으로 잘라내 재활용하고 싶습니다. 그림 (b)는 (a)의 울타리에서 잘라낼 수 있는 많은 직사각형 중 가장 넓은 직사각형을 보여줍니다. 울타리를 구성하는 각 판자의 높이가 주어질 때, 잘라낼 수 있는 직사각형의 최대 크기를 계산하는 프로그램을 작성하세요. 단 (c)처럼 직사각형을 비.. [알고스팟] 쿼드 트리 뒤집기 문제 링크 문제 정보문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)QUADTREE10000ms65536kb57762760 (47%)출제자출처분류JongMan알고리즘 문제 해결 전략보기문제대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(quad tree)란 것이 있습니다. 주어진 공간을 항상 4개로 분할해 재귀적으로 표현하기 때문에 쿼드 트리라는 이름이 붙었는데, 이의 유명한 사용처 중 하나는 검은 색과 흰 색밖에 없는 흑백 그림을 압축해 표현하는 것입니다. 쿼드 트리는 2N× 2N 크기의 흑백 그림을 다음과 같은 과정을 거쳐 문자열로 압축합니다.이 그림의 모든 픽셀이 검은 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림의 크기에 관계없이 b가 됩니다.이.. [분할 정복] 분할 정복에 대해서 알아보자 분할 정복은 이름 그대로 문제를 작은 부분으로 쪼개어서 해답을 찾은 뒤에 작은 조각들을 합치면서 다시 해답을 찾아내가는 방식입니다. 대표적인 분할 정복 방식으로는 병합 정렬이 있습니다. 위 그림에서 보듯이 병합 정렬은 배열을 반씩 쪼개서 가장 작은 단위로 쪼갠 다음에 정렬하고, 이 정렬된 배열을 점차적으로 정렬하는 방식입니다. 분할 정복을 할 때 가장 중요하게 고려해야 할 점이 있습니다. 바로 조그만 조각에서 나온 최적해를 이용해서 구해나간 답이 결국 최종 해답과 일치해야 한다는 것입니다. 작은 조각에서 나온 답이 결국 더 큰 조각에서는 쓸모가 없어진다면 의미없는 일을 한 것이겠죠... 또 다른 예로는 행렬의 거듭제곱을 구하는 코드가 있습니다. 보통의 방법으로 행렬의 m 제곱을 구하게 되면, n x n의.. 이전 1 다음
