브루트포스89 백준 11292 자바 - 키 큰 사람 (BOJ 11292 JAVA) 문제 : boj11292 각 TC마다 N개를 모두 입력받기 전에는 뭐를 출력해야할지 알 수 없다. 또한 입력이 들어온 순서를 유지해야 하므로 정렬해서 처리할 수도 없다. 그렇다면 전부 어딘가에 저장하면서 입력받는다. 이 때 입력받으면서 최대값을 확인한 후, 다시 순회하며 최대값에 부합하는 String을 출력해주면 된다. 이 경우 O(N+N)이 된다. 내 경우엔 ArrayList를 두고 최대값이 갱신되면 리스트를 초기화하는 방식을 택했다. 즉, 현재 최대값과 동일한 값이 들어오면 ArrayList에 String을 추가하고, 최대값보다 낮으면 무시하고, 최대값보다 크면 리스트를 초기화하고 현재 최대값도 갱신하면서 새로 만들어진 리스트에 String을 추가한다. 이 경우 O(N)이 된다. 메모리도 덜쓴다. 사.. 2022. 2. 14. 백준 11653 파이썬 - 소인수분해 (BOJ 11653 Python) 문제 : boj11653 소수들로 소인수 분해 후 그 결과를 오름차순으로 출력하면 되는 문제이다. 바로 생각날 부분은 우선 소인수 분해를 위한 소수를 구하기 위해 에라토스테네스의 체를 사용해 N이하의 소수를 구한 후, 작은 소수부터 차례대로 나눠보면서 나눠지면 출력하는 방식이다. 하지만 에라토스테네스의 체를 계산하는데도 사실 O(N)정도의 시간이 필요하며, 이 문제에서는 N이 하나만 주어지므로 굳이 사용하지 않아도 된다. 만약 TC가 여러개였다면 물론 미리 소수를 구해두는게 이득이었을 것이다. 이 문제의 경우 그냥 2부터 N까지의 수로 직접 N을 나눠보면서 나눠지는 수를 출력하기만 하면 된다. 코드 : github import sys input = sys.stdin.readline n = int(inpu.. 2022. 2. 10. 백준 1544 자바 - 사이클 단어 (BOJ 1544 JAVA) 문제 : boj1544 최대 50길이의 String이 최대 50개 주어진다. 그럼 매번 단어가 주어질 때 마다 해당 단어의 사이클 단어를 전부 미리 만들어둔다고 해도, 최대 50x50 = 2500개의 단어밖에 나오지 않는다! 따라서 그냥 복잡하게 생각할 것 없이 2500개를 전부 만들면서 모든 단어끼리 비교해보면 된다. 로직은 다음과 같다. 1. n개의 ArrayList를 생성한다. 2. i번째 단어를 입력받을 시 i번 단어로 만들 수 있는 모든 사이클 단어를 만들어서 i번째 ArrayList에 집어넣는다. 3. 1번째부터 i-1번째 ArrayList들을 각각 전부 순회하며 동일한 단어가 있었는지 확인한다. 4. '3'에서 없었다면 cnt를 1 증가시킨다. i를 1 증가시키며 i가 n이 될때까지 2~4를.. 2022. 2. 9. 백준 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. 백준 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. 이전 1 ··· 5 6 7 8 9 다음
