본문 바로가기

brute Force91

[자바] 백준 1214 - 쿨한 물건 구매 (java) 문제 : boj1214 필요 알고리즘 개념 수학, 정수론, 브루트포스 브루트포스로 풀 수 있긴한데, 수학적으로 시간복잡도를 줄여야한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 이 문제를 풀기전에, 혹시 개념이 잘 떠오르지 않는다면 '백준 14916번 : 거스름돈' 을 먼저 풀어보자. dp로도 풀 수도 있겠지만, 브루트포스로 푸는 경우를 생각해보자. 내 경우엔 이와 비슷한 문제를 풀었던 기억이 나서 거기서 시간을 깎아내.. 2022. 9. 2.
[자바] 백준 25494 - 단순한 문제 (Small) (java) 문제 : boj25494 필요 알고리즘 개념 브루트포스 (완전탐색) 모든 경우를 다 살펴보는 브루트포스 문제이다. 나머지 연산 (기본 수학) 나머지 연산이 무엇인지, 사용중인 언어에서 어떻게 계산할 수 있는지 알아야 한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 각 테스트 케이스마다, a,b,c의 모든 쌍을 확인하더라도 O(60^3) 의 시간복잡도이다. 따라서 모든 테스트케이스라고 해도 O(100*60^3)으로 시간복.. 2022. 8. 23.
[자바] 백준 1977 - 완전제곱수 (java) 문제 : boj1977 필요 알고리즘 개념 브루트포스 모든 경우를 살펴보는 브루트포스 알고리즘 개념이 필요하다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 1 2022. 8. 21.
[자바] 백준 1038 - 감소하는 수 (java) 문제 : boj1038 필요 알고리즘 개념 브루트포스 모든 경우의 수를 살펴보는 브루트포스 개념을 알고 있어야 한다. 브루트포스 글 백트래킹 브루트포스에서 모든 경우를 볼 때, 중간에 답이 될 가능성이 없는 부분을 제외시켜 시간복잡도를 낮추는 백트래킹 개념에 대해 알고 있어야 한다. 백트래킹 글 ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 이 문제에서 나올 수 있는 가장 큰 감소하는 수가 '9876543210'임은 생.. 2022. 8. 18.
[자바] 백준 5671 - 호텔 방 번호 (java) 문제 : boj5671 필요 알고리즘 개념 브루트 포스 모든 경우의 수를 다 살펴보는 것을 뜻한다. 다른 말로 완전탐색 이라 한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 입력 개수가 주어지지 않은 상태에서 자바에서는 어떻게 입력을 받을 수 있는지부터 살펴보자. BufferedReader를 사용해 받는다고 할 때, EOF(End of file)까지 입력받을 경우 BufferedReader의 readLine 함수에.. 2022. 8. 11.
[자바] 백준 22943 - 수 (java) 문제 : boj22943 필요 알고리즘 개념 브루트포스 가능한 모든 경우에 대해 완전탐색을 통해 경우의 수를 찾아줄꺼다. 에라토스테네스의 체 소수 판정 알고리즘이다. 한 개의 수가 소수인지 판정할때는 안쓰인다. 이 문제에서는 특정 범위 이내의 모든 소수를 찾아두고 풀이를 진행할 것이므로 에라토스테네스의 체를 사용했다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 이 문제를 풀기위해 알아야 하는 것들을 생각해보자. 1... 2022. 7. 28.
[자바] 백준 10504 - 덧셈 (boj java) 문제 : boj10504 24의 경우 7+8+9가 답이다. 대충 봐도 중간 특정 지점에서 시작되는 숫자에 대해, 몇 개의 합인지도 지정되지 않은 상태로 연속되는 양의 정수의 구간을 찾기란 어려워 보인다. 개인적으로 수학이 약해서 정말 어려웠다 ㅠ. 약간 생각을 바꿔서, 그럼 중간부터 시작되지 않고 항상 1부터 시작된다고 해보자. 즉, a까지의 합이라고 하면 1+2+...+a 가 N이라고 하면 어떨까? 이건 상대적으로 쉬워보인다. a는 최대 44720이니깐(44720x44721/2 = 999,961,560 이고, 문제에서 제시된 입력값의 최대치가 10^9 이므로 최대 44720 까지만 보면 된다.), O(44720)으로 찾을 수 있다. 그리고 a를 2부터 44720까지 증가시키면서 확인해보면 '만약 여러 .. 2022. 7. 22.
[자바] 백준 18114 - 블랙 프라이데이 (boj java) 문제 : boj18114 1. 한 개만 선택해서 C가 되는 경우 (코드 19~22line 참고) 이 경우는 간단하다. N개를 입력받으면서 해당 값이 C인 경우를 찾으면 된다. O(N) 2. 두 개를 선택해서 C가 되는 경우 (코드 24~31line 참고) 이 경우도 어렵지 않다. 미리 N개를 입력받으면서 배열에도 기록해두고, HashSet에도 기록을 해둔다고 해보자. 이후 배열을 순회하면서 현재 보고 있는 값이 A라고 할 때, HashSet에 C-A가 존재하는지만 확인해주면 된다. 주의점은 A != C-A 여야 한다(동일한 물건을 두 개 고르면 안되고, 모든 물건은 무게가 다르므로 A와 C-A가 동일할 수 없다). O(2N) 3. 세 개를 선택해서 C가 되는 경우 (코드 32~41line 참고) 이 경우.. 2022. 7. 21.
[자바] 백준 12100 - 2048 (Easy) (boj java) 문제 : boj12100 (상당히 귀찮은편인) 단순 시뮬레이션 문제이다. 최대 5번 이동이라고 했으므로, 처음 상태에서 상하좌우 4방향으로 움직이는걸 최대 5번 반복하면 된다. 즉, 최대 4^5번으로 모든 경우를 확인할 수 있다. 이 때 각 방향마다 NxN 칸의 모든 것들을 해당방향으로 움직여야 한다고 볼 수 있으므로 대략 O(N^2 x 4^5)의 시간복잡도가 된다. 그럼 남은건 상하좌우 방향으로 움직인다고 할 때, 문제에서 제시된 방법대로 동작만 되도록 시뮬레이션을 구현해주면 된다. 이 때 주의점은 예를들어 아래와 같은 경우를 보자. 2 0 0 2 0 0 2 0 0 위와 같은 경우 우측 방향으로 모두 이동시킨다고 했을 때, 우측으로 모두 붙어야 할 것이다. [A] 0 2 0 0 2 0 0 2 0 [B].. 2022. 7. 20.
[자바] 백준 11648 - 지속 (boj java) 문제 : boj11648 n이 한자리 수가 될 때 까지, 각 자리수를 곱한 새로운 값을 구해 n에 넣어주면 된다. 각 자리수를 곱하는 부분은 이하 코드의 요 부분을 참고해보자. while (n!=0) { cur*=n%10; n/=10; } 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { private void solution() throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); int cnt =.. 2022. 7. 12.