728x90 코딩테스트25 브루트 포스 - 백준 2309 [Python] 브루트 포스 : 모든 방법을 한번씩 시도해보는 알고리즘 O(방법의 개수 * 시도하는 복잡도) 문제의 가능한 경우의 수를 계산해본다. 가능한 모든 방법을 다 만들어본다. > 그냥 다 해보는 방법, for문, 순열, 재귀 호출 사용, 비트마스크 사용 각각의 방법을 이용해 답을 구해본다. Problem) https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net Solution) 난쟁이의 키는 변하지 않는다는 조건을 이용한다. 모든 키의 합 sum을 구한다. 7난장이의.. 2021. 7. 26. 골드바흐의 추측 - 백준 6588 [Python] 골드바흐의 추축은 아래와 같이 설명된다. 2보다 큰 모든 짝수는 두 소수의 합으로 표현 가능하다. 위의 문장에 3을 더하면 5보다 큰 모든 홀수는 세 소수의 합으로 표현 가능하다. 증명이 되어있지 않아 추측 하지만 10^18이하에서는 참인 것이 증명되어 있다. 100만 이하의 짝수가 들어왔을 때, 두 소수의 합으로 표현할 수 있는지를 알아보는 문제 Example) https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net Solut.. 2021. 7. 16. 소수 - 백준 1929 [Python] 소수의 조건 약수가 1과 자기 자신 밖에 없는 수 N이 소수가 되려면, 2보다 크거나 같고, N-1보다 작거나 같은 자연수로 나누어 떨어지면 안된다. 소수를 구하는 방법 어떤 수 N이 소수인지 아닌지? N이하의 모든 소수를 구하는 방법 2. N이하의 모든 소스를 찾는 방법 : 앞서 말한 1번과정과 비슷하게 문제풀이를 한다면 N루트N의 시간복잡도가 발생한다. 이때 에라토스테네스의 체를 활용하면 더 빠르게 풀 수 있다. 2부터 N까지 모든 수를 써놓는다. 아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다. 그 수는 소수이다. 이제 그 수의 배수를 모두 지운다. 이 문제를 해결하기 위해선, 2개의 배열이 필요하다. 수를 지웠는지 아닌지 [T/F] 소수의 목록을 유지할 배열 Example) https://w.. 2021. 7. 16. 소수 - 백준 1978 [Python] 소수의 조건 약수가 1과 자기 자신 밖에 없는 수 N이 소수가 되려면, 2보다 크거나 같고, N-1보다 작거나 같은 자연수로 나누어 떨어지면 안된다. 소수를 구하는 방법 어떤 수 N이 소수인지 아닌지? N이하의 모든 소수를 구하는 방법 1. 어떤 수 N이 소수인지 아닌지? : 소수의 정의를 이용하는 방법, 약수의 특징을 이용하는 방법, 2~루트N까지 나누어 떨어지는지 (약수가 있는지 판별) 검사해 보는 방법이 있다. 이때, 직접 루트N을 구하는 것이 아니라, 값을 찾을 때 i = 2 - 루트N이기 때문에 i제곱이 N보다 작거나 같다는 범위를 사용하여 문제를 해결한다. (실수는 근사값이기 때문에, 정수의 표현을 사용하는 것이 안전) Example) https://www.acmicpc.net/problem/.. 2021. 7. 16. 이전 1 2 3 4 5 6 7 다음 728x90