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

문제 https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 풀이 처음 문제를 접하면 가장 큰 종이(5x5)부터 순서대로 대입해보면 되는 그리디 알고리즘처럼 느껴진다. 하지만 이러한 방식으로 문제를 해결하면 아래와 같은 예외적인 입력에서는 오답을 출력한다. 위와 같은 종이 판에 5-> 4-> 3-> 2-> 1 의 순서로 종이를 대입하게 되면 위와 같이 3x3 크기의 종이 1개가 먼저 배치된 후 나머지는 1x1 크기의 종이 4개가 채우게 된다...

문제 www.acmicpc.net/problem/1543 1543번: 문서 검색 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한 www.acmicpc.net 풀이 단순한 문제인데 정답 비율이 낮은 이유는 있었다. 일단 풀고 보니 런타임 에러가 나서 계속 string의 범위 값을 확인했지만, 사실은 문서보다 찾는 단어가 더 긴 경우를 예외처리해주지 않으면 문서(document)의 범위 값을 넘어 버려 런타임 에러가 발생한다. 예외처리만 확실하다면 나머지는 간단하다. 처음부터 끝까지 substr() 을 이용하여 찾는 단어(word)와 비교하여 맞다면 count를 1 증..

문제 www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 풀이 궁수를 배치하는 경우의 수를 모두 탐색하여 해당 배치에서 최대 몇 명의 적을 죽일 수 있는지 확인하여 최댓값을 구하면 되는 부르트 포스 문제이다. 거리가 같다면 왼쪽의 적부터 공격하는 것과 궁수들이 동일한 적을 공격할 수 있다는 것을 주의 하며 구현하자. ArrayArcher(): 3명의 궁수를 배열하는 모든 경우의 수를 탐색. isArcherPosition[]에 해당 궁수가 배치되면 true 값을 저장하여, ..

문제 www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 풀이 쉬운 듯 하지만 정답률이 낮은 이유는 감소하는 수의 최댓값은 9,876,543,210로 int형의 최댓값인 2,147,483,647보다 크기 때문에 int 형이 아닌 long형을 써주지 않아 그런것 같다. 본인의 경우에는 감소하는 수가 0~9까지만 이용가능 하므로, 11자리 이상 갈 일이 없다고 생각하질 않고 문제를 풀어 메모리 초과가 발생했다... 두 점만 명심하고 풀면 어렵진 않다...

문제 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변� www.acmicpc.net 풀이 테트로미노는 문제에서 나오는 5가지의 모형을 대칭, 회전시키면 총 19개의 고정 형태의 테트로미노가 나온다. 종이의 크기는 500이하로, 19가지의 모형을 모두 대입해서 모든 경우의 수를 구하는 게 충분히 가능하다. 이를 구현하기 위해서 (0,0)인 현재 위치로 부터 상대적인 위치를 저장한 int tetrominoModel[19][3][2] 가 필요한다. 1 2 3 4 5 6 7 8 ..

문제 www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 풀이 모바일 게임으로 많이 해봤을 법한 2048게임을 구현하는 문제이다. 블록들은 네가지 방향중 한 방향으로 모두 이동 시키는데, 이때 같은 크기의 블록이 있다면 합쳐지면서 두배의 수가 된다. 또한 구현에서 중요한 것이 현재의 이동을 통해 이미 한번 합쳐진 블록은 또 다시 합칠 수가 없다. 이 점을 유의하며 구현해보자. 일단은 네가지 방향중 왼쪽으로 이동시키는 경우를 구현한 M..

문제 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이기 때문 에 서로의 친구 여부를 담아둔다. 그 후에는 기저 사례로 짝지어진 수가 전체 학생 수의 반인 ..