본문 바로가기

브루트포스91

[자바] 백준 23807 - 두 단계 최단 경로 3 (java) 문제 : boj23807 필요 알고리즘 개념 다익스트라, 브루트포스 다익스트라로 거리를 구하고, 세 개의 정점은 브루트포스로 고를 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 이 문제에서 중요한건 시작점 x, 목표지점인 z, 그리고 P개의 중간정점 중 3개를 지나야 한다는 점이다. 아주 간단하게 생각해보자. x에서 출발해 P개의 중간정점까지의 최단 거리를 모두 안다고 해보자. 그리고 P개의 중간정점에서 중간정점들.. 2023. 3. 1.
[자바] 백준 2859 - 별 관찰 (java) 문제 : boj2859 필요 알고리즘 개념 수학, 정수론, 브루트포스 수식을 정리해 브루트포스로 모든 경우를 살펴보면서 나누어떨어지는 경우를 찾아야한다. 비둘기집의 원리 좀 더 명확하게 횟수를 지정하고 싶거나, 몇 번 해야 Never인지 따로 판단하지 않으려면 이게 필요하다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 시간과 분으로 된 문자열은 처리하기가 상당히 까다롭다. 그러니 우선 정수로 변환하기 위해 입력값을 .. 2023. 1. 30.
[자바] 백준 27162 - Yacht Dice (java) 문제 : boj27162 필요 알고리즘 개념 많은 조건 분기, 구현, 브루트포스 많은 조건을 분기해줘야 하는 구현문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 한 함수에서 if문으로 모두 처리하게 되면 디버깅이 쉽지 않다. 내 경우엔 클래스로 구성을 나누었다. Pedigree 라는 인터페이스가 있는데, 각 족보를 뜻한다. 내부에 maxScore(int[] arr)만 있고 해당 Pedgree의 구현체로 얻을 수 있는.. 2023. 1. 15.
[자바] 프로그래머스 - 순서쌍의 개수 (Lv0, Java) 문제 : Programmers-순서쌍의 개수 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges 필요 알고리즘 개념 브루트포스 n의 크기가 100만밖에 안되므로 그냥 1부터 n까지의 모든 수를 비교해보면 된다. O(n) 수학 (정수론) 좀 더 효율적으로 O(sqrt(n))으로도 풀 수 있다. 이 경우 수학적 지식이 좀 필요하다. 풀이 우선 n의 크기가 100만으로 매우 작으므로 그냥 1부터 n까지의 모든 수를 보면 된다. a를 1부터 n까지 증가시키면서, n%a == 0 이라면 b = n/a 가 되므로 answer을 1 증가시켜주면 된다. 이 경우 O(n)이 걸린다. int answer = 0; for (int i = 1; i 2022. 12. 2.
[자바] 백준 4375 - 1 (java) 문제 : boj4375 필요 알고리즘 개념 브루트포스 풀이1의 경우 BigInteger를 사용해 브루트포스로 푼다. 수학, 정수론 풀이2의 경우 나머지 연산의 특성을 사용해 BigInteger를 사용하지 않고 푼다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 2와 5로 나누어 떨어지지 않는다는 조건이 왜 붙었냐면, 소인수분해시 2와 5가 있을 경우 그 중 작은 수 만큼 수의 낮은 자리수에 0이 생겨서 1로 나누어떨어.. 2022. 11. 26.
[자바] 백준 6131 - 완전 제곱수 (java) 문제 : boj6131 필요 알고리즘 개념 브루트포스 대상으로 가능한 모든 경우를 직접 보면서 확인해주면 된다. 수학 제곱근. 제곱 연산이 필요하다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 정수 A, B에 대해 1 2022. 11. 25.
[자바] 백준 3724 - 표 (java) 문제 : boj3724 필요 알고리즘 개념 큰 수 연산, 브루트포스 문제에서 제시된 방식대로 모든 경우의수를 다 살펴보면 된다. 다만 엄청나게 큰 수 연산이 들어간.. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 주의점은 N과 M의 순서가 상당히 헷갈리게 들어오니 조심하자. 이 문제의 경우 모든 경우를 직접 해보면 된다. 즉, 각 열의 모든 수를 직접 다 곱해보고 비교하면 된다! 그러기 위해서는 대략 (2^31)^1000 .. 2022. 11. 7.
[자바] 백준 13410 - 거꾸로 구구단 (java) 문제 : boj13410 필요 알고리즘 개념 브루트포스 단과 항을 입력받아 구구단을 진행해 수를 구하고, 해당 수를 모두 뒤집은 것 중 가장 큰 값을 찾아야 한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 8단의 5개 항의 값은 8, 16, 24, 32, 40 이다. 이걸 전부 뒤집으면 8, 61, 42, 23, 4 이다.이 중 가장 큰 값은 61이므로 61을 출력해주면 답이 된다. 즉, N과 K를 입력으로 받아서 기본.. 2022. 11. 2.
[자바] 백준 11068 - 회문인 수 (java) 문제 : boj11068 필요 알고리즘 개념 수학 10진수를 2~64진법으로 진법을 변경할 줄 알아야 한다. 브루트포스 입력으로 들어온 수에 대해 2~64진법 모두로 변경 후 각각 팰린드롬인지 확인해보면 되므로 브루트포스(완전탐색) 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 난이도가 어려운 문제는 아닌데, 자잘하게 알아야 할게 많은 문제이다. 1. 10진수를 2~64진법으로 변경 10진수를 n진법으로 변경할 경.. 2022. 10. 21.
[자바] 백준 14912 - 숫자 빈도수 (java) 문제 : boj14912 필요 알고리즘 개념 브루트포스 모든 경우의수를 확인해보면 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 최대 n은 10만이고, 최대 자리수는 6개이다. 따라서 1부터 n까지 모든 자리수를 하나씩 비교해보더라도 O(N)이면 되므로 브루트포스로 모든 경우를 확인해주면 된다. 각 자리수를 모두 확인하려면 우선 편한 방법으로는 1부터 n까지 각 수를 String으로 변경해준 뒤 Str.. 2022. 9. 29.

티스토리툴바