문제https://www.acmicpc.net/problem/1987풀이과정입력으로 알파벳 대문자로 이루어진 보드판이 주어진다. (0,0) 부터 문제에서 주어진 규칙에 따라 인접한 상하좌우로 이동할 수 있는 최대칸 수를 출력해야하는 문제다.DFS로 접근을 했고 처음에는 문제를 잘못보고 이전 알파벳하고 방문하는 알파벳만 다르면 방문할 수 있는 줄 알았다.문제를 자세히 보면 밟아온 보드판에서 사용된 알파벳은 다시 밟을 수 없다고 한다.그래서 알파벳의 사용여부를 체크하는 배열을 만들어 DFS를 돌렸다.소스코드#include #include #include using namespace std; #define MAX 21 int r, c; char alpha[MAX][MAX]; // 입력되는 보드판 bool ch..
문제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의 남은 물의..
문제https://www.acmicpc.net/problem/1525풀이의 핵심 입력을 2차원 배열로 저장하지 않고 입력을 받아 하나의 정수로 만든다.BFS를 이용해 123456789 까지 탐색한다.상하좌우를 검사해서 바꿀 수 있으면 바꾼다.dist[num] 에 연산횟수를 저장한다.소스코드#include #include #include #include using namespace std; int dx[4] = { 0,0,1,-1 }; int dy[4] = { 1,-1,0,0 }; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n = 3; int start = 0; // 2차원 배열이 아닌 하나의 정수로 나타낸다. (0을 9로..
문제https://www.acmicpc.net/problem/9019풀이과정소수 경로 문제와 어떻게 보면 비슷한 문제지만 정말 까다로운 문제였다. 강의를 들으며 대충의 풀이방법을 알고 구현을 시작했지만 시간이 꽤 걸렸다.BFS문제며 최소횟수 문제이기 때문에 dist[]로 횟수를 저장한다. 하지만 이 문제는 어떤 연산을 통해서 수를 만들었나 출력해야하기 때문에 연산의 방법도 저장해야한다. 또한, 연산 전의 숫자를 저장해야한다.소스코드#include #include #include #include #include using namespace std; #define MAX 10001 bool visited[MAX]; int dist[MAX]; int from[MAX]; char how[MAX]; char cm..
문제https://www.acmicpc.net/problem/1963풀이과정입력으로 1쌍의 네 자리 소수가 주어진다. 출력은 두 소수 사이의 변환에 필요한 최소 회수를 출력해야한다. BFS로 해결할 수 있는 문제다. 아래와 같은 순서로 해결했다. 10000까지의 모든 소수를 구해 저장한다.change(num,index,digit) : 네 자리 소수 num의 index번째 숫자를 digit으로 바꾸는 함수를 구현한다.BFS를 통해 네자리 소수의 첫 번째 자리부터 끝자리까지 모든 경우의 수를 탐색한다. 이 때, 소수가 아니면 그냥 넘어간다.dist라는 배열의 변환 횟수를 저장한다. 소스코드#include #include #include #include using namespace std; #define MA..
문제https://www.acmicpc.net/problem/1697풀이과정이제부터 모든 문제를 제한시간 1시간을 두고 최대한 생각을 해보고나서 안될 것 같으면 검색을 해야겠다. 한시간이 되기 전에 이 문제가 주어지는 n을 n-1,n+1,n*2 로 나눠지는 트리를 만들어 depth를 출력하면 될 것 같다는 생각을 하게됐다. 하지만 생각처럼 구현을 하지 못했다.이제는 슬슬 BFS, DFS가 이해되기 시작한다. 나중에 한 번 더 풀어봐야겠다소스코드#include #include #include using namespace std; #define MAX 200000 bool chk[200000]; // i에 방문했는지의 여부 int dist[200000]; // dist[i] i까지 가는데 걸린 비용 int ..
문제https://www.acmicpc.net/problem/10819풀이과정완전탐색을 순열로 구현해서 푼 문제다. N의 범위가 작기 때문에 순열로 완전탐색을 해도 시간초과가 나지 않을 수 있다. 보통 N이 10이하면 순열로 문제를 풀어도 된다고 한다.먼저 입력받은 배열을 sort()를 통해 정렬을 해준 후 next_permutation을 통해서 모든 순열을 돌면서 가장 차이가 큰 값을 찾는다.소스코드#include #include #include using namespace std; int calculate(vector &a) { int result = 0; for (int i = 1; i < a.size(); i++) { result += abs(a[i - 1] - a[i]); } return res..
문제https://www.acmicpc.net/problem/1107풀이과정리모컨이 부숴졌으면 고치면 되지 왜 그러는지 참 아무튼 리모컨의 어떤 숫자 버튼이 고장났을 경우 +,- 버튼을 통해 이동하고 싶은 채널로 가야한다. 이 때, 최소 이동횟수를 구하는 문제다. 브루트 포스를 이용하면 풀 수 있었다.처음 초기값은 문제에서 지금 보고있는 채널이 100번이므로 abs(N-100) 으로 지정한다.그리고 0번부터 100만까지 채널을 하나하나 탐색해서 제일 짧은 이동횟수를 구한다. (100만인 이유는 범위는 50만까지지만 채널 이동은 50만 위로 올라가서 -버튼을 누르는 경우가 있기 때문)소스코드를 보면 이해하기가 더욱 쉽다.소스코드#include using namespace std; #define MAX_M ..