https://algospot.com/judge/problem/read/QUADTREE algospot.com :: QUADTREE 쿼드 트리 뒤집기 문제 정보 문제 대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(quad tree)란 것이 있습니다. 주어진 공간을 항상 4개로 분할해 재귀적 algospot.com 문자열을 가리키는 포인터를 하나씩 뒤로 옮겨가면서 재귀호출한다. 분할한 부분의 전체가 흰색이거나 검은색일 경우 뒤집어도 똑같은 패턴이므로 그대로 리턴한다. 그게 아니라면 다시 분할한다. 위와 아래 조각들이 바뀐 패턴이 최종 결과이다. #include #include using namespace std; string reverse(string::itera..
https://algospot.com/judge/problem/read/CLOCKSYNC algospot.com :: CLOCKSYNC Synchronizing Clocks 문제 정보 문제 그림과 같이 4 x 4 개의 격자 형태로 배치된 16개의 시계가 있다. 이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있다. 이 시계들이 모두 12시를 가리키도록 algospot.com 각각의 스위치들과 연결된 시계가 있다. 스위치를 누를때마다 시간이 3시간 흐른다. (12->3->6->9) 이 때 모든 시계를 12시로 돌리기 위해 스위치를 최소 몇 번 눌러야 할지 계산해야한다. 먼저 스위치를 4번 누르면 다시 원상태로 돌아온다. 그러므로 스위치를 안 누르거나 최대 3번 누르는 것으로 한정시킬 수 있다..
BOARDCOVER
https://algospot.com/judge/problem/read/BOARDCOVER algospot.com :: BOARDCOVER 게임판 덮기 문제 정보 문제 H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이 algospot.com 완전탐색 문제이다. 그런데 경우의 수를 어떻게 중복없이 체계적으로 셀 수 있을까? 순서를 강제하면 된다. 게임판의 빈 부분을 좌상단부터 하나씩 채워나간다. 이 때 모든 빈 부분이 덮어지면 경우의 수를 하나 더해준다. 아래 그림에서 별표 부분을 덮는다고 가정하자. 이 때 별표 왼쪽 부분까지는 다 채워져 있다. 그러면 L자 모양의 블록을 덮는 경우가 4가..
https://algospot.com/judge/problem/read/BOGGLE algospot.com :: BOGGLE 보글 게임 문제 정보 문제 보글(Boggle) 게임은 그림 (a)와 같은 5x5 크기의 알파벳 격자인 게임판의 한 글자에서 시작해서 펜을 움직이면서 만나는 글자를 그 순서대로 나열하여 만들어지는 영어 algospot.com cache[x][y][idx]를 이용해서 현재 위치 (x,y)에서 idx까지 탐색했을 때 중복 탐색 여부를 확인해준다. 그러면 탐색 가지수를 줄일 수 있다. #include #include int t,n,len; char map[7][7],s[15]; int cache[5][5][10]; int dx[8]={-1,-1,-1,0,0,1,1,1}; int dy[8]..
0~n-1까지 n개의 원소가 있을 때 그 중 m개를 고르는 모든 조합을 출력한다. n: 전체 원소 수 picked: 지금까지 고른 원소들의 번호 toPick: 더 고를 원소의 수 #include #include using namespace std; void printPicked(vector picked) { for(int i : picked) printf("%d ",i); printf("\n"); } void pick(int n,vector& picked,int toPick) { if(toPick==0) { printPicked(picked); return; } int smallest=picked.empty()?0:picked.back()+1; for(int next=smallest;next
https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같다. www.acmicpc.net d[x][y] = x번째 행렬부터 y번째 행렬까지 곱했을 때 곱셈 연산의 최소값 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 #include int n,a[500][2],d[500][500]; int go(int x,int y) { if(d[x][y]) return d[x][y]; if(x==y) ..
https://www.acmicpc.net/problem/2133 2133번: 타일 채우기 문제 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. 입력 첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다. 출력 첫째 줄에 경우의 수를 출력한다. 예제 입력 1 복사 2 예제 출력 1 복사 3 힌트 아래 그림은 3×12 벽을 타일로 채운 예시이다.... www.acmicpc.net d[i][j] = 3*i를 채우는 방법의 수, i열의 상태는 j 상태 다이나믹을 이용해서 경우의 수들을 구할 수 있다. 그림을 그려보면 쉽게 이해할 수 있다. i열을 계산할 때 i-1열은 꽉 차 있어야 한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 ..
https://www.acmicpc.net/problem/1328 1328번: 고층 빌딩 상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼쪽에 서서 빌딩을 몇 개 볼 수 있는지 보았고, 집에 돌아오는 길에는 가장 오른쪽에 서서 빌딩을 몇 개 볼 수 있는지 보았다. 상근이는 가장 왼쪽과 오른쪽에서만 빌딩을 봤기 때문에, 빌딩이 어떤 순서로 위치해있는지는 알 수가 없다. 빌딩의 개수 N과 가장 왼쪽에서 www.acmicpc.net D[N][L][R] = 각각 1~N의 높이를 가진 빌딩을 세웠을 때 가장 왼쪽에서 L개, 가장 오른쪽에서 R개의 빌딩이 보이는 경우의 수..