재귀입니당~
--------------------------------------------------------------------------------------------------------------------------
<9095번 / 1, 2, 3 더하기>
또 이거야? 이 문제 뭐야 알고리즘의 대가 뭐 이런건가... 알대 딱대.
정수 N을 1, 2, 3의 합으로 표현하는 것이다. 여기서 N의 제한이 10이니까 가능하고, 총 경우의 수는 자리에 올 수를 3개 중에서 고르는 거니까 3^n이다. 이전과는 달리 재귀함수로 해결해보자.
우선 브루트 포스를 사용하기 위해 찾아봐야 할 3가지 경우가 있다.
1. 불가능한 경우
- 재귀함수 호출을 계속해도 정답을 못 구하는 경우
- 문제 조건을 위배하는 경우
2. 정답을 찾은 경우
- 더 이상 함수를 호출할 필요가 없다.
3. 다음 경우를 호출해야할 경우
모든 문제를 풀 떄 위의 3가지를 생각하며 풀어준다. 그럼 이 문제에 적용을 해보도록 하자!
이 문제에서 재귀함수를 go(count, sum, goal)로 하였다. 이 함수는 숫자 count개로 합 sum을 만드는 경우의 수를 구한다. 그럼 위의 3가지를 따져보면 불가능한 경우는 sum>goal인 경우이다. 정답은 sum=goal일때고 다음 경우는 go(count+1, sum+i, goal)로 호출하면 된다.
막상 코드 구현을 해보니 count가 필요가 없어서 count 없이 구현하였다.
|
#include <iostream> #include <algorithm> using namespace std; int go(int sum, int goal) { if (sum > goal) return 0; if (sum == goal) return 1; int res = 0; for (int i = 1; i <= 3; i++) { res += go(sum + i, goal); } return res; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; while (t--) { int n; cin >> n; cout << go(0, n) << '\n'; } return 0; } |
<1759번 / 암호 만들기>
암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음과 최소 두 개의 자음으로 구성되어 있다. 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되어있어야 한다. 암호로 사용할 수 있는 문자의 종류는 C가지, 가능성 있는 암호를 모두 구하는 문제이다. 여기서 어떤 알파벳이 등장하거나, 등장하지 않거나(현재 알파벳이 암호에 추가되거나, 추가되지 않거나)로 나눌 수 있다. 그러면 시간복잡도는 O(2^C)이다.
그럼 브루트포스 3가지로 나눠서 생각해보자. 재귀함수 go에서 n은 암호의 길이, alpha는 입력으로 받은 알파벳 배열, password는 지금까지 만든 암호, i는 배열의 인덱스이다. 그리고 3가지로 나누면 우선 정답을 찾은 경우는 password의 길이가 n이면 된다. 그리고 불가능한 경우는 재귀함수를 계속 호출해도 정답이 아닌 경우와 문제의 조건을 위반한 경우이다. 문제의 조건은 모든 배열을 만들고 판단하도록 하고 우선 재귀함수를 계속 호출해도 정답이 아닌 경우는 선택할지 말지 결정할 알파벳의 인덱스인 i가 alpha의 크기 즉, 사용할 수 있는 배열의 크기보다 큰 경우이다. 그럼 더이상 선택할 알파벳이 없는데 암호가 완성되지 않았으므로 정답을 찾을 수 없다. 마지막으로는 다음 경우를 호출해야하는 경우이다. 이 경우는 i번쨰 알파벳을 선택하는 경우와 선택하지 않는 경우로 나눌 수 있다. 선택하는 경우는 go(n, alpha, password+alpha[i], i+1)로 호출하고, 선택하지 않는 경우는 go(n, alpha, password, i+1)을 호출하면 된다.
여기서 C가 길이인 배열을 선택할지 말지 고르는거니까 시간복잡도는 O(2^C)이다.
구현해보겠습니당
check함수로 한 개의 모음과 두 개의 자음으로 구성되어 있는지 확인한다. 저기서 i가 alpha보다 큰 경우가 정답을 찾은 경우 아래에 있는데 이게 위로 올라가게되면 마지막 알파벳을 포함하는 경우를 처리할 수 없기 때문에 저기에 있어야 한다. 그니까 위에서 password길이랑 n길이 비교해서 같은지 아닌지 확인하고 만약에 password가 짧은데 i가 alpha사이즈보다 크면 더이상 password를 구할 수 없으니까 return하는거다. 이것도 선택하던가 말던가니까 시간복잡도 O(2^c)이다.
|
#include <iostream> #include <algorithm> #include <vector> #include <string> using namespace std; bool check(string &password) { int ja = 0; int mo = 0; for (char x : password) { if (x == 'a' || x == 'e' || x == 'i' || x == 'o' || x == 'u') { mo++; } else ja++; } if (ja >= 2 && mo >= 1) { return true; } else return false; } void go(int n, vector<char> &alpha, string password, int i) { if (password.length() == n) { if (check(password)) { cout << password << '\n'; } return; } if (i >= alpha.size()) { return; } go(n, alpha, password + alpha[i], i + 1); go(n, alpha, password, i + 1); } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int l, c; cin >> l >> c; vector<char> alpha(c); for (int i = 0; i < c; i++) { cin >> alpha[i]; } sort(alpha.begin(), alpha.end()); go(l, alpha, "", 0); return 0; } |
<14501번 / 퇴사>
n+1일이 되는 날 퇴사를 하려고 한다. 남은 n일 동안 최대한 많은 상담을 하려고 한다. 하루에 하나의 상담을 할 수 있고 i일에 상담을 하면 T[i]일이 걸리고 P[i]원을 번다. 이 문제도 i일에 상담을 할지 말지 결정하면 되기 때문에 시간 복잡도는 는 O(2^n)이다. n의 제한이 15니까 모든 경우를 다 구할 수 있다.
이 문제도 3가지 경우를 생각해보자. 함수가 go(day, sum)이라고 하면 day일이 되었을 때 day일에 있는 상담을 할지 말지 결정해야 한다. sum은 지금까지 얻은 수익이 된다.
첫번째로 정답을 찾은 경우는 day가 n+1과 같은 경우이다. n+1일이 되는날 퇴사하니까 같으면 퇴사를 하는 것이다. 불가능한 경우는 day가 n+1보다 큰 경우이다. 이는 조건이 위배되는 것이므로 불가능하다. 마지막으로 다음 경우를 호출하는 경우는 day날에 상담을 하는 경우와 상담하지 않는 경우로 나눌 수 있다. 상담을 하는 경우는 go(day+T[day], sum+P[day])이고, 하지 않는 경우는 go(day+1, sum)이다.
코드 작성 해볼까융~~
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
#include <iostream> #include <algorithm> using namespace std; int t[16]; int p[16]; int n; int ans = 0; void go(int day, int sum) { if (day == n + 1) { if (ans < sum) ans = sum; return; } if (day > n + 1) { return; } go(day + t[day], sum + p[day]); go(day + 1, sum); return; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n; for (int i = 1; i <= n; i++) { cin >> t[i] >> p[i]; } go(1, 0); cout << ans << '\n'; return 0; } |
cs |
-백트래킹
재귀 함수를 브루트 포스를 하다보면, 더 이상 함수 호출이 의미 없는 경우가 있다. 이 때, 이런 경우를 제외하고 브루트 포스를 진행하면 백트래킹이라고 한다. 쉽게 말하면 그냥 브루트 포스는 일단 모든 경우를 다 만들고 문제의 조건과 맞는지 판단했다면, 백트래킹은 함수 호출중에 중간에 정답을 구할 수 없을 것 같으면 함수 호출을 중단한다. 그러면 코드상으로는 크게 달라지는 것 같지 않지만 시간이 굉장이 단축된다.
<14889번 / 스타트와 링크>
n명을 n/2명씩 두 팀으로 나누려고 한다. 이 때 n의 제한은 20이고 짝수이다. 두 팀의 능력치를 구한 다음, 차이의 최소값을 구하는 문제이다. S[i][j]는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 S[i][j[의 합이다. 그럼 아래 그림처럼 첫번째 사람부터 n번째 사람까지 1번팀 혹은 2번팀을 고르는 것이다. 그럼 이의 시간 복잡도는 O(2^n)이다.
이 문제는 n 제한이 20이기 때문에 그냥 다 해보는것도 가능하긴 하다. 우선 다 구해보도록 하자. 재귀함수를 go(index, first, second)라고 하면 index번째 사람을 first, second 팀 중 어디에 넣을지 결정한다. 정답을 찾은 경우는 index가 n과 같을 때이다. 다음 경우는 1번팀 선택시와 2번팀 선택시의 함수 호출은 go(index+1, first, second)로 동일하다. 하지만 first와 second에 index를 넣고 함수를 호출하고, 다시 index를 빼는 과정이 필요하다.
먼저 백트래킹 사용하지 않고 다 구한 후 조건에 맞는지 판단하도록 해보자
|
#include <iostream> #include <algorithm> #include <vector> int s[20][20]; int n; using namespace std; int go(int index, vector<int> &first, vector<int> &second) { if (index == n) { if (first.size() != n/2) return -1; if (second.size() != n / 2) return -1; int t1 = 0; int t2 = 0; for (int i = 0; i < n / 2; i++) { for (int j = 0; j < n / 2; j++) { if (i == j) continue; //i=j면 s[i][j]=0이니깐 t1 += s[first[i]][first[j]]; t2 += s[second[i]][second[j]]; } } int diff = abs(t1 - t2); return diff; } int ans = -1; first.push_back(index); int t1 = go(index + 1, first, second); if (ans == -1 || (t1 != -1 && ans > t1)) { ans = t1; } first.pop_back(); second.push_back(index); int t2 = go(index + 1, first, second); if (ans == -1 || (t2 != -1 && ans > t2)) { ans = t2; } second.pop_back(); return ans; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> s[i][j]; } } vector<int> first, second; cout << go(0, first, second) << '\n'; return 0; } |
자 이제 백트래킹을 해보자. 저 위의 코드에서 불가능한 경우만 추가하면 된다. 중간에 함수를 호출해도 정답을 구할 수 없을 것 같으면 종료하는 것이다. 그 경우는 first와 second의 크기가 n/2보다 크면 무조건 안된다. 따라서 함수 호출 중에 n/2보다 크다면 무조건 종료하는 부분을 추가하면 된다.
29, 30번쨰 줄만 추가했다. 보기엔 별거 아니지만 실제로는 시간이 엄청 단축 된다고 한다!
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
#include <iostream> #include <algorithm> #include <vector> int s[20][20]; int n; using namespace std; int go(int index, vector<int> &first, vector<int> &second) { if (index == n) { if (first.size() != n/2) return -1; if (second.size() != n / 2) return -1; int t1 = 0; int t2 = 0; for (int i = 0; i < n / 2; i++) { for (int j = 0; j < n / 2; j++) { if (i == j) continue; //i=j면 s[i][j]=0이니깐 t1 += s[first[i]][first[j]]; t2 += s[second[i]][second[j]]; } } int diff = abs(t1 - t2); return diff; } if (first.size() > n / 2) return -1; if (second.size() > n / 2) return -1; int ans = -1; first.push_back(index); int t1 = go(index + 1, first, second); if (ans == -1 || (t1 != -1 && ans > t1)) { ans = t1; } first.pop_back(); second.push_back(index); int t2 = go(index + 1, first, second); if (ans == -1 || (t2 != -1 && ans > t2)) { ans = t2; } second.pop_back(); return ans; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> s[i][j]; } } vector<int> first, second; cout << go(0, first, second) << '\n'; return 0; } |
<15661번 / 링크와 스타트>
이전 문제와 다른 점은 인원수가 정해지지 않았다는 것이다. 위의 코드에서 출력 부분과 탈출조건? 만 조금 바꿔주었다.
|
#include <iostream> #include <algorithm> #include <vector> int s[20][20]; int n; using namespace std; int go(int index, vector<int> &first, vector<int> &second) { if (index == n) { int fir = first.size(); int sec = second.size(); if (fir < 1) return -1; if (sec < 1) return -1; int t1 = 0; int t2 = 0; for (int i = 0; i < fir; i++) { for (int j = 0; j < fir; j++) { if (i == j) continue; //i=j면 s[i][j]=0이니깐 t1 += s[first[i]][first[j]]; } } for (int i = 0; i < sec; i++) { for (int j = 0; j < sec; j++) { if (i == j) continue; t2 += s[second[i]][second[j]]; } } int diff = abs(t1 - t2); return diff; } int ans = -1; first.push_back(index); int t1 = go(index + 1, first, second); if (ans == -1 || (t1 != -1 && ans > t1)) { ans = t1; } first.pop_back(); second.push_back(index); int t2 = go(index + 1, first, second); if (ans == -1 || (t2 != -1 && ans > t2)) { ans = t2; } second.pop_back(); return ans; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> s[i][j]; } } vector<int> first, second; cout << go(0, first, second) << '\n'; return 0; } |
<2529번 / 부등호>
부등호 기호가 나열된 수열 A가 있다. 기호의 앞뒤에 한자리 숫자를 넣어서 부등호 관계를 만족시키려고 한다. 이 때, 선택된 수는 모두 달라야 한다. k개의 부등호 관계를 모두 만족시키는 (k+1)개 자리의 정수 중에서 최댓값과 최솟값을 구하는 문제이다.
그럼 각 부등호 사이에 올 숫자는 0부터 9까지의 숫자이고 숫자끼리 중복은 허용되지 않으니까 앞에서 사용한 숫자를 제외하고 선택해주면 된다.
아래는 일단 백트래킹을 사용하지 않고 브루트포스만을 사용하여 코드를 짠 것이다. 아래를 이용하여 구현해보았다.
main함수에서 auto는 알아서 자료형을 맞추도록 하는 것이다. minmax_element는 .first에 min_element가 저장되고, .second에 max_element가 저장되는 알고리즘이다. 이걸 통해 쉽게 배열의 최댓값과 최솟값을 찾았다!!
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
#include <iostream> #include <algorithm> #include <vector> #include <string> using namespace std; char a[20]; //부등호 저장 int n; vector<string> ans; bool check[10]; bool ok(string num) //수가 n+1까지 있다 { for (int i = 0; i < n; i++) { if (a[i] == '<') { if (num[i] > num[i + 1]) return false; } else if (a[i] == '>') { if (num[i] < num[i + 1]) return false; } } return true; } void go(int index, string num) { if (index == n + 1) { if (ok(num)) { ans.push_back(num); } return; } for (int i = 0; i <= 9; i++) { if (check[i]) continue; check[i] = true; go(index + 1, num + to_string(i)); check[i] = false; } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n; for (int i = 0; i < n; i++) { cin >> a[i]; } go(0, ""); auto p = minmax_element(ans.begin(), ans.end()); cout << *p.second << '\n'; cout << *p.first << '\n'; return 0; } |
위에서는 모든 경우를 구한 후 ok함수를 통해 조건에 부합한지 확인했다. 그러면 이번엔 백트래킹을 이용하여 애초에 안되는 것을 검사해서 구해보도록 하자! 함수 호출 중간에 정답이 될 수 없는 경우를 발견하면 그 뒤의 호출은 진행하지 않아도 되기 때문에 시간이 엄청 단축된다.
good함수를 추가해서 배열 추가 전에 확인하고 추가한다. 이게 바로 백트래킹! 이 결과로 시간이 엄청 단축되었다. 백트래킹은 문제마다 시간을 줄일 수 있는 방법이 다르기 때문에 문제마다 어떻게 줄일 수 있을지 생각해야 한다.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
#include <iostream> #include <algorithm> #include <vector> #include <string> using namespace std; char a[20]; //부등호 저장 int n; vector<string> ans; bool check[10]; bool good(char x, char y, char op) { if (op == '<') { if (x > y) return false; } if (op == '>') { if (x < y) { return false; } } return true; } void go(int index, string num) { if (index == n + 1) { ans.push_back(num); return; } for (int i = 0; i <= 9; i++) { if (check[i]) continue; if (index == 0 || good(num[index - 1], i + '0', a[index - 1])) { check[i] = true; go(index + 1, num + to_string(i)); check[i] = false; } } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n; for (int i = 0; i < n; i++) { cin >> a[i]; } go(0, ""); auto p = minmax_element(ans.begin(), ans.end()); cout << *p.second << '\n'; cout << *p.first << '\n'; return 0; } |
<1248번 / 맞춰봐>
sign 배열에는 입력받은 문자열에 따라서 +면 1, -면 -1, 0이면 0을 저장해서 부호를 표시해준다. ans배열에 진짜 수열을 저장하고 sign배열의 원소*i를 하면 해당 숫자가 부호에 맞게 적용되니까 이 점을 사용했다.
|
#include <iostream> #include <string> using namespace std; int n; int sign[10][10]; //부호를 저장하는 배열(+ || -) int ans[10]; //실제 수열을 저장하는 배열 bool ok(int index) { int sum = 0; for (int i = index; i >= 0; i--) { sum += ans[i]; if (sign[i][index] == 0) { if (sum != 0) return false; } else if (sign[i][index] < 0) { if (sum >= 0) return false; } else if (sign[i][index] > 0) { if (sum <= 0) return false; } } return true; } bool go(int index) { if (index == n) { return true; } if (sign[index][index] == 0) { ans[index] = 0; return ok(index) && go(index + 1); } for (int i = 1; i <= 10; i++) { ans[index] = sign[index][index] * i; if (ok(index) && go(index + 1)) return true; } return false; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n; string str; cin >> str; int cnt = 0; for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { if (str[cnt] == '0') { sign[i][j] = 0; } else if (str[cnt] == '+') { sign[i][j] = 1; } else if (str[cnt] == '-') { sign[i][j] = -1; } cnt++; } } go(0); for (int i = 0; i < n; i++) { cout << ans[i] << ' '; } cout << '\n'; return 0; } |
'코딩테스트 > 알고리즘 기초 강의' 카테고리의 다른 글
| 2강 - 그래프 1 (2) _ 그래프의 탐색 (0) | 2020.12.30 |
|---|---|
| 2강 - 그래프 1 (1) (0) | 2020.12.29 |
| 1강 브루트 포스 - 순열 (0) | 2020.09.01 |
| 1강 브루트 포스 - N과 M (0) | 2020.08.29 |
| 1강 브루트 포스 - 건너 뛰며 해보기 (0) | 2020.08.28 |
댓글