수학11 [백준] 1963번 - 소수 경로 (C++) 문제 및 풀이 문제) 백준 - BFS - 소수 경로 https://www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 주어진 첫 소수의 한 자리를 바꾸어 두 번째 소수를 만들 수 있는 최소 변환 수를 구하는 문제였습니다. 에라토스테네스의 체를 활용하여 10000 이하에 대하여 소수 판별(isPrime)을 진행합니다. 그 후 주어진 수의 첫자리부터 4번째 자리까지 변환하면서 소수이면서 방문하지 않은 수에 대하여 queue에 push 하여 BFS를 진행합니다. C++ 소스 코드) Full.. 2022. 3. 16. [백준] 21920번 - 서로소 평균 (C++) 문제 및 풀이 문제) 백준 - 수학 - 서로소 평균 https://www.acmicpc.net/problem/21920 21920번: 서로소 평균 첫 번째 줄에 입력될 수들의 개수 $N$이 주어진다. $(2 \le N \le 500,000)$ 두 번째 줄에는 수열 $A$를 이루는 자연수 $A_{i}$ 가 공백으로 구분되어 주어진다. $(2 \le A_{i} \le 1,000,000)$ 수열 $A$에 $X$와 서로 www.acmicpc.net 서로소를 만족하는 수들의 평균을 구하는 문제였습니다. 유클리드 호제법을 통해 서로소를 판별합니다. C++ 소스코드) 2022. 3. 11. [백준] 22943번 - 수 (Python) 문제 및 풀이 문제) 백준 - 수학 - 수 https://www.acmicpc.net/problem/22943 22943번: 수 0부터 9까지 $K$가지의 숫자를 한 번씩만 사용하여 만들 수 있는 수 중 아래 조건을 모두 만족하는 수들의 개수를 구해보자. 단, 수의 맨 앞에는 0이 올 수 없다. 즉, 0143는 불가능하다. 서로 다른 www.acmicpc.net 소수 판별을 이용해 다양한 조건을 만족하는 수의 개수를 찾는 문제였습니다. 0부터 9까지 K개로 이루어진 수를 찾기 위해 itertools에 내장된 permutation을 활용했습니다. 만약 뽑힌 수의 앞 수가 0일 경우 만족하지 않으므로 무시합니다. 그 후, 에라토스테네스의 체를 활용한 소수 판별을 바탕으로 문제에 주어진 조건대로 확인합니다. Python 소.. 2022. 3. 2. [백준] 11687번 - 팩토리얼 0의 개수 (C++) 문제 및 풀이 문제) 백준 - 수학 - 팩토리얼 0의 개수 https://www.acmicpc.net/problem/11687 11687번: 팩토리얼 0의 개수 첫째 줄에 M (1 ≤ M ≤ 100,000,000)이 주어진다. www.acmicpc.net 팩토리얼에서 0의 개수는 5의 개수에 영향을 받습니다. 1부터 MAX까지 5*1부터 5*MAX까지 5의 개수를 세어줍니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Solution/11687_%ED%8C%A9%ED%86%A0%EB%A6%AC%EC%96%BC0%EC%9D%98%EA%B0%9C%EC%88%98.cpp GitHub - Chocochip101/BOJ_Solution.. 2022. 2. 22. [백준] 5618번 - 공약수 (C++) 문제 및 풀이 문제) 백준 - 수학 - 공약수 https://www.acmicpc.net/problem/5618 5618번: 공약수 첫째 줄에 n이 주어진다. n은 2 또는 3이다. 둘째 줄에는 공약수를 구해야 하는 자연수 n개가 주어진다. 모든 자연수는 108 이하이다. www.acmicpc.net 숫자들의 모든 공약수를 구하는 문제였습니다. 모든 숫자들에 대해 최대 공약수를 구하여 그 최대 공약수의 약수들을 출력하면 해결할 수 있습니다. C++ 소스코드) 2022. 2. 21. [백준] 21919번 - 소수 최소 공배수 (C++) 문제 및 풀이 문제) 백준 - 수학 - 소수 최소 공배수 https://www.acmicpc.net/problem/21919 21919번: 소수 최소 공배수 수열 중에 소수는 2, 3, 5가 있다. www.acmicpc.net N개의 숫자 배열 A를 입력받아 각 숫자의 소수 판별 후 최소 공배수를 구하면 해결할 수 있었습니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Solution/21919_%EC%86%8C%EC%88%98%EC%B5%9C%EC%86%8C%EA%B3%B5%EB%B0%B0%EC%88%98.cpp GitHub - Chocochip101/BOJ_Solution: BOJ Solutions BOJ Solutions.. 2022. 2. 18. [백준] 21000번 - Archer Vlad (C++) 문제 및 풀이 문제) 백준 - 물리학 - Archer Vlad https://www.acmicpc.net/problem/21000 2022. 2. 10. [백준] 9421번 - 소수상근수 (C++) 문제 및 풀이 문제) 백준 - 에라토스테네스의 체 - 소수상근수 https://www.acmicpc.net/problem/9421 9421번: 소수상근수 양의 정수 n의 각 자리수의 제곱의 합을 계산한다. 그렇게 해서 나온 합도 각 자리수의 제곱의 합을 계산한다. 이렇게 반복해서 1이 나온다면, n을 상근수라고 한다. 700은 상근수이다. 72 + 02 + 02 = www.acmicpc.net 1부터 N까지 차례로 소수와 상근수 판별을 하여 둘 다 만족할 경우 출력합니다. 소수 판별은 에라토스테네스의 체를 활용하여 해결했습니다. 상근수는 판별은 상근수 변환을 이용하여 변환할 때마다 set에 insert 합니다. 만약, set에 변환된 숫자가 존재할 경우 cycle이 돌아 상근수가 아니므로 false를 return 합니.. 2022. 2. 9. [백준] 17128번 - 소가 정보섬에 올라온 이유 (C++) 문제 및 풀이 문제) 백준 - 수학 - 소가 정보섬에 올라온 이유 https://www.acmicpc.net/problem/17128 17128번: 소가 정보섬에 올라온 이유 첫째 줄에 소의 수를 나타내는 N과 욱제가 장난칠 횟수 Q가 주어진다. (4 ≤ N ≤ 200,000, 1 ≤ Q ≤ 200,000) 둘째 줄에 N마리 소들의 품질 점수 Ai가 순서대로 주어진다. (1 ≤ |Ai| ≤ 10) 셋째 줄에 www.acmicpc.net Brute Force(완전 탐색)으로 해결할 시, N이 최대 20만이기 때문에 TLE로 틀립니다. parSum[idx] : idx부터 4마리 소들의 품질 점수의 곱 idx(i) : 인덱스 처리 함수 ans : 쿼리 후 품질 점수 부분합을 저장하여 쿼리로 소의 품질점수가 Update될때마.. 2022. 1. 28. 이전 1 2 다음 반응형
