문제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 ..
문제https://www.acmicpc.net/problem/1476풀이과정범위가 작기 때문에 브루트 포스 방법으로 완전탐색을 하면 쉽게 풀 수 있는 문제다.소스코드#include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int e, s, m; int cmp_e=1, cmp_s=1, cmp_m=1; int ans = 1; cin >> e >> s >> m; while (true) { if (e == cmp_e && s == cmp_s && m == cmp_m) { cout 28 ? 1 : cmp_s + 1; cmp_m = cmp_m+1 > 19 ? 1 : cmp_m + 1; ans += 1; } return 0; }
문제https://www.acmicpc.net/problem/1722풀이과정N이 주어지면 k번째 순열을 출력하거나 순열을 입력받아서 몇 번째 순열인지 출력하는 문제다.처음에 문제를 보고 next_permutation을 쓰면 쉽게 풀릴 줄 알고 썻는데 너무 쉽게 풀려고 했나보다 N의 최대값이 20이기 때문에 브루트 포스로 풀면 시간초과가 나버린다.아래와 같은 알고리즘을 통해 구현을 해야 시간초과가 안나고 해결할 수 있다.입력 순열로 5 2 4 7 6 3 1 이 주어지면 1 ? ? ? ? ? ? - 6!개 , 2 ? ? ? ? ? ? 6!개, 3 ? ? ? ? ? ? 6!개, 4 ? ? ? ? ? ? 6!개 5 1 ? ? ? ? ? - 5!개 5 2 1 ? ? ? ? - 4!개, 5 2 3 ? ? ? ? -..
문제https://www.acmicpc.net/problem/10974풀이과정정수 N이 주어지면 1부터 N까지의 수로 이루어진 순열을 사전순으로 모두 출력하는 문제이다. 1~N 까지 vector에 push next_permutation을 이용해 끝까지 출력 소스코드#include #include #include using namespace std; vector v; int main() { int N; cin >> N; for (int i = 0; i < N; i++) v.push_back(i + 1); do { for (int i = 0; i < v.size(); i++) cout
문제https://www.acmicpc.net/problem/10972풀이과정1부터 N까지의 수로 이루어진 순열이 주어지면 사전순으로 다음에 오는 순열을 구하는 문제이다. 이러한 문제들을 보면 항상 내 머리로는 셀 수 있는데 코딩을 할 수가 없어서 자괴감이 들었던 것 같다.찾아보니 C++ 에 정말 편리한 함수가 존재했다. next_permutation(v.begin(),v.end()) 는 v라는 벡터의 처음과 끝을 주면 다음 순열이 존재할 경우 true를 리턴하고 벡터의 원소들을 다음 순열로 만들어준다. 꼭 벡터가 아니여도 배열의 처음과 끝을 줘도 된다.이러한 함수를 내가 구현해봐야 좋겠지만 일단은 사용법만 알아두고 응용하는 법만 알아둬야겠다.반대로 prev_permutation도 있다.소스코드#incl..
문제https://www.acmicpc.net/problem/6603풀이과정문제를 다 읽어본 후 [완전탐색] 문제라는걸 알았는데 DFS로 구현해야하는 문제인지는 잘 몰랐다. 풀이를 찾아서 DFS 구현을 봤는데 잘 이해가 가지 않는다.DFS로 탐색을 하다가 6개가 모이면 출력을 하는 식인데 이러한 과정이 어떻게 진행되는지 정확하게 이해를 하지 못했다.인프런 강의와 다른 강의를 좀 더 찾아서 DFS를 이용한 완탐 구현을 좀 더 공부하고 다시 풀어봐야겠다.소스코드#include #include #define MAX_N 13 using namespace std; int S[MAX_N]; int lotto[MAX_N]; int k; void lotto_print() { for (int i = 0; i < 6; i..