승쨩개발공부

#include using namespace std;#include #include #include #include #include int n, m;int a[105][105];int vis[105][105];int dy[4] = { -1, 0, 1, 0 };int dx[4] = { 0,1,0,-1 };int cnt = 0;// 문제 : a가 0인곳은 공기임, 1인곳 상우하좌에 2개이상 공기가 있을떄 치즈녹임 녹일치즈가 있을떄 cnt 1 증가시켜서 출력해야함 void dfs(int y, int x){ vis[y][x] = 1; for (int i = 0; i ny || 0 > nx || ny >= n || nx >= m) continue; if (vis[ny][nx] || a[ny][nx] == 1)..

상당히 어려웠는데 퀸에 이동을 막는 규칙을 어떻게 정해야하는지 어려웠다. 퀸은 이렇게 상하좌우 대각선으로 움직일 수 있다. 그리고 0번쨰열에 아무곳에나 퀸을 두면 같은 열에 둘 수 없다.그러면 열을 재외하고행,왼쪽대각선,오른쪽대각선 을 체크를 해 주어야한다. 1.행행을 비교하는 0,1과 2,1이 어떻게 같은 행에 있는지 판단하는가?y값이 같은지 확인하면 된다.둘다 1 2.왼쪽 대각선 왼쪽 대각선을 비교하는 1,2과 3,0이 어떻게 같은지 판단하는가?x + y값이 같은지 확인하면 된다.둘다 3 3.오른쪽 대각선오른쪽 대각선을 비교하는 1,1과 3,3이 어떻게 같은지 판단하는가?x - y값이 같은지 확인하면 된다둘다 0  주의사항2차원 배열로 만들면 안되고, O(1)로 판단하여 가지치기를 해야한다 즉 백트레..

백트레킹은 모든 경우의 수를 재귀적으로 탐색할떄 사용한다.for문으로도 가능하지만 n개의 숫자가 늘어날수록 중첩for문을 해야하니 효율적이지 못할 수 있다. #include #include #include #include using namespace std;int n, m;bool vis[15];vector v;void dfs(){ if (v.size() == m) { for (const int& i : v) { cout > n >> m; dfs(); return 0;}

이전 문제들과 분할법은 똑같지만입력이 붙어있으니 string으로 받아야하고전체영역이 0 이면 0 출력 1이면 1출력섞여있으면 계속 4등분씩 쪼개가면서 체크해야한다. 재귀 슬슬 감 오니 백트레킹,DP 들어가자.

전 문제 BJ 1780 종이의 개수와 풀이 방법은 같다 그러므로 설명 생략

문제풀이분할 정복 알고리즘과 재귀를 이용하여 해결하는 문제이다.분할 정복 알고리즘이란 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 해결하는 방법이다.이 문제에 따르면종이(배열) 안의 숫자들이 모두 같다면, 그 종이는 분할하지 않고 넘어간다.종이 내에 다른 숫자가 하나라도 포함된다면, 그 종이를 9분할 한다.9분할한 종이 하나하나마다 숫자가 같은지 확인한다.(다시 1번으로 반복)9*9 크기의 종이를 예로 들면,9*9 크기에 채워진 숫자들, 즉 81칸의 숫자가 모두 같다면 -> n으로만 적혀있는 종이의 개수 ++하나라도 다르다면 3*3 크기의 종이 9개로 분할 (즉 3^n승이니 한변의 길이는 n/3이다)3*3 크기의 종이 하나하나 다시 체크 -> 모두 같다면 -> n으로만 적혀있는 종이의 개수 ++ ..