본문 바로가기

수학117

[자바] 백준 2734 - 드럼통 쌓기 (java) 목차문제 : boj2734  필요 알고리즘기하학기하학 문제이다... 수학 어렵다.※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.  풀이  입력으로 쓰레기통의 가장 아래에 있는 N개의 드럼통이 주어진다. 그리고 항상 그 윗줄에는 N-1개의 드럼통이 있다고 했고, 그런식으로 위로 쌓다가 가장 위 1개의 드럼통의 (x,y)를 구하는 문제이다.   그래서 풀이자체는 간단한데, N개의 입력이 주어지면 최종적으로 남은게 1개일 때 까지 다음을.. 2024. 5. 27.
[자바] 백준 1342 - 행운의 문자열 (java) 목차문제 : boj1342  필요 알고리즘수학 (순열 개념) 또는 브루트포스 + 백트래킹순열 개념을 사용해서 풀 수도 있고, 백트래킹을 써서 풀 수도 있다.※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.  풀이  우선 순열 개념으로 푸는건 뒤로 미루고 브루트포스+백트래킹으로 푸는 것 부터 살펴보자.단순히 생각해보면 dfs로 모든 경우를 백트래킹하면서 찾은 후, 이미 나온 문자가 아니라면 카운팅하는 방법이 있을 것이다. 대강 O(10.. 2024. 5. 16.
[자바] 백준 1484 - 다이어트 (java) 목차문제 : boj1484  필요 알고리즘수학수학 문제긴한데 딱히 수학적 지식이나 알고리즘 지식이 필요한 문제는 아니다.※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.  풀이  내 풀이 로직은 다음과 같다. 보면 알겠지만 딱히 수학이나 알고리즘 지식이 필요한 부분은 없다. 다만 이전과의 차이가 G를 넘어서는 제곱수부터는 무시해도 된다는 직관은 필요하다. 저걸로 인해 시간복잡도가 엄청 줄어든다. 1. 제곱수들의 리스트를 만드는데, 바.. 2024. 5. 2.
[자바] 백준 31778 - PPC 만들기 (java) 목차문제 : boj31778  필요 알고리즘그리디, 투 포인터 (두 포인터), 수학 그리디 아이디어로 풀 수 있고, 내 경우 투 포인터를 사용해 구현했다. 경우의 수를 찾기 위해 약간의 수학적 지식도 필요하다.※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.  풀이  우선 어떻게 K번 연산을 적용해야 PPC 부분문자열의 최대치가 될지부터 생각해보자. 직관적으로 찾기 어렵지 않은데, 아무튼 최대한 많은 P가 앞쪽으로 가야하고, 최대한 .. 2024. 4. 30.
[자바] 백준 23128 - Math (java) 목차 문제 : boj23128 필요 알고리즘 수학, 브루트 포스 (brute force) 약간의 수학적 직관으로 범위를 좁히면, 그냥 브루트 포스로 다 대입해보면 답을 구할 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 문제에서 제시된 찾고자 하는 내용을 수식으로 나타내보면 다음과 같이 나타낼 수 있다. A와 B는 각각 a_i와 a_j를 뜻한다. C는 임의의 정수이다. 여기서 A, B의 범위는 [1, 1000000.. 2024. 4. 6.
[자바] 프로그래머스 - 분수의 덧셈 (Lv0, Java) 목차 문제 : Programmers - 분수의 덧셈 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges 필요 알고리즘 구현, 수학 딱히 알고리즘을 필요로 하지 않는다. 분수의 덧셈 방법만 알면 된다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 유클리드 호제법을 이용할수도 있겠으나, 굳이 최대 분자 분모가 1000인 상황에서 쓸 필요는 없다. 그냥 단순 .. 2024. 3. 29.
[자바] 백준 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.

티스토리툴바