본문 바로가기

브루트포스83

[자바] 백준 1490 - 자리수로 나누기 (java) 목차 문제 : boj1490 필요 알고리즘 브루트포스, 수학 오히려 무지성으로 풀면 정답인 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 최악의 경우는 123456789 또는 987123456 처럼 1~9 모두로 이루어진 값이 입력으로 들어오는 경우이다. 이 때 lcm(1,2,3,...9)는 2520이다. 따라서 최악의 경우라도 9876543210000 이내로는 2520의 배수가 존재한다. 그러므로 생각보다 정답의.. 2023. 7. 20.
[자바] 백준 9202 - Boggle (java) 목차 문제 : boj9202 필요 알고리즘 브루트포스, 백트래킹, 그래프 탐색(dfs 혹은 bfs 등), 트리, 트라이(Trie) 원래 플래급 가면 여러가지 섞어야 하는 경우가 많긴하다. 내 경우엔 메인 알고리즘은 트라이였고, 나머진 트라이로 로직 구현을 위한 부가적인 부분이었다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 일단 내 경우엔 트라이로 풀었는데, 의견쪽을 보니 시간이 널널해서 그냥 해싱 처리해도 된다고 한다... 2023. 6. 27.
[자바] 백준 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.
[자바] 백준 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.

티스토리툴바