문제 algospot.com/judge/problem/read/QUADTREE algospot.com :: QUADTREE 쿼드 트리 뒤집기 문제 정보 문제 대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(quad tree)란 것이 있습니다. 주어진 공간을 항상 4개로 분할해 재귀적 algospot.com 풀이 알고리즘 문제 해결 전략에 등자하는 대표적인 분할 정복 문제. 해당 문제의 원본 그림의 크기는 최대 2의 20승 이기 때문에 단순히 원본 그림으로 복구시킨 후 다시 압축하는 것은 속도도 시간도 부족하다. 해당 문제는 문자열을 4개의 부분으로 분할하여 해결해야한다. 상하가 반전되므로 최소의 분할 대상 크기인 2x2에서는 (가)의 배열은 (나)로 변경되어야 한..

문제 algospot.com/judge/problem/read/CLOCKSYNC algospot.com :: CLOCKSYNC Synchronizing Clocks 문제 정보 문제 그림과 같이 4 x 4 개의 격자 형태로 배치된 16개의 시계가 있다. 이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있다. 이 시계들이 모두 12시를 가리키도록 �� algospot.com 풀이 이번 문제의 핵심은 두 가지이다. 시계는 4번 돌리면 결국 원상태로 돌아온다. 즉, 4번 이상 시계를 돌릴 필요는 없다. 스위치를 누르는 순서는 중요하지 않다. 예를 들어, 0번과 1번 스위치를 누른다고 할 때 무엇을 먼저 누르든 결과는 같다. int pushedNum[10]; //스위치를 누른 횟수를 저장 int c..

문제 algospot.com/judge/problem/read/BOARDCOVER algospot.com :: BOARDCOVER 게임판 덮기 문제 정보 문제 H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이 �� algospot.com 풀이 흰 칸들을 4가지 모양(회전하면 네 가지 모양이 나옴)으로 덮을 경우 가능한 경우 수를 구하는 문제. 해당 문제는 다음과 같이, 한 빈칸을 네 가지 경우로 채우는 재귀 함수를 구현한다. 빨간 부분이 호출된 칸이고, 그 칸과 인접한 1,2번 블록을 채우는 네 가지 블록 모델이다. 이렇게 네가지 경우 이외는 생각해 주지 않아도 되는 이유는 흰 칸의 위치..

문제 https://www.algospot.com/judge/problem/read/PICNIC algospot.com :: PICNIC 소풍 문제 정보 문제 안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 www.algospot.com 풀이 고등학교 확률과 통계 시간에 뭔가 많이 볼 듯한 문제였다. 모든 경우의 수를 확인하는 Burute Force방법으로 해결하면 된다. 이차원 배열인 bool partnerBoard[45][45] //45인 이유는 최대의 짝의 경우 수가 (10*9)/2이기 때문 에 서로의 친구 여부를 담아둔다. 그 후에는 기저 사례로 짝지어진 수가 전체 학생 수의 반인 ..

문제 www.algospot.com/judge/problem/read/BOGGLE algospot.com :: BOGGLE 보글 게임 문제 정보 문제 보글(Boggle) 게임은 그림 (a)와 같은 5x5 크기의 알파벳 격자인 게임판의 한 글자에서 시작해서 펜을 움직이면서 만나는 글자를 그 순서대로 나열하여 만들어지는 영어 �� www.algospot.com 풀이 알고리즘 문제 해결 전략 서적에서 무식하게 풀기(Burute Force) 장에서 가장 처음 나오는 문제이다. 이 문제의 정답 비율이 극악인 이유는 단순히 모든 경우의 수를 확인하는 방법으로는 시간제한을 초과하기 때문이다. 따라서 BF장에서 나오는 문제이지만 동적 계획법(Dynamic programming)을 사용해야 시간 안에 통과할 수 있다. ..

문제 https://www.algospot.com/judge/problem/read/FESTIVAL algospot.com :: FESTIVAL 록 페스티벌 문제 정보 문제 커다란 공연장을 빌려서 록 페스티벌을 개최하려고 합니다. 이 페스티벌은 여러 날 동안 진행되며, 하루에 한 팀의 밴드가 공연장에서 콘서트를 하게 됩니다. 전체 � www.algospot.com 풀이 흔히 종만북이라는 알고리즘 문제 해결 전략 책에서 가장 먼저 나오는 문제. 그 만큼 제출 횟수는 많지만 소수점 출력이 8자리 이상은 되어야해서 틀리는 경우가 많은 듯하다. 첫 문제다 보니 틀리면 상당히 의지가 꺽인다.. ㅠㅠ 가장 먼저 생각난 방법은 역시 모든 경우의 수를 모두 구해보는 부르트 포스 전략이다. 공연장을 대여할 수 있는 날의..