https://www.acmicpc.net/problem/1017 1017번: 소수 쌍 지민이는 수의 리스트가 있을 때, 이를 짝지어 각 쌍의 합이 소수가 되게 하려고 한다. 예를 들어, {1, 4, 7, 10, 11, 12}가 있다고 하자. 지민이는 다음과 같이 짝지을 수 있다. 1 + 4 = 5, 7 + 10 = 17, 11 + www.acmicpc.net 난이도 : 플래티넘 3 태그 : 수학, 정수론, 소수 판정, 에라토스테네스의 체, 이분 매칭 설명 소수 판정 + 이분 매칭 문제입니다. 이분 매칭에 관해서는 아래 글을 참고해주세요. https://uknowblog.tistory.com/444 [알고리즘] 이분 매칭 (Bipartite Matching) 이분 매칭을 간단히 이야기하면 연애 매칭 프로..

https://www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 난이도 : 골드 4 태그 : 수학, 그래프 이론, 그래프 탐색, 정수론, 너비 우선 탐색, 소수 판정, 에라토스테네스의 체 설명 한 번에 한 글자씩 수를 바꿀 수 있으며, 바꾼 숫자는 소수여야 합니다. 목표 숫자로 바꾸는 최소 횟수를 출력하는 문제입니다. 너비 우선 탐색(BFS)을 사용해 '숨바꼭질' 문제와 같이 최단 경로(최소 횟수)를 찾는 문제입니다. https://www.acmicpc.net/prob..

https://www.acmicpc.net/problem/20302 20302번: 민트 초코 상원이가 고른 디저트가 “민트 초코”인 경우 mint chocolate, “치약”인 경우 toothpaste를 출력한다. www.acmicpc.net 난이도 : 골드 4 태그 : 수학, 정수론, 소수판정, 에라토스테네스의채 설명 상당히 어려웠던 문제였습니다 그냥 단순히 입력으로 주어지는 연산을 그대로 했더니 당연하게 시간초과 발생하였고, *, / 연산을 각각 리스트로 만들어 6 -> 2 * 3, 10 -> 2 * 5와 같이 소인수 분해 한 후, 각각에 리스트에 넣어준 뒤 (첫 항은 *로 처리), * 연산이 남아있으면 유리수, / 연산이 남아있으면 유리수로 판단하였습니다. 6 / 4 = (3 * 2) / (2 * ..

https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 난이도 : 실버 1 태그 : 수학, 정수론, 소수 판정, 에라토스테네스의 체 설명 골드바흐 추측은 4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다. 라는 추측입니다. 아직 수학적으로 증명되지 않았기에 추측이라고 불립니다. 4보다 큰 짝수를 두 홀수 소수의 합으로 나타낼 수 있을 경우, 두 소수의 차이가 가장 큰 두 수를 출력, 나타낼 수 없을 경우 "Goldb..

https://www.acmicpc.net/problem/1747 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 난이도 : 실버 1 태그 : 수학, 브루트포스 알고리즘, 정수론, 소수 판정, 에라토스테네스의 체 설명 소수이면서, 동시에 팰린드롬인 수를 찾는 문제입니다. 팰린드롬은 그냥 단순히, 문자열을 뒤집었을 때 같은 문자열 (ex> 토마토, 기러기)을 팰린드롬이라고 합니다. 해당 문제에서는 에라토스테네스의 채가 유용하게 쓰일 것 같네요. 에라토스테네스의 채? http..

https://www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 난이도 : 골드 5 태그 : 수학, 정수론, 백트래킹, 소수 판정 설명 백트래킹 + 소수판정 문제입니다. 백트래킹으로 수열을 구한 뒤, 수열을 숫자로 바꿔 해당 숫자가 소수인지 판단하였습니다. 소스코드 시간초과 var n = -1 lateinit var nums: Array val sb = StringBuilder() fun main() { n = readln().toInt() nums..

https://www.acmicpc.net/problem/2581 2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net 난이도 : 실버 5 태그 : 수학, 정수론, 소수 판정 설명 소수는 자기 자신과 1로만 나뉘는 수 입니다. 따라서 2 부터 자기 자신까지 나뉘눈 수가 있는지 판단하면 됩니다. 소스코드 a = int(input()) b = int(input()) lst = list() for i in range(a, b+1): lst.append(i) for i in range(len(lst)): check = False n..

https://uknowblog.tistory.com/117 [백준 1253번] [Kotlin] 좋다 https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 난이도 : 골드 4 uknowblog.tistory.com 난이도 : 브론즈 1 태그 : 수학, 정수론, 유클리드 호제법 설명 가장 오래된 알고리즘인 유클리드 호제법을 사용해 풀 수 있습니다. 해당 알고리즘에 관해서는 백준 2069번 - 최대공약수와 최소공배수 포스팅을 참고해주세요. https://uknowblog.tisto..

https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 난이도 : 실버 5 태그 : 정수론, 수학, 소수판정 설명 https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 주어진 n개의 수 중 소수를 찾는 문제입니다. 소수를 판단하는 방법은, 2부터 해당 수 - 1까지 나눠진다면 소수입니다. 소스코드 re = int(input()) nu..

https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 난이도 : 브론즈 1 태그 : 수학, 정수론, 소수 판정 설명 N에 대해 소인수분해를 하는 문제입니다. 소인수분해 과정은 꽤 간단합니다. 60을 소인수분해 한다 했을때, 60 / 2 = 30 이며, 30 / 2 = 15 입니다. 2로는 더 이상 나눠지지 않으니 3으로 나눠봅시다. 15 / 3 = 5 이며, 더 이상 3으로 나누어지지 않고, 4로도 나누어지지 않습니다. 5 / 5 = 1 입니다. 이와 같이 60을 소인수분해 하면 2 * 2 * 3 * 5 = 60을 구할 수 있습니다. 소스코드 fun main() { v..