내일 개강이다... 이거 다 듣고 개강하고 싶었는데ㅠㅠ 오늘 밤새서 최대한 듣고 공부해보자!
아 졸려졸려졸려졸려졸려 자고싶은데 할거 너무 많아 이거 다들으려면 오늘 이거 다해야되는데 너무졸려졸려졸려
-------------------------------------------------------------------------------------------------------------------------------
순열은 문제 풀이를 할 때 순서가 중요한 의미를 가질때 사용하는 방법이다. 예를 들면 1-2-3과 1-3-2가 다른 것일때처럼
-순열 사용하기
우선 순열이란 임의의 수열을 다른 순서로 섞는 연산이다. 크기가 N인 수열의 서로 다른 순열은 총 N!개가 있다. 이 때 모든 순열을 사전순으로 나열했을 때 오는 첫순열은 오름차순이 되고, 마지막 순열은 내림차순이 된다.
먼저 다음 순열을 구하는 방법을 알아보자. 다음 순열을 구할 떄는 사전순으로 다음에 오는 순열과 이전에 오는 순열을 찾으면 된다. C++ STL의 algorithm에는 이미 다음순열을 구하는 함수인 next_premutation과 prev_permutation이 존재하기 때문에 그냥 이거 사용하면 된다. 근데 지금은 공부중이니까 직접 구현도 해보자!
다음 순열을 구할때 만약 A = {1, 2, 3, 4} 라는 수열이 있으면 1로 시작하는 순열 쭉 오고 그 다음엔 2로 시작하는거 ...오고 또 쪼개보면 1-2하고 쭉 오고 다음은 1-3하고 쭉오고... 뭐 이런식이다. 이 방법을 이용하는 것이다.
자 예를 들어 A = [7, 2, 3, 6, 5, 4, 1]이라고 하자. 음 자세한건 아래 사진 첨부할테니까 참고하도록
아래에서 <는 오름차순 >는 내림차순을 말한다. j는 다음순열을 찾을 때 바꿔줄 숫자? 를 의미한다.
그래서 다음순열을 구하는 방법을 정리하면 아래와 같고, 시간복잡도는 O(N)이 된다. 따라서 전체 순열을 모두 구하려면 순열의 숫자만큼 반복해야하기 때문에 전체 순열의 시간 복잡도는 O(N!*N)이다.
<10972번 / 다음 순열>
주로 다음 순열을 구하는 함수는 bool함수를 사용하는데 현재 순열이 마지막 순열인 경우에는 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 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
#include <iostream> #include <algorithm> using namespace std;; int a[10001]; bool next_permutation(int *a, int n) { int i = n - 1; while (i > 0 && a[i - 1] >= a[i]) //뒤에서부터 내림차순 판단 { i--; } if (i <= 0) //마지막 순열 return false; int j = n - 1; while (a[j] <= a[i - 1]) { j--; } swap(a[i - 1], a[j]); j = n - 1; while (i < j) { swap(a[i], a[j]); i++; j--; } return true; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; for (int i = 0; i < n; i++) { cin >> a[i]; } if (!(next_permutation(a, n))) cout << -1 << '\n'; else { for (int i = 0; i < n; i++) { cout << a[i] << ' '; } cout << '\n'; } return 0; } |
cs |
이번엔 STL 알고리즘에 있는거 써서 해보자~ 역시 기성품이 싸고 좋다니께~
|
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 |
#include <iostream> #include <algorithm> #include <vector> using namespace std;; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } if (next_permutation(a.begin(), a.end())) { for (int i = 0; i < n; i++) { cout << a[i] << ' '; } } else cout << -1; cout << '\n'; return 0; } |
cs |
<10973번 / 이전 순열>
이건 위의 코드에서 부등호만 바꾸면된다.
|
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 a[10001]; bool prev_permutation(int *a, int n) { int i = n - 1; while (i > 0 && a[i - 1] <= a[i]) //뒤에서부터 오름차순 판단 { i--; } if (i <= 0) //첫 순열 return false; int j = n - 1; while (a[j] >= a[i - 1]) { j--; } swap(a[i - 1], a[j]); j = n - 1; while (i < j) { swap(a[i], a[j]); i++; j--; } return true; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; for (int i = 0; i < n; i++) { cin >> a[i]; } if (!(prev_permutation(a, n))) cout << -1 << '\n'; else { for (int i = 0; i < n; i++) { cout << a[i] << ' '; } cout << '\n'; } return 0; } |
cs |
이것도 함수이름만 prev로 바꾸면 된다
|
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 |
#include <iostream> #include <algorithm> #include <vector> using namespace std;; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } if (prev_permutation(a.begin(), a.end())) { for (int i = 0; i < n; i++) { cout << a[i] << ' '; } } else cout << -1; cout << '\n'; return 0; } |
cs |
<10974번 / 모든 순열>
모든 순열을 구할 떄는 주로 do-while문을 사용한다. 이 함수는 중복된 숫자가 있어도 커버가 가능한 아주 기특한 함수이다. do while로 다음순열을 쭉구해서 쭉 출력하면 된다궁
|
#include <iostream> #include <algorithm> #include <vector> using namespace std;; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) { a[i] = i + 1; } do { for (int i = 0; i < n; i++) { cout << a[i] << ' '; } cout << '\n'; } while (next_permutation(a.begin(), a.end())); return 0; } |
-팩토리얼
모든 순열을 구하는 것의 시간 복잡도는 앞에서 말했다시피 O(N*N!)이다. 아래는 팩토리얼의 값을 나타낸거고 이를 통해서 모든 순열을 구할 수 있는 것은 10이 한계임을 알 수 있다. (1억이 넘어가면 너무 오래걸리기 때문) 이 점을 유의하며 문제들을 계속 풀어보자.
<10819번 / 차이를 최대로>
이 문제의 N의 범위는 8이하니까 모든 순열을 구해서 풀 수 있다. 문제에서 수의 순서만 변경할 수 있다고 하니까 이는 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 |
#include <iostream> #include <algorithm> #include <vector> using namespace std; int calculate(vector<int> &a) { int sum = 0; for (int i = 1; i < a.size(); i++) { sum += abs(a[i] - a[i - 1]); } return sum; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } sort(a.begin(), a.end()); int ans = 0; do { int temp = calculate(a); ans = max(ans, temp);
} while (next_permutation(a.begin(), a.end())); cout << ans << '\n'; return 0; } |
cs |
<10971번 / 외판원 순회 2>
Travelling Salesman Problem (TSP)라고 한다. 여기서 모든 도시를 거치고 한번 갔던 도시는 다시 갈수없다는 점에서 순열로 풀 수 있다. 이 문제도 제한이 10이기 때문에 모든 순열을 다 구해봐도 된다.
차이는 최대로 문제에서 calculate만 약간 바꿔주어 풀면 된다.
으휴 모지리야 문제에서 처음 도시로 돌아갈 수 있어야된다고 했으니까 조건이 w[d[n-1]][d[0]]이 0이 아닐때 안에서 ans의 최소값을 결정해줘야되는데 그걸 안해서 다섯번을 틀리고 겨우 오류 찾음 으휴으휴 똥멍청이 으이구
여기서 아래처럼 원래로 돌아와야 하는 외판원 순회 문제의 특성에 따라서 첫 시작 인덱스를 1로 고정해도 된다. 그러면 시간 복잡도는 O(N*(N-1)!)=O(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> #include <vector> using namespace std; int w[20][20]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> w[i][j]; } } vector<int> d(n); for (int i = 0; i < n; i++) { d[i] = i; } int ans = -1; do { bool ok = true; int sum = 0; for (int i = 0; i < n-1; i++) { if (w[d[i]][d[i + 1]] == 0) { ok = false; } else { sum += w[d[i]][d[i + 1]]; } } if (ok && w[d[n - 1]][d[0]] != 0) { sum += w[d[n - 1]][d[0]]; if (ans > sum || ans < 0) { ans = sum; } } } while (next_permutation(d.begin()+1, d.end())); cout << ans << '\n'; return 0; } |
cs |
<6603번 / 로또>
우선 next_permutation은 아래처럼 같은 수가 수열에 존재해도 문제 없이 사용할 수 있다.
입력으로 주어진 k개의 수 중에서 6개의 수를 고르는 문제이다. 이 문제를 숫자를 선택할지 말지로 나눠서 순열로 해결이 가능하다. 0을 k-6개, 1을 6개 넣은 다음 next)permutation을 수행하면 모든 조합을 구할 수 있다.
코드 구현해볼게융
for문 auto로 출력했다. 로또 알고리즘은 위에 한걸로 구현했다.
|
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 |
#include <iostream> #include <algorithm> #include <vector> using namespace std; int w[20][20]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); while (true) { int n; cin >> n; if (n == 0) break; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } vector<int> d; for (int i = 0; i < n - 6; i++) { d.push_back(0); } for (int i = 0; i < 6; i++) { d.push_back(1); } vector<vector<int>> ans; do { vector<int> cur; for (int i = 0; i < n; i++) { if (d[i] == 1) { cur.push_back(a[i]); } } ans.push_back(cur); } while (next_permutation(d.begin(), d.end())); sort(ans.begin(), ans.end()); for (auto &v : ans) { for (int i = 0; i < v.size(); i++) { cout << v[i] << ' '; } cout << '\n'; } cout << '\n'; }
return 0; } |
cs |
다해따!
'코딩테스트 > 알고리즘 기초 강의' 카테고리의 다른 글
| 2강 - 그래프 1 (1) (0) | 2020.12.29 |
|---|---|
| 1강 브루트 포스 - 재귀 (0) | 2020.09.03 |
| 1강 브루트 포스 - N과 M (0) | 2020.08.29 |
| 1강 브루트 포스 - 건너 뛰며 해보기 (0) | 2020.08.28 |
| 1강 브루트 포스 - 브루트 포스 (0) | 2020.08.27 |
댓글