브루트포스(Brute-force) 란?Brute Force, 무식하게 힘으로 라는 의미를 가지고 있다. 브루트포스는 완전 탐색 이라고도 불리며, 가능한 모든 경우의 수를 하나도 빠짐없이 전부 시도해보는 방법이다. 즉, 자물쇠의 비밀번호를 맞히기 위해 '0000'부터 '9999'까지 모든 숫자를 하나씩 돌려보는 것과 같은 원리이다. 장점코드를 작성하는 방법이 직관적이라, 초보자도 쉽게 구현할 수 있다. 가능한 모든 경우를 확인하기 때문에, 정확도를 100% 보장한다. 단점시간과 자원 비용이 매우 높다. 문제의 규모 및 복잡도에 예민하다. 문제의 규모가 커지면 확인해야 할 경우의 수가 늘어나, 정답을 찾기까지 너무 오래 걸린다. 브루트포스는 가장 기초적인 알고리즘으로, 문제 해결의 기본 원리를 이해하는 ..
문제 문제 해결 방법에라스토테네스의 체 이용하여 소수 구하기소수의 합 구하기 시간 제한이 짧으므로, 시간 복잡도를 고려하여 코드를 구성하는 게 중요하다. 에라스토테네스의 체https://skylarcoding.tistory.com/361 문제 반례 찾는 법아래 링크에서 확인할 수 있다.https://skylarcoding.tistory.com/303 코드 해설소수 판별 체를 한번만 만들어 시간 복잡도 개선소수끼리의 합 구할 때, 이중 for 문이 아닌 n = i + (n - i) 공식 이용하여 시간 복잡도 개선 위 두 가지만 유의하고 이전의 에라스토테네스의 체 문제 풀이들을 참고하면 쉽게 풀 수 있다. [Java] 백준1929 소수 구하기 : 에라스토테네스의 체출처: https://skylar..
문제 에라스토테네스의 체https://skylarcoding.tistory.com/361 문제 반례 찾는 법아래 링크에서 확인할 수 있다.https://skylarcoding.tistory.com/303 코드package AlgorithmStudy.src.silver;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class S4948 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(Syst..
문제 힌트에라스토테네스의 체를 이용하여 푼다. 에라스토테네스의 체의 기본 원리체로 치듯이 수를 걸러낸다 하여 '에라스토테네스의 체' 라고 부른다. n까지의 모든 수가 담긴 배열을 준비한다.모두 소수라고 가정한다.값을 반복하며 배수를 지운다. 문제 반례 찾는 법아래 링크에서 확인할 수 있다.https://skylarcoding.tistory.com/303 백준 알고리즘 문제 풀기, 반례 찾는 방법아래 사이트에서 약 400개의 문제에 대해 반례를 찾을 수 있다.https://testcase.ac/ Testcase AC총 385개의 백준 문제에 대해 반례를 찾을 수 있습니다. 찾고 있는 문제가 없나요?testcase.ac 백준에 제출하skylarcoding.tistory.com 문제풀이 pac..
유클리드 호제법, 최대공약수 구하기두 개의 자연수 또는 정수의 최대공약수 (GCD : Greatest Common Divisor) 을 구하는 가장 빠르고 효율적인 알고리즘이다. 호제법은 '서로 나누는 방법' 이라는 뜻이다. 두 수 A와 B의 최대공약수는 B와 A를 B로 나눈 나머지의 최대공약수와 같다. 예를 들어 보자. 1112 와 695의 최대공약수를 구할 때, 큰 수를 작은 수로 나눈다. (반복)1112 % 695 = 417 (나머지)695 % 417 = 278 (나머지)417 % 278 = 139 (나머지)278 % 139 = 0 (나머지)나머지가 0이 나온 시점에 나누는 수로 사용된 139가 1112와 695의 최대공약수이다. 위 내용을 코드로 구현하면 아래와 같다. public static ..
문제시간 복잡도 개념 보러가기 풀이우선 기본 공식을 알아보자. O(g(n)) 은 f(n) 정리하면, a1 * n + a0 a1 * n + a0 그런데 이렇게 제출하면 틀렸습니다. 가 출력된다. 너무 모르겠어서 다른 사람들 블로그를 찾아봤다. 결론부터 말하자면 조건식에 아래 코드를 넣어줘야 한다고 한다.&& a1 그런데 이 부분이 너무 이해가 안 갔다. 제대로 설명하는 사람이 거의 없었다. 내가 이해한 대로 설명을 해보겠다. 혹시 틀리다면, 댓글로 알려주길 바랍니다!! 1. 나온 조건식을 전부 좌항으로 옮기면 아래와 같이 변경된다. 2. 이때, 문제에 나온 조건을 만족시켜야 한다.모든 n ≥ n0에 대하여 f(n) ≤ c × g(n)인 양의 상수 c와 n0가 존재한다나는 이를 n 이 어떤 값이건 위..
문제시간복잡도 개념 보러가기 풀이풀이에는 두 가지 방법이 있다.1. 시그마로 계산하는 방법2. 경우의 수 구하기 수학 안본지 6년이 넘어서 .. 공식을 찾는게 너무 어려워 다른 분 블로그를 참고했다. 정리하자면, 아래 경우의 수의 규칙이 아래와 같다. (1,2,3) ... (1,6,7)(2,3,4) ... (2,6,7) 때문에 아래와 같이 나올 수 있게 된다. n = 7i = 1/ j 2/ 3, 4, 5, 6, 7 /5 j 3/ 4, 5, 6, 7 /4 j 4/ 5, 6, 7 /3 j 5/ 6, 7 /2 j 6/ 7 /1i = 2/ j 3/ 4, 5, 6, 7 /4 j 4/ 5, 6, 7 /3 ..
문제시간복잡도 개념 보러가기 풀이반복문이 3번 반복되므로, n의 세제곱이 된다. 최고차항의 차수는 3이 된다. 왜 세제곱을 하는지 궁금하면 여기에서 개념을 확인할 수 있다.2. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다. 코드package AlgorithmStudy.src.bronze;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.math.BigInteger;public class B24266 { public static void main(String[] args) throws IOException { BufferedRe..
문제시간복잡도 개념 보러가기 풀이n == 7i = 1/ 2, 3, 4, 5, 6, 7,/ 6i = 2/ 3, 4, 5, 6, 7/ 5i = 3/ 4, 5, 6, 7/ 4i = 4/ 5, 6, 7/ 3i = 5/ 6, 7/ 2i = 6/ 7/ 1234567345670456700567000670000700000000000 6 + 5 + 4 + 3 + 2 + 1 로 결과가 나오는 것을 알 수 있다. 이는 위 표를 보면, 6 * 7의 절반인 것을 알 수 있다. 공식은 n(n-1)/2 이다. 코드package AlgorithmStudy.src.bronze;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamRea..
문제시간복잡도 개념 보러가기 풀이이중 for 문 구조로, n이 2번 (n*n) 으로 반복되는 것을 알 수 있다. 즉 n의 2제곱이므로 실행 횟수는 n*n, 최고차항의 차수는 2이다.* 500,000 X 500,000 은 250,000,000,000으로 int 의 범위를 벗어남을 유의해야한다. ( int 범위 2,147,483,647) 코드package AlgorithmStudy.src.bronze;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.math.BigInteger;public class B24264 { public static void main(Strin..
