본문 바로가기

정수론26

[자바] 백준 2986 - 파스칼 (java) 문제 : boj2986 필요 알고리즘 개념 소수 판정 소수 판정 시 소수인지 알고 싶은 값 N에 대해 sqrt(N) 까지만 살펴보면 된다는 점을 알아야 풀 수 있다. 에라토스테네스의 체 혹은 소수판정 시 제곱근 까지만 확인하면 되는 이유 글에서 해당 개념을 익힐 수 있다. 수학, 정수론 기본적인 수학 지식이 있어야 풀 수 있다. 정확힌 나머지 연산에 대한 개념과 소수(prime number)가 무엇인지, 약수가 무엇인지 정도만 알면 된다. 나머지 연산 : 코드에서는 일반적으로 '%'로 표현된다. A%B는 A를 B로 나누고 남은 나머지를 뜻한다. A%B==0 이라면 B가 A의 약수임을 뜻한다. 소수(prime number) : 2이상의 자연수 중 1과 자기 자신만을 약수로 가지는 수이다. 예를들어 2,3,.. 2022. 8. 7.
[자바] 백준 10504 - 덧셈 (boj java) 문제 : boj10504 24의 경우 7+8+9가 답이다. 대충 봐도 중간 특정 지점에서 시작되는 숫자에 대해, 몇 개의 합인지도 지정되지 않은 상태로 연속되는 양의 정수의 구간을 찾기란 어려워 보인다. 개인적으로 수학이 약해서 정말 어려웠다 ㅠ. 약간 생각을 바꿔서, 그럼 중간부터 시작되지 않고 항상 1부터 시작된다고 해보자. 즉, a까지의 합이라고 하면 1+2+...+a 가 N이라고 하면 어떨까? 이건 상대적으로 쉬워보인다. a는 최대 44720이니깐(44720x44721/2 = 999,961,560 이고, 문제에서 제시된 입력값의 최대치가 10^9 이므로 최대 44720 까지만 보면 된다.), O(44720)으로 찾을 수 있다. 그리고 a를 2부터 44720까지 증가시키면서 확인해보면 '만약 여러 .. 2022. 7. 22.
[코틀린, 자바] 백준 14651 - 걷다보니 신천역 삼 (Large) (boj kotlin java) 문제 : boj14651 우선 3의 배수를 판정하는 방법부터 알아보자. 이 경우 수 A의 모든 자리의 숫자의 합이 3의 배수라면 A도 3의배수이다(정수론). 그럼 이 문제는 N자리 숫자에 대해, N번의 선택을 거친 결과 모든 자리 수의 합이 3의 배수인 경우의 수를 찾는 문제인 셈이다. 물론 단순하게 brute force로 찾아보려 한다면 O(3^33333)이 필요하므로 불가능하다. DP로 생각해보자. dp[a][b]를 a번째 자리수까지 더했을 때의 합을 3으로 나눈 나머지가 b인 경우의 수로 정해보자. 그럼 a가 5일때까지만 살펴보자. (N=5) 1. 우선 a=1 일 경우 다음과 같이 될 것이다. 또 이렇게 두면 '0으로 시작하는 수는 만들 수 없는 수 이삼' 부분을 별도로 처리하지 않아도 되기 때문에.. 2022. 7. 10.
[자바] 백준 1241 - 머리 톡톡 (boj java) 문제 : boj1241 에라토스테네스의 체 혹은 소수판정 시 제곱근 까지만 확인하면 되는 이유(글 링크) 이 글을 이해했다면 쉽게 풀 수 있다. N개를 입력받으면서 HashMap 등으로 각 숫자의 존재 여부 및 몇 개 존재하는지 저장해둔다. 이후 N개를 순회하면서 각각을 A라고 하면, 1부터 sqrt(A) 사이에 존재하는 A의 약수가 B라 하자. 그럼 HashMap에서 B의 개수를 더해주고, A/B도 약수일 것이므로 그것도 HashMap에서 찾아 더해주면 된다. 이 때 주의점은 sqrt(A)로 A가 나누어 떨어질 경우 (즉, (int)sqrt(A) * (int)sqrt(A) == A 인 경우), 두 번 더해지게 되므로 한 번은 빼줘야 한다. 그럼 시간복잡도는 N명 중 가장 큰 숫자가 K라 할 때, O(N.. 2022. 4. 28.
백준 9613 자바 - GCD 합 (boj 9613 java) 문제 : boj9613 우선 모든 쌍을 확인하는게 이 가능할지 확인해보자. n은 최대 100 이므로 모든 쌍을 확인할 경우 O(n^2)이 필요하고, 총 t개의 테스트케이스가 존재하므로 O(100*100^2) 이므로 충분히 가능하다. 그럼 뭐 어렵게 생각할 것 없이 무지성으로 모든 쌍을 확인해보면 된다. 모든 쌍 확인은 예를들어 배열의 길이가 5일 경우 인덱스는 0,1,2,3,4가 존재할 것이다. 그럼 0-1, 0-2, 0-3, 0-4, 1-2. 1-3. 1-4, 2-3, 2-4, 3-4 와 같이 확인하면 된다. 코드의 27~28line을 참고해보자. 그리고 모든 쌍에 대해 각각 GCD를 구해 그 결과를 더해주면 되는데, GCD의 경우 유클리드 호제법을 사용하면 빠르게 구할 수 이다. 유클리드 호제법은 검.. 2022. 4. 6.
백준 2749 자바 - 피보나치 수 3 (boj 2749 java) 문제 : boj2749 일단 10^18 이므로 그냥 구하기는 절대로 불가능한 수치임을 알 수 있다 ㅋㅋㅋ. 내 경우엔 피보나치의 경우 행렬의 거듭 제곱으로 풀 수 있다는걸 이미 알고 있었으므로 공식만 찾아서 풀었다. 공식은 f(n)이 n번째 피보나치라 할 때, 아래와 같다. 이 때 거듭 제곱의 계산은, 분할 정복을 활용해서 O(logN)에 빠르게 구할 수 있다. 예를들어 A^8 = ((A^2)^2)^2 임을 활용하는 것이다. 혹시 모른다면 예전에 백준 게시판에 답글달았던 이 글을 참고하면 된다. 그보다, 다른분의 풀이도 보다보니 '피사노 주기'라는 것도 알게 되었다. 피보나치 수를 어떠한 수로 나눈 나머지는 항상 주기성을 가진다고 한다. 수의 세계는 신비로운 것 같다. 코드 : github import .. 2022. 4. 5.

티스토리툴바