PS831 [자바] 백준 16563 - 어려운 소인수분해 (java) 목차 문제 : boj16563 필요 알고리즘 정수론, 소수 판정, 에라토스테네스의 체 에라토스테네스의 체를 사용해 소수를 구한 후 소인수분해를 해서 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 백준 3142를 풀면서 좀 더 개선된 소인수분해 테크닉을 익히게 되어, 민상님의 소개로(?) 풀어본 관련 문제이다. 코드 1은 기존에 내가 쓰던방식으로 푼 코드이고, 코드 2가 개선된 소인수분해 테크닉으로 짜본.. 2024. 2. 23. [자바] 백준 3142 - 즐거운 삶을 위한 노력 (java) 목차 문제 : boj3142 필요 알고리즘 정수론, 소수 판정, 에라토스테네스의 체 에라토스테네스의 체를 사용해 소수를 구한 후 소인수분해를 해서 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 어떤 수가 완전제곱수인지 우선 생각해보자. 내가 풀이를 위해 생각한 완전제곱수 판정은, 소인수 분해 후 각 소인수의 개수가 모두 짝수라면 완전제곱수가 가능하다는 점을 이용하는 것이었다. 예를들어서 예제 입력 2를.. 2024. 2. 23. [자바] 백준 3089 - 네잎 클로버를 찾아서 (java) 목차 문제 : boj3089 필요 알고리즘 매개변수 탐색(Parametric Search), 이분탐색, 정렬 2차원에 대한 매개변수 탐색(이분탐색 응용)으로 풀 수 있는 문제이다. 이걸 위해 정렬이 필요하다. 시뮬레이션 M개의 명령에 대해 시뮬레이션을 돌려봐야 최종 결과를 알 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 R, L, U, D 각각의 명령에 대해 필요한 동작은 다음과 같다. R : 동일 Y축에서 우측.. 2024. 2. 22. [자바] 백준 1309 - 동물원 (java) 목차 문제 : boj1309 필요 알고리즘 DP (동적계획법, 다이나믹 프로그래밍) 기본적인 형태의 DP 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 Nx2 칸으로 동물원이 구성된다. N칸의 세로는 우선 생각하지 말고, 2칸인 가로칸의 존재 가능한 상태를 생각해보자. 다음과 같이 4가지 종류로 존재 가능하다. 다만 이 중 (d)는 가로로 붙어 있게 배치할 수 없다고 하였으므로 불가하여 (a)~(c)의 3가지만 이.. 2024. 2. 21. [자바] 백준 7588 - Amicable (java) 목차 문제 : boj7588 필요 알고리즘 수학, 정수론 약수 구하는 것과 관련된 정수론 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 N이 최대 백만이고, 테스트케이스가 존재한다. 따라서 미리 백만까지의 모든 Amicable 쌍을 구해둔 후, 각 테스트케이스마다 알맞게 출력해주면 된다. 여기서 구현이 필요한 부분은 결국 어떠한 수가 주어졌을 때, 그 수의 모든 제수의 합을 구하는 녀석이 필요하다. 이 때, 주어진.. 2024. 2. 19. [자바] 프로그래머스 - 석유 시추 ([PCCP 기출문제] 2번) (Lv2, Java) 목차 문제 : Programmers - [PCCP 기출문제] 2번 / 석유 시추 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges 필요 알고리즘 탐색 (BFS, DFS 등) 약간의 아이디어만 있다면 탐색 알고리즘으로 풀 수 있다. 풀이 우리가 알아야 하는건, 각 열 번호에서 접근 가능한 석유들의 합이다. cnt[X] 라는 배열을 정의해보자. 이건 X 인덱스 열에서 접근 가능한 석유들의 총 합을 뜻한다. 최종적으로 cnt[0] 부터 cnt[m-1] 까지의 값 중 가장 큰 값을 출력하면 될 것이다. 예를들어 아래와 같이 표현될 것이다. 최종적으로 cnt 배열에서 가장 큰 값이 9 이므로 9가 답이다. --- 그럼 이제 cnt[] 에 값을.. 2024. 1. 22. [자바] 백준 16400 - 소수 화폐 (java) 목차 문제 : boj16400 필요 알고리즘 에라토스테네스의 체, DP (동적 계획법), 냅색 (배낭 문제), 정수론 에라토스테네스의 체로 소수를 전처리 후, 냅색 DP를 돌려서 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 순서대로 생각해보자. 1. N이하의 화폐를 모두 알아야 한다. -> 에라토스테네스의 체 등으로 N 이하의 모든 소수를 미리 구해두자. sqrt(N) 까지만 확인해본 이유는 '에라토스테네스의.. 2023. 12. 15. [자바] 백준 13565 - 침투 (java) 목차 문제 : boj13565 필요 알고리즘 그래프 탐색 (bfs, dfs) 약간의 아이디어만 생각나면 dfs나 bfs 같은 그래프 탐색으로만 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 주어진 격자에서 맨윗줄 중 흰색(0)칸을 찾아 거기서부터 BFS를 계속 진행한다면 좀 귀찮다. 약간의 아이디어를 더한다면 BFS 한방에 해결할 수 있다. 아이디어는 생각보다 간단한데, 주어진 격자(이미지 좌측)의 맨위와 맨 .. 2023. 12. 15. [자바] 백준 1375 - 나이 (java) 목차 문제 : boj1375 필요 알고리즘 그래프 탐색(bfs, dfs), 값/좌표 압축 값/좌표 압축이야 그냥 String을 쓰기 편하게 int로 바꾼 것 뿐이고, 풀이는 그냥 bfs를 썼다. 의외로 별다른 것 없이 bfs나 dfs로 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 입력이 String으로 들어오는데 이 부분부터 처리해보자. 그냥 새로운 문자열이 들어오면 그걸 새로운 int로 바꿔주면 된다... 2023. 12. 14. [자바] 백준 30025 - K의 배수 (java) 목차 문제 : boj30025 필요 알고리즘 DP (동적 계획법), 수학 DP를 이용해 풀 수 있는 문제이다. 풀이를 위해 수학적인 지식이 필요하다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 M자리의 양의 정수를 구하고, 그 중 K의 배수가 몇 개인지 구하는 문제이다. 물론 실제로 가능한 모든 M자리 양의 정수를 구해보면 O(N^M) = O(10^100) 이라는 천문학적인 경우의수가 되므로 불가능하다. 그럼 어떻게.. 2023. 12. 12. 이전 1 2 3 4 5 6 7 ··· 84 다음
