본문 바로가기
반응형

PS/백준

 (318)
[BOJ] 백준 17103 골드바흐 파티션 (Swift) 문제 https://www.acmicpc.net/problem/17103 17103번: 골드바흐 파티션 첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다. www.acmicpc.net 풀이 짝수 n을 두 소수의 합으로 나타낼 수 있는 경우의 수를 구해야하는 문제입니다. 또한 순서만 다른 것은 제외해야합니다. (3 + 7, 7 + 3) 그렇다면 먼저 소수인 수들을 구해주어야겠죠? n이 최대 1,000,000 입니다. 1,000,000 이하의 소수들을 전부 구해줍시다. 그리고 이 소수들의 합으로 n을 나타낼 수 있다면 하나씩 세어주면 되지 않을까요? ...아닙니다... 1,00..
[BOJ] 백준 4948 베르트랑 공준 (Swift) 문제 https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 풀이 n보다 크고 2 * n 보다 작거나 같은 소수의 개수를 출력하는 문제입니다. 에라토스테네스의 체 알고리즘을 사용하여 소수들을 구할 수 있습니다. n이 최대 123,456 이므로, 에라토스테네스의 체 알고리즘을 사용하여 123,456 * 2 만큼의 소수들을 한 번에 구해줍시다. 그 이후, n + 1 부터 2 * n 까지의 소수들의 개수를 출력해주면 됩니다. 고차함수 filter를 ..
[BOJ] 백준 1929 소수 구하기 (Swift) 문제 https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 풀이 m이상 n이하의 소수를 모두 출력하는 문제입니다. 에라토스테네스의 체 알고리즘을 사용하면 쉽게 풀이할 수 있습니다. https://dev-mandos.tistory.com/93 [알고리즘] 에라토스테네스의 체 (Swift) 에라토스테네스의 체 에라토스테네스의 체 알고리즘은 고대 그리스 수학자인 에라토스테네스가 만들어낸 소수를 찾는 알고리즘 입니다. 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네 dev-mando..
[BOJ] 백준 4134 다음 소수 (Swift) 문제 https://www.acmicpc.net/problem/4134 4134번: 다음 소수 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. www.acmicpc.net 풀이 n을 입력받은 후, n보다 크거나 같은 소수 중 가작 작은 소수를 출력해야합니다. 2부터 n - 1까지 나누어보고 나누어 떨어진다면 소수가 아니라고 판별할 수 있습니다. 이 방식은 $O(n)$의 시간 복잡도가 소요됩니다. 2부터 $\sqrt{n}$ 까지만 나누어 떨어지는지 확인해도 동일한 결과입니다. 이 방식은 $O(\sqrt{n})$의 시간 복잡도가 소요됩니다. 아래 포스팅에 정리를 해두었습니다. https://dev-mandos.tistory.com/91 [알고리즘..
[BOJ] 백준 2485 가로수 (Swift) 문제 https://www.acmicpc.net/problem/2485 2485번: 가로수 첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3 ≤ N ≤ 100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가 www.acmicpc.net 풀이 모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수를 구하는 문제입니다. 어떻게 모두 같은 간격이 되도록 할 수 있을까요? (4, 8, 10, 14)에 가로수가 심어져있다고 가정하면, 간격은 (4, 2, 4) 가 될 것입니다. 모두 같은 간격을 갖으려면 2가 되겠네요. (6, 12)에 심어야 모든 가로수가 2의 간격을 갖게 될 것입니다. 그렇다면 간격중 가장 작은..
[BOJ] 백준 1735 분수 합 (Swift) 문제 https://www.acmicpc.net/problem/1735 1735번: 분수 합 첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 입력되는 네 자연수는 모두 30,000 이하이다. www.acmicpc.net 풀이 두 분수의 합을 기약분수 형태로 구하는 코드를 작성하면 됩니다 두 분수의 합은 어떻게 구할 수 있을까요? $$\frac{2}{3} + \frac{5}{6} = \frac{2 \times 6 + 3 \times 5}{3 \times 6} = \frac{27}{18}$$ 와같이 구할 수 있습니다. 이를 기약분수 형태로 나타내려면.. 27과 18의 최대공약수로 각각 나누어 주면 되겠죠? 최대공약수는 유클리드 호제법을 사용하여 구할 수 있습니다...
[BOJ] 백준 13241 최소공배수 (Swift) 문제 https://www.acmicpc.net/problem/13241 13241번: 최소공배수 정수 B에 0보다 큰 정수인 N을 곱해 정수 A를 만들 수 있다면, A는 B의 배수이다. 예: 10은 5의 배수이다 (5*2 = 10) 10은 10의 배수이다(10*1 = 10) 6은 1의 배수이다(1*6 = 6) 20은 1, 2, 4,5,10,20의 배수이다. 다 www.acmicpc.net 풀이 https://dev-mandos.tistory.com/156 [BOJ] 백준 1934 최소공배수 (Swift) 문제 https://www.acmicpc.net/problem/1934 1934번: 최소공배수 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배..
[BOJ] 백준 1934 최소공배수 (Swift) 문제 https://www.acmicpc.net/problem/1934 1934번: 최소공배수 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있 www.acmicpc.net 풀이 최소공배수는 어떻게 구할 수 있을까요? 최소공배수는 두 수의 곱 / 최대공약수로 구할 수 있습니다. 그렇다면 최대공약수는 어떻게 구할 수 있을까요? 최대공약수는 소인수분해를 하여 공통된 소수를 찾아서 구할 수도 있겠지만, 유클리드 호제법을 사용하면 더 효율적으로 구현할 수 있습니다. 유클리드 호제법은 나머지를 구하는 연산을 통해 구현하는데, 간단하게 12와 30이 있..
반응형

티스토리툴바