brute Force92 백준 1590 자바 - 캠프가는 영식 (BOJ 1590 JAVA) 문제 : boj1590 n개의 경우 각각에 대해 만족하는 가장 작은 시각을 찾아보면 된다. n개의 경우 각각에 대해 a가 0부터 C-1까지의 자연수라고 할 때, 다음 식을 통해 나온 값 중 최초로 T 이상의 값이 나오는 경우가 해당 경우의 최소수치이다. n개에 대해 각각 위의 최소수치를 구하고, 그 중 가장 작은 값이 답이다. 이 때 C는 최대 100 이므로 0부터 99까지 전부 다 해봐도 최대 O(NC) 정도의 시간복잡도이므로 전부 다 해보면 된다. 따라서 브루트 포스이며, 최초로 T 이상의 값이 나올 경우 바로 중지하면 되고 추가로 f(a)가 이미 이전에 나온 값보다 큰 경우엔 더이상 볼 필요도 없으므로 백트래킹도 가미하면 좀 더 효율적으로 할 수 있다. 코드에서 while문 내의 's < t'부분이.. 2022. 2. 6. 백준 9753 자바 - 짝 곱 (BOJ 9753 JAVA) 문제 : boj9753 100000일 때 100001이 답이란걸 문제 예시에서 보여줬으므로 사실 100000이하의 소수 곱에 대해서만 신경쓰면 된다. 그리고 어차피 가장 작은 소수가 2 이므로 50000까지만 보면 된다. 따라서 5만 이하의 모든 소수를 우선 에라토스테네서의 체로 구한다. 그리고 소수의 곱을 모든 쌍을 보면서 모두 구한다. 이 때 10만이 넘어간다면 제외해도 된다. 구한 값은 어차피 10만까지만 알면 되므로 배열에 넣어도 되고, 내 경우엔 더 큰 수를 빨리 구해보려고 TreeSet에 넣었다. 이후 하나씩 입력받으면서 TreeSet의 ceiling을 출력하면 된다. '2'의 과정을 배열에 했다면 입력받은 값 이상을 순회하며 가장 작은 소수를 출력하면 된다. 코드 : github import.. 2022. 1. 18. 백준 8807 자바 - Przedziały (BOJ 8807 JAVA) 문제 : boj8807 1. 다음과 같은 입력을 생각해보자. 1 5 1 2 2 2 3 5 7 8 10 10 이 문제의 경우 만약 모든 범위를 한 선에 겹쳐그릴 수 있다면 쉽게 답을 구할 수 있을 것이다. 그럼 어떻게 각 범위를 합칠 수 있을지 생각해보면 된다. 우선 가장 간단한 방식으로, 모든 범위에 해당하는 배열을 만들고 입력을 받으며 범위를 채운 후, 마지막에 모든 범위에 대해 확인해서 개수를 세는걸 생각할 수 있다. 다만 이 문제의 경우 이렇게되면 모든 범위가 -10억~+10억이 되므로 모든 범위 확인만해도 대략 20초정도 걸린다. 2. 다른 방법을 생각해보자. 사실 각 A,B에 대해 범위를 순회만 해도 최대 20억번 해야하므로 시간초과가 확실하다. 따라서 아예 다른 방식으로 생각해봐야 한다. OR.. 2022. 1. 16. 백준 9847 자바 - 4SUM (BOJ 9847 JAVA) 문제 : boj9847 1. Brute Force로 가능한가? 4개의 수의 합이 0이 되는 경우를 찾아야 한다. 제일 간단하게 생각해보면 모든 쌍을 보면 된다. 이 경우 O(500^4) 이므로 유효한 시간 내에 찾을 수 없다. 2. 문제를 단순화 해보자 그럼 우선 문제를 단순화해서 생각해보자. 세트가 2개만 존재한다고 생각해보자(각 세트에 들어간 수는 N개). 그럼 각 세트에서 하나씩 골라서 2개의 수의 합은 어떻게 찾을 수 있을까? 모든 경우를 보는 O(N^2)보다 더 빠른 방법이 있을까? 두 세트가 X와 Y라고 한다면, X의 수를 정렬한 후 Y의 모든 수를 순회하면서 X에 대해 이분탐색으로 합이 0이 되는 경우를 찾을 수 있을 것이다. 그럼 O(NlogN[정렬] + N[순회]*logN[이분탐색]) 정.. 2022. 1. 8. 백준 18511 자바 - 큰 수 구성하기 (BOJ 18511 JAVA) 문제 : boj18511 N이 최대 1억이고, K의 각 원소는 1부터 9 까지이므로 어쨌든 8자리 수 이내로 모든 답이 나온다. 그리고 K는 최대 3개까지이므로 모든 경우를 봐도 최대 O(3^8) 이다. 따라서 따로 다른 방법 생각해볼 것 없이 브루트 포스로 풀면 된다. 약간의 백트래킹을 넣어서 예를들어 이미 N보다 큰 값이라면 더이상 볼 것 없이 종료하는 식으로 하면 된다. 백트래킹 개념을 넣지 않아도 시간내에 통과 가능한 간단한 문제이다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { private int max =.. 2022. 1. 3. 백준 10819 자바 - 차이를 최대로 (BOJ 10819 JAVA) 문제 : boj10819 N이 최대 8밖에 안된다. 8개의 수로 만들 수 있는 모든 경우를 확인해봐도 O(N!) 이므로 그냥 모든 경우를 확인해보면 된다. 재귀나 스택을 사용한 dfs로 짜면 완전탐색(=brute force)을 쉽게 짤 수 있다. 단순 반복문으로 짜려고 하면 최대 8중첩 반복문이 필요하다 ㅋㅋ 재귀에 익숙치 않다면 방문체크가 어려울 수 있다. 다음 수를 선택하기 전에(내부에서 dfs를 다시 부르면서 cnt+1 해주는 부분이 다음 수를 선택하기 위한 부분이다.) 방문체크를 하고, 반환된 후에 다시 방문체크를 해제해줘야 모든 경우를 볼 수 있다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; impor.. 2022. 1. 1. 백준 2670 자바 - 연속부분최대곱 (BOJ 2670 JAVA) 문제 : boj2670 1. 모든 경우를 보면서, 이전 값이 1.0 보다 크다면 현재 입력받은 수를 곱해준다. 이전까지 구해둔 값이 1.0 이하라면 현재값을 곱하는 것이 손해이므로, 현재값부터 다시 연속된 수를 파악하면 된다. 예를들어 1.2 0.9 1.5 가 있고 현재 1.5를 살펴볼 차례라고 해보자. 이전까지의 값의 곱인 1.2*0.9는 1.08이므로 1.0보다 크다. 따라서 1.5까지 곱해서 1.620이 답이 된다. 반면에 1.1 0.9 1.5라면 1.1*0.9 = 0.99 이므로 1.5에 곱하면 오히려 손해이다. 따라서 1.5부터 다시 구해나가는 것이 더 이득이다. 정리하면 현재 입력받은 수가 cur, 이전까지 계산하던 값이 bf 라고 해보자. bf>1.0이라면 bf = bf * cur이 될 것이.. 2021. 12. 23. 백준 3011 자바 - 이름 지어주기 (BOJ 3011 JAVA) 문제 : boj3011 1. A에서 B 구간의 최대가 10^9이므로, 우선 모든 경우를 봐서는 통과할 수 없음을 알 수 있다. 그럼 뭔가 정답 구간을 정할 수 있는 방법이 있다는 얘기이다. 이 문제의 경우, 어떠한 X 지점에 대해 모든 N지점 중 거리의 차가 최소인 지점을 최대한 멀리 두려고 한다(min{|X-Pi|, i ∈ [1,N]}). 즉, X는 모든 N개의 지점 P_i와 최대한 멀리 떨어지면 된다. 2. 입력이 4 10 46 56 70 10 70 인 경우를 생각해보자. 어떻게 해야 N개의 지점에서 가장 멀리 떨어진 X 지점을 모두 보지 않고 찾을 수 있을까? 최선의 선택은 각 지점들의 중간지점들을 보면, 그 중 가장 양쪽의 차이가 큰 지점을 고르면 될 것임을 생각해볼 수 있다(그리디). 그리고 하.. 2021. 12. 17. 백준 14911 자바 - 궁합 쌍 찾기 (BOJ 14911 JAVA) 문제 : boj14911 1. 주어지는 수의 개수가 주어지지 않으므로 입력받기 전에 총 배열의 크기를 알 수 없다. 미리 최대 개수 배열을 만들어 입력받은 후 처리하거나, 자바의 split 합수를 사용해 처리하면 된다. 2. 최대 개수가 10개밖에 안되므로 모든 경우의 수를 보면 된다. 다만 주의점은 사전 순으로 출력해야 한다는 부분인데, 이를 위해 정렬 후 모든 경우를 보면 된다. 또한 문제에 명시적으로 나타나진 않았으나, '사전 순으로 앞서는 기준은 a < c이거나, a == c 이면서, b < d 인 것' 에 따라 a==c이면서 b==d인 경우는 정의되지 않은 것을 알 수 있다. 따라서 서로 다른 쌍이라 할지라도, 동일한 출력값은 출력하면 안된다. 예를들어 입력이 1 1 1 1 1 2 와 같을 경우.. 2021. 12. 15. 백준 9327 자바 - 용량 확보 (BOJ 9327 JAVA) 문제 : boj9327 음주코딩이 더 코딩이 잘된다는게 사실인것같다. 평소엔 시간 꽤나 걸리던 골1과 플5 문제가 둘다 한방에 해결됬다. 뭐지.. 이상하다. 아무래도 이것저것 복잡도 계산 해볼 정신머리가 없어서 무지성으로 짜보다 보니 오히려 빨리 해결하는 것 같다 ㅋㅋㅋ 결국 입력으로 주어진 n개의 용량x2에 대해 존재 가능한 모든 합의 경우의 수 중, 확보하려는 용량 e보다 같거나 큰 것 중 가장 가까운걸 출력하면 된다. 예를들어 n개가 400 600 700 일 경우 존재 가능한 모든 합의 경우의 수는 다음과 같다. 400 1000 1100 600 1300 700 이걸 정렬하면 400 600 700 1000 1100 1300 이 되고, 이 중 만약 e가 1050이라면 1050보다 같거나 큰 수중 가장 .. 2021. 12. 13. 이전 1 ··· 5 6 7 8 9 10 다음
