문제https://www.acmicpc.net/problem/2580풀이과정스도쿠를 완성하는 문제이다. DFS와 백트래킹을 통해 가능한 수를 구해서 완성되면 출력한다. 스도쿠의 규칙은 열, 행 , 3x3 정사각형 칸에 1~9까지의 숫자가 한개씩만 존재해야한다.이러한 규칙에 따라서 열, 행, 정사각형의 어떤 숫자(1~9)가 존재하는지 체크하는 배열을 만든다.모든 경우의 수를 다 해볼 수 있지만 그렇게 하면 시간초과가 뜰 수 있다.소스코드#include using namespace std; #define MAX_NUM 10 int sudoku_size = 9; int sudoku[MAX_NUM][MAX_NUM]; bool chk_row[MAX_NUM][MAX_NUM]; // 행에 숫자(1~9)가 존재하는지 ..
문제https://www.acmicpc.net/problem/1759풀이과정문제에서 만들어야 될 암호의 길이와 사용할 수 있는 알파벳의 종류가 주어진다.입력으로 주어지는 사용할 수 있는 알파벳들을 배열로 저장하였고, 그 배열의 인덱스를 하나씩 늘려가며 사용할지 안할지 결정해 암호를 만드는 recursion 함수를 구현했다.소스코드의 주석을 보면 이해하기가 쉽다.소스코드#include #include #include #include using namespace std; bool chk(string &password) { int ja = 0, mo = 0; int length = password.length(); for (int i = 0; i < length; i++) { char c = password[..
문제https://www.acmicpc.net/problem/2251풀이과정A, B, C 세 가지 물통의 부피가 주어진다. 문제에서 물통 C는 처음부터 꽉 차있다고 주어진다. 문제에서 원하는 답은 물통 A가 비어있을 때 C에 남아있는 물의 양이다. 문제에서 물이 옮겨담기는 과정에서 손실되는 경우는 없다고 했다. 그러므로 A, B 물통에 남아있는 물의 양만 있다면 물통 C에 남아있는 물의 양도 구할 수 있다. c(물통 C의 남은 물의 양) = C(물통 C의 부피) - a(물통 A의 남은 물의 양) - b(물통 B의 남은 물의 양) 물을 옮겨담는 경우의 수는 총 6가지다. A -> BA -> CB -> AB -> CC -> AC -> B모든 경우를 탐색해보기 위해 BFS를 이용하고 물통 A, B의 남은 물의..