이번엔 배운 수학 알고리즘을 응용하는 문제를 풀어봅시다~
-최대공약수
> 유클리드 호제법
<9613번 / GCD 합>
유클리드 호제법을 통해 모든 쌍의 GCD를 구한다. 이 때 모든 쌍의 GCD를 구하기 위해 이중 for문을 사용한다. 그리고 모든 결과를 더하면 된다.
|
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 |
#include <iostream> #include <string> #include <algorithm> using namespace std; int gcd(int a, int b) { if (b == 0) return a; else return gcd(b, a%b); } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; int arr[100]; while (t--) { int n; cin >> n; for (int i = 0; i < n; i++) { cin >> arr[i]; } long long sum = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { sum += gcd(arr[i], arr[j]); } } cout << sum << '\n'; } return 0; } |
cs |
<17087번 / 숨바꼭질 6>
동생의 수가 1일 때만 예외처리를 해주고 다른 경우는 배열에 거리의 차를 저장한다. 이 때 abs함수를 통해 거리 차의 절댓값을 저장한다. 그리고 유클리드 호제법을 통해 모든 거리의 차의 GCD를 구한다.
|
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 <string> #include <cstdlib> using namespace std; #define MAX 100000 int arr[MAX]; int gcd(int a, int b) { if (b == 0) return a; else return gcd(b, a%b); } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, s; cin >> n >> s; if (n == 1) { int a; cin >> a; cout << abs(a - s) << '\n'; return 0; } for (int i = 0; i < n; i++) { int a; cin >> a; arr[i] = abs(a - s); } int g = gcd(arr[0], arr[1]); for (int i = 2; i < n; i++) { g = gcd(g, arr[i]); } cout << g << '\n'; return 0; } |
cs |
-진법 변환
이 파트는 알고리즘에서 크게 중요하게 다뤄지지 않는다고 한다. 그래도 연습문제는 풀어보자!
<1373번 / 2진수 8진수>
우선 2진수를 8진수로 바꾸는 방법은 2진수 뒤에서 부터 3개씩 끊어서 십진수로 변환하고 이를 붙히면 8진수가 된다. 그래서 반복문을 통해서 뒤에서부터 3개씩 잘라서 변환하였고, 그 결과를 stack에 넣은 뒤, 연산이 모두 끝나면 이를 string으로 형변한하여 출력하였다.
|
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 |
#include <iostream> #include <string> #include <stack> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); string str; cin >> str; stack<int> s; int index = str.length() - 1; string res; while (index>=0) { int bin = 1; int r = 0; for (int i = 0; i < 3; i++) { if (index < 0) break; if (str[index] == '1') { r += bin; } bin *= 2; index--; } s.push(r); } while (!s.empty()) { res += to_string(s.top()); s.pop(); } cout << res << '\n'; return 0; } |
cs |
<1212번 / 8진수 2진수>
음 고민해봤는데 8진수라 케이스가 8개밖에 없어서 그냥 swtich-case문으로 case나눠서 결과를 string으로 붙여버렸다. 단순하긴한데 이게 그나마 괜찮은것같다...흠... 사실 모르겠다ㅎㅎㅎ 그냥 이게 편해서 이렇게 했어ㅋㅋㅋ
|
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 <string> #include <stack> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); string str; cin >> str; if (str == "0") { cout << "0" << '\n'; return 0; } string res; int len = str.length(); for (int i = 0; i < len; i++) { switch (str[i]) { case '0': res += "000"; break; case '1': if (i == 0) res += "1"; else res += "001"; break; case '2': if (i == 0) res += "10"; else res += "010"; break; case '3': if (i == 0) res += "11"; else res += "011"; break; case '4': res += "100"; break; case '5': res += "101"; break; case '6': res += "110"; break; case '7': res += "111"; break; } } cout << res << '\n'; return 0; } |
cs |
<2089번 / -2진수>
이 문제는 음수 나누기만 조심하면 된다. 나눈 몫에 계속 -을 붙혀서 나눠주면 된다. 만약 2로 나눈 몫이 음수고, 나머지가 0이 아니라면 현재 몫에 1을 뺴주고 -를 붙혀서 재귀함수를 호출하여 해결한다. 이 문제는 이 방법을 이해하는데도 오래걸렸고, 재귀함수의 흐름을 이해하는데도 꽤 걸렸다. 주어진 코드를 우선 돌리면서 재귀함수의 흐름을 이해했는데 함수 내에서 재귀가 되면 그 동작을 마치고 순서대로 원래 자리로 돌아와서 그 다음단계를 실행하는 것이었다! 어찌보면 당연한 내용인데 아직도 재귀함수가 헷갈리는것같다... 연습해서 익숙해져야지! 그리고 이 문제는 출력이 자주 있기 때문에 cout대신 printf를 사용하여 속도를 높였다.
|
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 <stdio.h> void go(int n) { if (n == 0) return; if (n % 2 == 0) { go(-(n / 2)); printf("0"); } else { if (n > 0) go(-(n / 2)); else go(-(n - 1) / 2); printf("1"); } } int main() { int n; scanf("%d", &n); if (n == 0) printf("0"); else go(n); printf("\n"); return 0; } |
cs |
-소수
<17103번 / 골드바흐 파티션>
이 문제는 골드바흐 추측을 조금 수정하여 풀면 된다. 에라토스테네스의 체로 미리 소수를 구하고 골드바흐의 추측의 경우를 모두 세준다. 이 때 다른 조합의 경우 같은 경우가 2번 나오는거니까 2로 나눠주고 3+3과 같이 조합이 하나인거는 한번 더 더해줘서 전체 값을 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 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 |
#include <iostream> #include <vector> using namespace std; #define MAX 1000000 int arr[MAX]; vector<int> v; void erathostenes(void) { for (int i = 2; i < MAX; i++) { arr[i] = i; } for (int i = 2; i*i < MAX; i++) { if (arr[i] != 0) { for (int j = 2 * i; j <= MAX; j += i) { arr[j] = 0; } } } for (int i = 3; i < MAX; i++) { if (arr[i] != 0) { v.push_back(i); } } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); erathostenes(); int t, num; cin >> t; while (t--) { num = 0; int n; cin >> n; if (n == 0) break; for (int i = 2; i < n; i++) { if (arr[n - i] + arr[i] == n) { num++; if (n == 2 * i) num++; }
} cout << num/2 << '\n'; } } |
cs |
끝!!!!!
'코딩테스트 > 알고리즘 기초 강의' 카테고리의 다른 글
| 4강 다이나믹 프로그래밍 1 - 다이나믹 프로그래밍 소개 (0) | 2020.08.21 |
|---|---|
| 3강 수학 1 - 참고 (0) | 2020.08.20 |
| 2강 자료구조 1 - 참고 (0) | 2020.08.20 |
| 3강 수학 1 - 수학 1 (0) | 2020.08.19 |
| 2강 자료구조 1 - 연습 (0) | 2020.08.16 |
댓글