본문 바로가기

정수론24

[자바] 백준 16563 - 어려운 소인수분해 (java) 목차 문제 : boj16563 필요 알고리즘 정수론, 소수 판정, 에라토스테네스의 체 에라토스테네스의 체를 사용해 소수를 구한 후 소인수분해를 해서 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 백준 3142를 풀면서 좀 더 개선된 소인수분해 테크닉을 익히게 되어, 민상님의 소개로(?) 풀어본 관련 문제이다. 코드 1은 기존에 내가 쓰던방식으로 푼 코드이고, 코드 2가 개선된 소인수분해 테크닉으로 짜본.. 2024. 2. 23.
[자바] 백준 3142 - 즐거운 삶을 위한 노력 (java) 목차 문제 : boj3142 필요 알고리즘 정수론, 소수 판정, 에라토스테네스의 체 에라토스테네스의 체를 사용해 소수를 구한 후 소인수분해를 해서 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 어떤 수가 완전제곱수인지 우선 생각해보자. 내가 풀이를 위해 생각한 완전제곱수 판정은, 소인수 분해 후 각 소인수의 개수가 모두 짝수라면 완전제곱수가 가능하다는 점을 이용하는 것이었다. 예를들어서 예제 입력 2를.. 2024. 2. 23.
[자바] 백준 7588 - Amicable (java) 목차 문제 : boj7588 필요 알고리즘 수학, 정수론 약수 구하는 것과 관련된 정수론 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 N이 최대 백만이고, 테스트케이스가 존재한다. 따라서 미리 백만까지의 모든 Amicable 쌍을 구해둔 후, 각 테스트케이스마다 알맞게 출력해주면 된다. 여기서 구현이 필요한 부분은 결국 어떠한 수가 주어졌을 때, 그 수의 모든 제수의 합을 구하는 녀석이 필요하다. 이 때, 주어진.. 2024. 2. 19.
[자바] 백준 16400 - 소수 화폐 (java) 목차 문제 : boj16400 필요 알고리즘 에라토스테네스의 체, DP (동적 계획법), 냅색 (배낭 문제), 정수론 에라토스테네스의 체로 소수를 전처리 후, 냅색 DP를 돌려서 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 순서대로 생각해보자. 1. N이하의 화폐를 모두 알아야 한다. -> 에라토스테네스의 체 등으로 N 이하의 모든 소수를 미리 구해두자. sqrt(N) 까지만 확인해본 이유는 '에라토스테네스의.. 2023. 12. 15.
[자바] 백준 20500 - Ezreal 여눈부터 가네 ㅈㅈ(java) 목차 문제 : boj20500 필요 알고리즘 동적 계획법 (DP), 정수론 정수론 특히 나머지 연산의 성질에 대해 알아야 하고, 효율적으로 풀기 위해 DP가 필요하다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 아래와 같이 자리수를 늘려나가 만들어지는 N자리 양의 정수 중 15의 배수가 몇 개인지 구하는 문제이다. 당연하게도 1과 5로 이루어진 N자리 수는 2^N 개나 된다. 2^1515개의 정수는 천문학적인 수치이므로 .. 2023. 12. 5.
[자바] 백준 1612 - 가지고 노는 1 (java) 목차 문제 : boj1612 필요 알고리즘 수학, 정수론 나머지 연산의 성질을 알고 있어야 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 N의 실제 배수를 계산하면서 전부 1로만 이루어져 있는지 확인하는건 상당히 난감하다. 반대로 생각해보자. 결국 1, 11, 111, 1111, .... 이런 수가 결국 N으로 나누어 떨어진다면 N의 배수인거다. 이 경우엔 좀 쉬워진다. 그냥 1, 11, 111, ... 이런 .. 2023. 12. 4.
[자바] 백준 1684 - 같은 나머지 (java) 목차 문제 : boj1684 필요 알고리즘 정수론, 유클리드 호제법 의외로 GCD 문제이다! ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 N이 2인 경우만 생각해보자. 문제에서 입력된 어떠한 정수 2개를 N1, N2라고 하면, R1==R2가 되려면 아래처럼 식이 전개될 것이다. 따라서 N2-N1 즉, 두 수의 차이는 정수인 Q2-Q1과 D의 곱이 된다. 이 때 Q2-Q1이 뭔지는 모르겠지만 아무튼 정수인 D가 가장 크.. 2023. 7. 25.
[자바] 백준 7481 - ATM놀이 (java) 문제 : boj7481 필요 알고리즘 개념 정수론, 수학 나머지 연산을 사용해 풀 수 있다. 비둘기집의 원리 현재는 테스트케이스가 너무 빈약해서 의미 없지만, 테스트케이스 추가 시 통과하려면 비둘기집의 원리로 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 a와 b 중 큰 수를 hi, 작은 수를 lo 라고 해보자. 우선 가장 적은 수의 지폐를 만들려면, 가능한 경우의 수 중 hi가 가장 큰 경우를 찾아야 한다. .. 2023. 1. 31.
[자바] 백준 2859 - 별 관찰 (java) 문제 : boj2859 필요 알고리즘 개념 수학, 정수론, 브루트포스 수식을 정리해 브루트포스로 모든 경우를 살펴보면서 나누어떨어지는 경우를 찾아야한다. 비둘기집의 원리 좀 더 명확하게 횟수를 지정하고 싶거나, 몇 번 해야 Never인지 따로 판단하지 않으려면 이게 필요하다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 시간과 분으로 된 문자열은 처리하기가 상당히 까다롭다. 그러니 우선 정수로 변환하기 위해 입력값을 .. 2023. 1. 30.
[자바] 백준 1323 - 숫자 연결하기 (java) 문제 : boj1323 필요 알고리즘 개념 수학, 정수론 나머지 연산의 법칙을 활용하는 수학문제이다. 비둘기집의 원리 불가능한 경우를 알기 위해 비둘기집의 원리를 사용해야 한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 N이 10억까지 가능한데, 이걸 3번만 붙여도 long 으로 표현 가능한 수치를 넘어간다. BigInteger를 사용해 뭔가를 구하게되면 결국 문자열로 처리하는 것이므로 연산 속도가 엄청나게 느려진다. .. 2023. 1. 21.