판교의 메타몽

https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 몇 몇 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다. 나머지 빈 칸을 채우는 방식은 다음과 같다. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 굵은 선으로 구분되어 있는 3 www.acmicpc.net 스토쿠(9x9)에서 숫자를 집어 넣는데는 조건이 있다. 1. 가로 2. 세로 3. 3x3칸 이 세 가지에서 겹치는 숫자가 없어야 숫자를 넣..

#include #include #define MAX 16 using namespace std; int arr[MAX]; int N,ans = 0; bool check(int num){ for(int i=1; i N; dfs(0); cout

#include #define MAX 9 int arr[MAX]; bool check[MAX]; using namespace std; void BackTracking(int Count, int N, int M, int Start){ if(Count==M){ for(int i=0; i

#include #define MAX 9 int arr[MAX]; bool check[MAX]; using namespace std; void BackTracking(int Count, int N, int M){ if(Count==M){ for(int i=0; i

백 트래킹 (Back Tracking) 말 그대로 왔던 길을 다시 추적하는 알고리즘. 즉, 모든 경우를 전부 고려하는 알고리즘이다. 여기까지만 본다면 모든 경우를 하나하나 실험해보는 'Brute Force'가 떠오를 것이다. Brute Force와는 차별화된 Back Tracking의 특징은 필요없는 값은 정답 후보군을 제거해주는 가지치기(Pruning 혹은 Branch and bound)이다. 이 가지치기를 통해 한번 갔던 루트 중, 재방문이 필요없는 루트는 탐색하지 않는다. 백 트레킹에는 크게 3가지 종류가 있다. 스택 혹은 재귀함수를 이용하는DFS(깊이우선탐색, Depth First Search), 큐를 이용하는 BFS(너비우선탐색, Breadth First Search) BFS/HS(최선우선탐색,..

#include #include using namespace std; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); bool check1 = true; // 열의 홀 짝 (가로) bool check2 = true; // 행의 홀 짝 (세로) int T = 0; int num; cin >> num; while(T

#include using namespace std; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int num = 0; cin >> num; for(int i=0; i

#include #include using namespace std; int calculate(double a, double b){ double ans = 0; double i=0; for(; ; i++){ if(i*i>b-a) break;} i-=1; if(i*i==b-a) ans = i*2-1; else if(i*i T; int a[T]; for(int i=0; i> start >> end; if(end-start

Stable_sort() 그리고 sort() 먼저 하단의 이미지를 참고하자 (참고 : https://blog.naver.com/chogahui05/221215669388) 안정 정렬 (stable sort)이란 뭘까요? 의외로 ps 사이트에서 알게 모르게 많이 질문받는 것 중 하나입니다. sorting을 배우시면서 안정 정렬을 간... blog.naver.com 단순 sort로 정렬을 진행 할 경우, 우선순위가 동등할 때 '들어온 순서'에 따른 기존의 순서는 필수적으로 지켜지지 않을 수 있다. 10개 정도의 적은 데이터가 입력되면 지켜질 수도 있지만, 수천개, 수만개의 데이터가 들어오면 순서가 지켜지지 않을 수 있다. 때문에 들어온 순서또한 안정적이게 지켜질 수 있도록, 두 가지 방법 중 하나를 선택해서..

#include #include #include using namespace std; bool check(paira, pairb){ return a.first> T; for(int i=0; i> age >> name; v.push_back(pair(age,name));} stable_sort(v.begin(),v.end(),check); for(int i=0; i