hades

🥅 문제https://www.acmicpc.net/problem/5639 🔍 설계입력으로 주어진 50 30 24 5 28 45 98 52 60 에서 루트, L, R을 구분하면, 50 30 24 5 28 45 98 52 60 이다.L, R 서브트리 각각의 서브트리를 구해도 루트는 첫 번째, L은 두 번부터 루트보다 작은 수까지, R은 루트보다 큰 수부터 끝까지라는 것을 알 수 있다. 서브 트리에 해당하는 인덱스의 범위를 재귀로 만들어서 LRV를 진행하면 된다. 주의해야할 점은 개수가 정해져 있지 않기 때문에, while을 이용하여 벡터에 입력값을 지정했는데, 이럴 경우 최종 인덱스는 마지막 인덱스보다 하나 더 많은 총 개수이다. 따라서 범위를 지정할 때, end는 사용되지 않는다는 것에 유의해야 한다...

🥅 문제https://www.acmicpc.net/problem/9663 🔍 설계N-Queen에서 퀸들은 같은 행, 같은 열, 대각선에 놓이지 말아야 한다. 한 행씩 모든 열에 배치를 시도하고, 배치가 가능하면, 다음 행으로 넘어가서 배치한다. 이 과정을 반복한다. check에서 현재 행과 현재 행 이전까지의 행을 살펴보기 때문에 같은 행에 놓일 수 없고, 같은 열인지, 대각선에 위치하는지만 확인하면 된다. 👊 풀이#include #include #include #include using namespace std;int n, result = 0;vector col(15);bool check(int cur_row) { for (int i = 1; i > n; nqueen(1); cout

🥅 문제https://www.acmicpc.net/problem/14500 🔍 설계처음에는 시작 좌표를 잡고, 그 좌표에서 시작하는 테트로미노 케이스를 모두 만들어서 값을 도출하려 했으나, 대칭과 회전까지 고려했을 때, 케이스가 너무 많아진다. 테트로미노의 특징은 인접한 칸으로 이루어져 있다는 것이다. 따라서, DFS를 이용하여 4개의 칸으로 이루어진 테트로미노를 만들 수 있다. (poli) 하지만, ㅗ 모양의 테트로미노는 인접한 칸으로 확장해나가는 DFS로 구할 수 없으므로, 따로 만들어야 한다. ㅗ 모양을 만드는 가장 쉬운 방법은 十 모양의 테트로미노를 만들고, 상하좌우에서 하나씩 빼면 된다. 十 모양을 구성하는데, 칸이 존재할 수 있는 범위를 벗어나는 경우에는 제외되었다고 생각하면 되고, 제외된..

🥅 문제https://www.acmicpc.net/problem/2630 🔍 설계현재 색종이의 모든 칸의 색이 같지 않으면 4등분해 나가는 문제이다. 재귀로 해결할 때의 시간 복잡도를 계산해보면, O(2^7*2^7+2^6*2^6*2^2+2^5*2^5*2^2*2^2...)=O(2^14*8)=O(2^17)이므로, 시간 제한 1초 내에 해결할 수 있다. 재귀함수에 시작점과 현재 색종이의 변의 길이를 전달한다. 칸의 색이 하나라도 다르면 잘라야 하기 때문에 비교 대상은 시작점의 색으로 하였다.  현재 색종이의 모든 칸을 확인하면서 다른 색을 가진 칸이 있다면, 4등분한 색종이를 나타내는 재귀함수를 실행한다. 현재 색종이의 모든 칸을 확인하면서 다른 색을 가진 칸이 없다면, 시작점의 색과 모두 같다는 의미이므..

🥅 문제https://www.acmicpc.net/problem/1074 🔍 설계2 X 2가 될 때까지 나누다가 2 X 2가 되었을 때, Z를 그리면서 순서를 센다.  나누는 과정에서도 Z 모양으로 나눈다.  중요한 것은 영역을 나누는 과정에서 Target 칸이 속하지 않은 영역의 칸 수는 순서를 신경쓰지 않아도 되므로, 쉽게 구할 수 있다는 것이다.  재귀 함수를 통해  영역의 한 변의 길이가 2라면, Z를 그리면서 순서를 센다. 2보다 크다면 Target 칸이 속하지 않은 영역의 칸 수를 더한다.  주의해야할 점은 나누는 과정에서도 Z 모양으로 나누기 때문에 순서를 신경써야 한다. 👊 풀이#include #include #include #include using namespace std; int..