본문 바로가기

브루트포스88

[세미나] 배열, 브루트 포스 (기초 자료구조 및 알고리즘 2회차) 세미나 진행한 pdf 입니다. 이후 자료구조 설명의 기반이 되는 배열과, 역시 이후 알고리즘 설명의 기반이 되는 브루트 포스에 대해 다룹니다. 이후에 영상이나 음성이 필요하다고 생각되는 회차가 있으면 그것도 공유할 예정입니다. ppt의 우측 상단 '새 탭에서 보기' 를 누르시면 크게보거나 pdf를 다운받아 보실 수 있습니다. 2023. 12. 11.
[자바] 백준 3151 - 합이 0 (java) 목차 문제 : boj3151 필요 알고리즘 브루트포스 (brute force) 모든 경우를 보면 되긴한데, 효율적으로 보면 된다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 단순히 생각하면 10000C3을 전부 보면 되는데 당연히 그러면 대충 O(10000^3) 이므로 비효율적이다. 약간 아이디어를 더해보자. N개의 수를 입력 받으면서 어떠한 수가 몇 번 나왔는지 미리 세두자. HashMap으로 처리해도 되고, 그냥 들어.. 2023. 11. 21.
[자바] 백준 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.