본문 바로가기

Algorithm/Math

 (97)
(C++) - 백준(BOJ) 9020번 : 골드바흐의 추측 답 www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 아리스토테네스의 체를 이용해 푸는 문제였습니다. 풀이방법 1. 아리스토테네스의 체로 소수가 아닌 수들을 체크한다. 2. 서로 다른 두 소수들 중 가장 작은 차이가 나는 경우는 두 소수가 각각 n/2일 경우다. 따라서 차이가 가장작은 n/2를 중앙으로 i, n-i를 차례대로 보면서 정답을 갱신해나가면 차이가 최소인 두 소수가 나온다. Code #include #define fastio ios_..
(C++) - 백준(BOJ) 1011번 : Fly me to the Alpha Centauri 답 https://www.acmicpc.net/problem/1011 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행�� www.acmicpc.net 풀이방법 : distance = y - x 마지막은 무조건 1광년을 선택해야 한다. 거리,선택한 광년의 흐름,선택횟수 순으로 정리해봤습니다. 01 : 1 선택횟수 : 1 02 : 1 -> 1 선택횟수 : 2 03 : 1 -> 1 -> 1 선택횟수 : 3 04 : 1 -> 2 -> 1 선택횟수 : 3 수의 증감이 ^형태로 되어 있어 대칭을 이룰 때 2..
(C++) - 백준(BOJ) 2998번 : 8진수 https://www.acmicpc.net/problem/2998 2998번: 8진수 문제 창영이는 여러 가지 진법을 공부하고 있다. 창영이는 어제 2진법을 배웠고, 오늘은 8진법을 배웠다. 이제, 2진법 수를 8진법 수로 변환하려고 한다. 창영이가 사용한 방법은 다음과 같다. 2진수의 길이가 3으로 나누어 떨어질 때 까지 수의 앞에 0을 붙인다. 그 다음, 3자리씩 그룹을 나눈다. 아래의 표를 참고해 8진수로 바꾼다. 2진수가 주어졌을 때, 창영이가 사용한 방법을 이용해 8진수로 바꾸는 프로그램을 작성하시오. 000 0 001 1 010 www.acmicpc.net 간단한 진법 변환 문제였습니다. 12345678910111213141516171819202122232425262728293031323334..
(C++) - 백준(BOJ) 1789번 : 수들의 합 https://www.acmicpc.net/problem/1789 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net 서로 다른 n개의 자연수의 합이 s n의 최대 : 가장 작은 수부터 더해서 s가 될 경우 12345678910111213141516171819202122#include #define ll long longusing namespace std;int main() { ll n; ll ans = 0; ll sum = 0; cin >> n; for (ll i = 1; sum
(C++) - 백준(BOJ) 1010번 : 다리놓기 https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 조합 문제였습니다. 풀이방법 겹치지 않게 다리를 놓는 방법은 순서에 상관없이 뽑는 조합의 방식과 유사합니다. m개 중 n개를 뽑는 경우의 수를 출력하면 됩니다. Code #include using namespace std; int t; int comb[31][31]; int dfs(int n, int k){ if(n == k || k == 0) return 1; int &ret = comb[n][..
(C++) - 백준(BOJ)코딩 11758번 : CCW 답 www.acmicpc.net/problem/11758 11758번: CCW 첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다. www.acmicpc.net 대표적인 기하 알고리즘 중 하나인 CCW입니다. ※CCW : p1,p2,p3 점에서 볼 때 선분p1p2, 선분p2p3의 외적을 이용합니다. ※외적의 정의 : AXB = a*b*sina로 정의 되는데 이뜻은 vector A를 기준으로 vector B가 얼마나 회전하려는 성질을 가지고 있는지를 표시하는 척도라고 볼 수 있습니다. 따라서 외적의 값이..
(C++) - 백준(BOJ) 2942번 : 퍼거슨과 사과 #include #include using namespace std; int GCD(int a, int b)//가짓수는 r,g의 최대공약수의 약수의 개수 { if (b == 0) { return a; } return GCD(b, a%b); } int main() { int r, g; cin >> r >> g; int gcd = GCD(r, g); for (int i = 1; i
(C++) - 백준(BOJ) 2960번 : 에라토스테네스의 체 https://www.acmicpc.net/problem/2960 2960번: 에라토스테네스의 체 2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다. www.acmicpc.net 에라토스테네스의 체를 구현하는 문제였습니다. Code #include using namespace std; int n, k, cnt, c[1001],ans; int main() { cin >> n >> k; for (int i = 2; i

티스토리툴바