본문 바로가기

브루트포스84

[자바] 백준 10471 - 공간을 만들어 봅시다 (java) 목차 문제 : boj10471 필요 알고리즘 브루트포스 모든 경우를 확인해서 풀 수 있는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 이 문제는 0, W, 그리고 입력받은 P개의 파티션(0 < P < W) 총 P+2개에 대해 모든 쌍을 확인해 차이를 확인하면 되는 문제이다. 모든 경우를 보면 되므로 브루트포스(완전탐색) 이다. 그렇게 해도 O(P^2) 이므로 시간이 충분하다! 코드 : github import j.. 2023. 3. 17.
브루트포스 알고리즘 (Brute force 알고리즘) 목차 브루트포스란? 복잡한 알고리즘을 굳이 생각하지않고, 컴퓨터의 빠른 연산력을 이용해 모든 경우를 다 살펴보는 것을 의미합니다. brute force, BF, 완전탐색(exhaustive search), 완탐 정도로 불립니다. 설명을 위해 코딩테스트와 비슷한 형태의 문제로 예를들겠습니다. N개의 숫자를 입력받아 이 중 임의의 3개의 수를 골랐을 때, 세 수의 합이 S인 모든 경우의 수를 구하여라. 입력은 첫째줄에 공백을 기준으로 순서대로 N과 S가 주어진다. (3 ≤ N ≤ 20, lSl ≤ 1,000,000) 두번째줄에는 N개의 정수가 공백을 기준으로 주어지며, 각 정수의 절대값은 1,000,000을 넘지 않는다.(제한시간1초) 예를들어 만약 입력이 아래와 같이 주어졌다면, N=10, S=0이고 3개.. 2023. 3. 15.
[자바] 백준 1251 - 단어 나누기 (java) 목차 문제 : boj1251 필요 알고리즘 브루트 포스 3개의 단어로 나눌 수 있는 모든 경우를 확인해서 풀 수 있다. 정렬 사전순으로 가장 앞서는 단어를 알기 위해 문자열에 대해 사전순으로 정렬을 해줘야 한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 단어의 최대 길이는 50이다. 따라서 3개의 단어로 나눌 수 있는 경우의 수는 대략 50x50가지 경우가 존재한다. 따라서 O(N^2)으로, 모든 경우를 다 봐도 풀 수.. 2023. 3. 8.
[자바] 백준 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.