지금은 새벽 3시 11분~~ 2016 무한상사 보는즁~~ 넷플릭스도 봐야되는데~~~ 암튼 코로나 GAESAEKI~~
강의 듣고 올게여~! / 응 다음날 들었어~ 오늘부터 진짜 열심히 해서 주말까지 강의 다들을거야 뿌엥
---------------------------------------------------------------------------------------------------------------------
브루트 포스 방법을 만드는 방법에는 재귀, 순열, 비트마스크 총 3가지 경우가 있는데 그 중에서도 재귀 방법이 가장 중요하다. 순열과 비트마스크는 모두 재귀로 표현할 수 있기 때문이다. 따라서 재귀 연습을 하기 위해서 N과 M으로 연습해볼것이다. 이 문제는 순서 관련 문제와 선택 관련 문제로 나눠서 풀 수 있다.
<15649번 / N과 M (1)>
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 모두 구하는 문제. 이 문제는 순서와 관련된 문제이다.
c배열은 중복확인 함수, a배열은 진짜 수열 저장하는 함수, go함수는 수열 구하는 함수, 이 함수를 재귀해서 푼다. index는 a배열의 index로 이게 m이랑 같아지면 수열의 길이가 끝난거니까 출력해준다. 그리고 반복문에서 수열을 찾는데 중복된 수가 아니라면 a배열에 추가하고, go함수를 호출한다. 그 때 호출이 끝나면 하나의 배열이 끝난거니까 c[i]를 false로 초기화해준다.
|
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 |
#include <iostream> #include <algorithm> using namespace std;; int a[10]; bool c[10]; void go(int index, int n, int m) { if (index == m) { for (int i = 0; i < m; i++) { cout << a[i] << ' '; } cout << '\n'; return; } for (int i = 1; i <= n; i++) { if (c[i] == true) continue; a[index] = i; c[i] = true; go(index + 1, n, m); c[i] = false; //a[index] 초기화 (굳이 필요없어서 생략) } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; go(0, n, m); return 0; } |
cs |
<15650번 / N과 M (2)>
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 오름차순 수열을 모두 구하는 문제.
위의 문제와 다른 점은 이 문제는 오름차순이라는 점이다. 따라서 전에는 1~N 중 앞에서 사용하지 않은수를 골랐지만 이번엔 앞에서 쓴 수가 num이면 다음으로 올 수는 num+1 ~ N중 사용하지 않은 수가 와야 한다.
여기서는 어차피 오름차순이어서 중복을 확인하는 배열이 필요가 없다. (오름차순 만족하려면 당연히 중복일 수 없으니깐) 여기서 start가 다음 수로 올수 있는 수의 시작이 된다. 그래서 반복문에서 i+1을 넣어준다.
|
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 |
#include <iostream> #include <algorithm> using namespace std;; int a[10]; void go(int index, int start, int n, int m) { if (index == m) { for (int i = 0; i < m; i++) { cout << a[i] << ' '; } cout << '\n'; return; } for (int i = start; i <= n; i++) { a[index] = i; go(index + 1, i + 1, n, m); } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; go(0, 1, n, m); return 0; } |
cs |
이 문제는 경우의 수가 n*(n-1)*(n-2)*...*1이 M개가 있는데 이 때 M의 최대값이 N과 같으므로 시간 복잡도는 O(N!)이다.
이번엔 순서가 아닌 선택 방법으로 이 문제를 풀어보자. 이는 각각의 자연수를 선택하는 경우와 선택하지 않는 경우로 나눠서 풀 수 있다. M개의 수에 어떤 수가 들어갈지를 결정해 보자. 얘는 1부터 N까지의 수가 선택되거나 선택되지 않거나 둘 중 하나기 때문에 시간복잡도는 O(2^n)이다.
num은 실제 수열의 숫자, selected는 선택된 숫자의 갯수, 여기서 현재 숫자가 선택된 경우 먼저나오고 선택되지 않은 경우가 나오는데 오름차순으로 출력해야하기 때문에 2개의 순서가 바뀌면 오름차순이 아닐수도 있다. 이거 조심!!
|
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 |
#include <iostream> #include <algorithm> using namespace std;; int a[10]; void go(int num, int selected, int n, int m) { if (selected == m) { for (int i = 0; i < m; i++) { cout << a[i] << ' '; } cout << '\n'; return; } if (num > n) return; a[selected] = num; go(num + 1, selected + 1, n, m); a[selected] = 0; go(num + 1, selected, n, m); } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; go(1, 0, n, m); return 0; } |
cs |
<15651번 / N과 M (3)>
1부터 N까지 자연수 중에서 M개를 고른 수열을 모두 구하는 문제 (중복 선택 가능)
이 문제는 N과 M (1)에서 중복처리 관련 내용을 지워주면 된다!
진짜 중복확인 배열 부분을 지우고 단순히 재귀만으로 해결하였다!
|
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 |
#include <iostream> #include <algorithm> using namespace std;; int a[10]; void go(int index, int n, int m) { if (index == m) { for (int i = 0; i < m; i++) { cout << a[i] << ' '; } cout << '\n'; return; } for (int i = 1; i <= n; i++) { a[index] = i; go(index + 1, n, m); } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; go(0, n, m); return 0; } |
cs |
<15652번 / N과 M (4)>
1부터 N까지 자연수 중에서 M개를 고른 수열을 모두 구하는 문제(중복 선택 가능, 비내림차순)
여기서 비내림 차순이란 같은 숫자가 존재하는 오름차순이다. 이 문제는 N과 M (2)에서 중복 부분만 제거해주면 된다. 이 문제도 순서방법으로 푸는것과 선택 방법으로 푸는 법이 있다.
첫번째로 순서를 기준으로 푼 코드이다. 2번 n과 m 문제에서 중복만 제거해서 풀었다! 그리고 여기서 중요한건 함수 재귀호출을 할 때 i+1이 아닌 i가 들어간다. 왜냐면 비내림차순이기 때문에!
|
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 |
#include <iostream> #include <algorithm> using namespace std;; int a[10]; void go(int index, int start, int n, int m) { if (index == m) { for (int i = 0; i < m; i++) { cout << a[i] << ' '; } cout << '\n'; return; } for (int i = start; i <= n; i++) { a[index] = i; go(index + 1, i, n, m); } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; go(0, 1, n, m); return 0; } |
cs |
2번째는 선택으로 푸는 방법이다. 사실 이 방법으로 풀수는 있지만 굳이..? 이런 느낌이라고 한다. 그래도 공부하는 과정이니까 한번 구해보자. 각각의 자연수를 선택하는 경우와 선택하지 않는 경우가 있다. 하지만, 중복 선택이 가능하기 때문에, 선택하는 경우를 i개 선택하는 경우로 세분화해야 한다.
index는 수열의 실제 수, selected 선택한 수의 갯수, 이 때 selected는 m이 최댓값이다.
|
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 |
#include <iostream> #include <algorithm> using namespace std;; int cnt[10]; void go(int index, int selected, int n, int m) { if (selected == m) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= cnt[i]; j++) { cout << i << ' '; } } cout << '\n'; return; } if (index > n) return; for (int i = m - selected; i >= 1; i--) //선택 { cnt[index] = i; go(index + 1, selected + i, n, m); } cnt[index] = 0; go(index + 1, selected, n, m); } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; go(1, 0, n, m); return 0; } |
cs |
지금까지 N과 M문제에서는 O(2^n) 시간 복잡도의 문제 풀이방법과 순서를 사용하는 풀이 방법이 중요하다!
<15654번 / N과 M (5)>
N개의 서로 다른 자연수 중에서 M개를 고른 수열을 모두 구하는 문제
이건 위의 문제 1~4까지랑 비슷하게 풀면 된다.
c는 중복확인, a는 수열의 인덱스 저장, num은 실제 숫자 배열이다.
|
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 |
#include <iostream> #include <algorithm> using namespace std;; int num[10]; int a[10]; int c[10]; void go(int index, int n, int m) { if (index == m) { for (int i = 0; i < m; i++) { cout << num[a[i]] << ' '; } cout << '\n'; return; } for (int i = 0; i < n; i++) { if (c[i]) continue; c[i] = true; a[index] = i; go(index + 1, n, m); c[i] = false; } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; for (int i = 0; i < n; i++) { cin >> num[i]; } sort(num, num + n); go(0, n, m); return 0; } |
cs |
<15655번 / N과 M (6)>
N개의 서로 다른 자연수 중에서 M개를 고른 수열을 모두 구하는 문제(오름차순)
위의 문제에 오름차순만 추가하면 된다. start 변수를 추가해서 이전 index보다 1크도록 함수를 호출하면 된다.
이건 오름차순 문제니까 중복확인은 필요가 없다. 아래는 순서로 풀어봤다.
|
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 |
#include <iostream> #include <algorithm> using namespace std;; int num[10]; int a[10];
void go(int index, int start, int n, int m) { if (index == m) { for (int i = 0; i < m; i++) { cout << num[a[i]] << ' '; } cout << '\n'; return; } for (int i = start; i < n; i++) { a[index] = i; go(index + 1, i+1, n, m); } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; for (int i = 0; i < n; i++) { cin >> num[i]; } sort(num, num + n); go(0, 0, n, m); return 0; } |
cs |
이번엔 선택방법으로 풀어보쟈~
|
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 |
#include <iostream> #include <algorithm> using namespace std;; int num[10]; int a[10];
void go(int index, int selected, int n, int m) { if (selected == m) { for (int i = 0; i < m; i++) { cout << num[a[i]] << ' '; } cout << '\n'; return; } if (index >= n) return; a[selected] = index; go(index + 1, selected + 1, n, m); a[selected] = 0; go(index + 1, selected, n, m); } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; for (int i = 0; i < n; i++) { cin >> num[i]; } sort(num, num + n); go(0, 0, n, m); return 0; } |
cs |
<15656번 / N과 M (7)>
N개의 서로 다른 자연수 중에서 M개를 고른 수열을 모두 구하는 문제 (중복 가능)
5번 문제에서 중복 수열만 없애면 된다.
|
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 num[10]; int a[10]; void go(int index, int n, int m) { if (index == m) { for (int i = 0; i < m; i++) { cout << num[a[i]] << ' '; } cout << '\n'; return; } for (int i = 0; i < n; i++) { a[index] = i; go(index + 1, n, m); } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; for (int i = 0; i < n; i++) { cin >> num[i]; } sort(num, num + n); go(0, n, m); return 0; } |
cs |
<15657번 / N과 M (8)>
N개의 서로 다른 자연수 중에서 M개를 고른 수열을 모두 구하는 문제(중복 가능, 비내림차순)
우선 순서를 통해서 구해보자. 이건 비내림차순이니깐 오름차순 문제에서 start를 쓰고 함수 재귀호출시 i를 넣어준다. 얘는 비내림차순이니까!
|
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 num[10]; int a[10]; void go(int index, int start, int n, int m) { if (index == m) { for (int i = 0; i < m; i++) { cout << num[a[i]] << ' '; } cout << '\n'; return; } for (int i = start; i < n; i++) { a[index] = i; go(index + 1, i, n, m); } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; for (int i = 0; i < n; i++) { cin >> num[i]; } sort(num, num + n); go(0, 0, n, m); return 0; } |
cs |
이번엔 선택 문제~
|
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 |
#include <iostream> #include <algorithm> using namespace std;; int num[10]; int cnt[10]; void go(int index, int selected, int n, int m) { if (selected == m) { for (int i = 0; i < n; i++) { for (int j = 1; j <= cnt[i]; j++) { cout << num[i] << ' '; } } cout << '\n'; return; } if (index >= n) return; for (int i = m - selected; i >= 1; i--) { cnt[index] = i; go(index + 1, selected + i, n, m); } cnt[index] = 0; go(index + 1, selected, n, m); } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; for (int i = 0; i < n; i++) { cin >> num[i]; } sort(num, num + n); go(0, 0, n, m); return 0; } |
cs |
<15663번 / N과 M (9)>
N개의 자연수 중에서 M개를 고른 수열을 모두 구하는 문제
5번 문제에서 중복제거를 해주면 된다.
sort함수를 통해 벡터를 정렬하고, unique함수를 통해 중복을 제거한 후 출력한다.
|
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 |
#include <iostream> #include <algorithm> #include <vector> using namespace std;; int num[10]; int a[10]; int c[10]; vector<vector<int>> d; void go(int index, int n, int m) { if (index == m) { vector<int> temp; for (int i = 0; i < m; i++) { temp.push_back(num[a[i]]); } d.push_back(temp); return; } for (int i = 0; i < n; i++) { if (c[i]) continue; c[i] = true; a[index] = i; go(index + 1, n, m); c[i] = false; } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; for (int i = 0; i < n; i++) { cin >> num[i]; } sort(num, num + n); go(0, n, m); sort(d.begin(), d.end()); d.erase(unique(d.begin(), d.end()), d.end()); for (auto &v : d) { for (int i = 0; i < m; i++) { cout << v[i] << ' '; } cout << '\n'; } return 0; } |
cs |
이번엔 선택 갯수로~
이 코드는 이해가 안간다.... 일단 넘어가고 다음에 더 고민해보자..ㅠㅠ
아 하나하나 써가면서 이해해부러따 키킥
|
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 |
#include <iostream> #include <algorithm> using namespace std; int cnt[10]; int num[10]; int a[10]; void go(int index, int n, int m) { if (index == m) { for (int i = 0; i < m; i++) { cout << a[i] << ' '; } cout << '\n'; return; } for (int i = 0; i < n; i++) { if (cnt[i] > 0) { cnt[i]--; a[index] = num[i]; go(index + 1, n, m); cnt[i]++; } } } int main() { int n, m; cin >> n >> m; int temp[10]; for (int i = 0; i < n; i++) { cin >> temp[i]; } sort(temp, temp + n); int k = 0; int c = 1; //숫자의 갯수(배열에 존재하는, 중복) int x = temp[0]; for (int i = 1; i < n; i++) { if (x == temp[i]) { c++; } else { cnt[k] = c; num[k] = x; c = 1; //c 초기화(c는 현재 수의 갯수) k++; x = temp[i]; //x가 입력받은 수 배열의 다음 숫자 } } cnt[k] = c; num[k] = x; n = k + 1; go(0, n, m); return 0; } |
cs |
<15664번 / N과 M (10)>
N개의 자연수 중에서 M개를 고른 수열을 모두 구하는 문제 (비내림차순)
-벡터로 중복 제거한거~ 그냥 전에 중복제거한거에서 start변수 추가하면 됨!
|
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 |
#include <iostream> #include <algorithm> #include <vector> using namespace std;; int num[10]; int a[10]; int c[10]; vector<vector<int>> d; void go(int index, int start, int n, int m) { if (index == m) { vector<int> temp; for (int i = 0; i < m; i++) { temp.push_back(a[i]); } d.push_back(temp); return; } for (int i = start; i < n; i++) { if (c[i]) continue; c[i] = true; a[index] = num[i]; go(index + 1, i+1, n, m); c[i] = false; } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; for (int i = 0; i < n; i++) { cin >> num[i]; } sort(num, num + n); go(0, 0, n, m); sort(d.begin(), d.end()); d.erase(unique(d.begin(), d.end()), d.end()); for (auto &v : d) { for (int i = 0; i < m; i++) { cout << v[i] << ' '; } cout << '\n'; } return 0; } |
cs |
-선택 사용하기 (이건 이전 문제에서 start로 바꿔주면 됨)
|
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 |
#include <iostream> #include <algorithm> using namespace std; int cnt[10]; int num[10]; int a[10]; void go(int index, int start, int n, int m) { if (index == m) { for (int i = 0; i < m; i++) { cout << a[i] << ' '; } cout << '\n'; return; } for (int i = start; i < n; i++) { if (cnt[i] > 0) { cnt[i]--; a[index] = num[i]; go(index + 1, i, n, m); cnt[i]++; } } } int main() { int n, m; cin >> n >> m; int temp[10]; for (int i = 0; i < n; i++) { cin >> temp[i]; } sort(temp, temp + n); int k = 0; int c = 1; //숫자의 갯수(배열에 존재하는, 중복) int x = temp[0]; for (int i = 1; i < n; i++) { if (x == temp[i]) { c++; } else { cnt[k] = c; num[k] = x; c = 1; //c 초기화(c는 현재 수의 갯수) k++; x = temp[i]; //x가 입력받은 수 배열의 다음 숫자 } } cnt[k] = c; num[k] = x; n = k + 1; go(0, 0, n, m); return 0; } |
cs |
<15665번 / N과 M (11)>
N개의 자연수 중에서 M개를 고른 수열을 모두 구하는 문제 (중복 선택 가능)
입력받은 수열에서 중복된 숫자 제거한 수열 새로 만들고 n 크기를 그 수열로 수정한 후 수열 만들어서 출력한다.
|
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 |
#include <iostream> #include <algorithm> using namespace std;; int num[10]; int a[10]; void go(int index, int n, int m) { if (index == m) { for (int i = 0; i < m; i++) { cout << a[i] << ' '; } cout << '\n'; return; } for (int i = 0; i < n; i++) { a[index] = num[i]; go(index + 1, n, m); } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; int temp[10]; for (int i = 0; i < n; i++) { cin >> temp[i]; } sort(temp, temp + n); int k = 0; int x = temp[0]; for (int i = 1; i < n; i++) { if (x != temp[i]) { num[k] = x; x = temp[i]; k++; } } num[k] = x; n = k + 1; go(0, n, m); return 0; } |
cs |
<15666번 / N과 M (12)>
N개의 자연수 중에서 M개를 고른 수열을 모두 구하는 문제 (중복 선택 가능, 비내림차순)
위이 문제에서 또 start만 추가했다
|
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 |
#include <iostream> #include <algorithm> using namespace std;; int num[10]; int a[10]; void go(int index, int start, int n, int m) { if (index == m) { for (int i = 0; i < m; i++) { cout << a[i] << ' '; } cout << '\n'; return; } for (int i = start; i < n; i++) { a[index] = num[i]; go(index + 1, i, n, m); } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; int temp[10]; for (int i = 0; i < n; i++) { cin >> temp[i]; } sort(temp, temp + n); int k = 0; int x = temp[0]; for (int i = 1; i < n; i++) { if (x != temp[i]) { num[k] = x; x = temp[i]; k++; } } num[k] = x; n = k + 1; go(0, 0, n, m); return 0; } |
cs |
이제 n과 m 그만,,,,,
'코딩테스트 > 알고리즘 기초 강의' 카테고리의 다른 글
| 1강 브루트 포스 - 재귀 (0) | 2020.09.03 |
|---|---|
| 1강 브루트 포스 - 순열 (0) | 2020.09.01 |
| 1강 브루트 포스 - 건너 뛰며 해보기 (0) | 2020.08.28 |
| 1강 브루트 포스 - 브루트 포스 (0) | 2020.08.27 |
| 4강 다이나믹 프로그래밍 1 - 연습 (0) | 2020.08.25 |
댓글