본문 바로가기

수학111

[자바] 백준 17436 - 소수의 배수 (java) 목차 문제 : boj17436 필요 알고리즘 포함 배제의 원리 (inclusion and exclusion) 포함 배제의 원리로 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 예제 입력 2를 생각해보자. 2 100 2 3 직관적으로 우린 이걸 푸는 방법을 알고 있다. 100 이하의 자연수 중 2로 나누어 떨어지는 수는 100/2 = 50개가 존재한다. 그리고 3으로 나누어떨어지는건 100/3 = 33개.. 2024. 2. 24.
[자바] 백준 7588 - Amicable (java) 목차 문제 : boj7588 필요 알고리즘 수학, 정수론 약수 구하는 것과 관련된 정수론 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 N이 최대 백만이고, 테스트케이스가 존재한다. 따라서 미리 백만까지의 모든 Amicable 쌍을 구해둔 후, 각 테스트케이스마다 알맞게 출력해주면 된다. 여기서 구현이 필요한 부분은 결국 어떠한 수가 주어졌을 때, 그 수의 모든 제수의 합을 구하는 녀석이 필요하다. 이 때, 주어진.. 2024. 2. 19.
[자바] 백준 30025 - K의 배수 (java) 목차 문제 : boj30025 필요 알고리즘 DP (동적 계획법), 수학 DP를 이용해 풀 수 있는 문제이다. 풀이를 위해 수학적인 지식이 필요하다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 M자리의 양의 정수를 구하고, 그 중 K의 배수가 몇 개인지 구하는 문제이다. 물론 실제로 가능한 모든 M자리 양의 정수를 구해보면 O(N^M) = O(10^100) 이라는 천문학적인 경우의수가 되므로 불가능하다. 그럼 어떻게.. 2023. 12. 12.
[자바] 백준 1612 - 가지고 노는 1 (java) 목차 문제 : boj1612 필요 알고리즘 수학, 정수론 나머지 연산의 성질을 알고 있어야 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 N의 실제 배수를 계산하면서 전부 1로만 이루어져 있는지 확인하는건 상당히 난감하다. 반대로 생각해보자. 결국 1, 11, 111, 1111, .... 이런 수가 결국 N으로 나누어 떨어진다면 N의 배수인거다. 이 경우엔 좀 쉬워진다. 그냥 1, 11, 111, ... 이런 .. 2023. 12. 4.
[자바] 백준 14257 - XOR 방정식 (java) 목차 문제 : boj14257 필요 알고리즘 조합론, 수학 수학적인 직관이 필요한 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 당연히 S와 X를 숫자 그 자체로 생각해보면 딱히 할 수 있는게 없다. 그리고 A+B=S야 그렇다 쳐도, A^B=X 는 어차피 비트단위로 연산되는 녀석이라, 비트단위로 봐야 뭔가 보일꺼라 생각했다. 그래서 비트로 변경해두고 보다보니 풀이가 보여서 풀게 되었다. 일단 당연하게도 A^B의 결.. 2023. 8. 11.
[자바] 백준 28251 - 나도리합 (java) 목차 문제 : boj28251 필요 알고리즘 수학, 분리 집합 (disjoint set, union-find) 기본적인 아이디어는 수학적 직관이 좀 필요하고, 그 직관을 구현하기 위해 분리 집합 알고리즘을 사용해야 하는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 4개의 수 a,b,c,d가 있다고 해보자. a와 b를 합치면 ab, c와 d를 합치면 cd가 필요하다. 그 후 ab와 cd를 합쳐보면 아래처럼 식이 나.. 2023. 8. 11.
[ABC301] D - Bitmask (AtCoder Beginner Contest 301 in Java) 목차 문제 : ABC301 - D 필요 알고리즘 문자열, 수학 이진수에 대한 수학적인 사고가 좀 필요한 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 1. 우선 '?'를 전부 '0'으로 바꿔본다. (만들 수 있는 최소값) 그게 n과 동일하다면 n이 답이고, n보다 크다면 애초에 불가능한 경우이므로 -1을 출력하고 끝낸다. 2. 다음으로 '?'를 전부 '1'로 바꿔본다. (만들 수 있는 최대값) 그게 n 이하라면 그.. 2023. 5. 13.
[자바] 백준 1790 - 수 이어 쓰기 2 (java) 목차 문제 : boj1790 필요 알고리즘 구현, 수학 수학적 사고를 통해 구현할 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 N이 1억까지이므로, 언어에 따라 실제로 수를 이어봐서 풀 수도 있어 보인다. 실제로 파이썬은 이렇게 풀 수 있음을 확인했다. 자바는 안될 것 같다. 우선 N이 100,000,000인 경우는 제외하고 최대 8자리까지 가능하다고 생각해보자. 그렇다면 자리수가 i개인 숫자는 ix9x.. 2023. 5. 9.
[자바] 백준 27961 - 고양이는 많을수록 좋다 (java) 목차 문제 : boj27961 필요 알고리즘 그리디 0마리 이상 k마리 이하에 안낚이도록 그리디 규칙을 정할 수 있어야 한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 주의해야하는 점은 복제 마법 부분이다. 0마리 이상 k마리 이하라고 했는데, k마리 복제하지 않는게 이득인 경우가 과연 있을까? 없다(갯수 안넘어가게 조절할 때 빼고). 즉 이 문제는 고양이를 1마리 늘리거나, 2배 늘릴 수 있을 때 최소의 행동을 구하는.. 2023. 4. 19.
[자바] 백준 27960 - 사격 내기 (java) 목차 문제 : boj27960 필요 알고리즘 수학, 2진수 2진수를 떠올렸다면 풀만한 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 과녁의 점수가 2진수의 각 자리수를 뜻하는걸 깨달았다면, 정수 표현방식과 동일하다는걸 떠올릴 수 있다. 즉, Sa, Sb 각각에 대해 어떤 과녁을 맞췄는지 항상 분리해낼 수 있다. 예를들어 7이라는 점수를 표현하려면 뭔가 과녁을 어떻게 조합하면 다양한 경우의 수가 있다고 생각할 수 있.. 2023. 4. 19.