S E P H ' S

코딩테스트 연습 - 소수 찾기 1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요. 소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. (1은 소수가 아닙니다.) 제한 조건 n은 2이상 programmers.co.kr 특정 범위 내의 소수를 판별하는 문제이다. 블로그의 에라토스테네스의 체의 설명을 보고 온다면 코드 이해가 쉬울 것이다. 에라토스테네스의 체 에라토스테네스의 체는 가장 대표적인 소수(Prime Number) 판별 알고리즘이다. 임의의 자연수 n에 대해 그 이하의 모든 소수를 찾는 가장 간단하고 빠른 방법이다. 먼저 입력받은 수가 소수인지 판 yoseph0310.tistory.com def sol1(n): sieve = [True] * (n..

에라토스테네스의 체는 가장 대표적인 소수(Prime Number) 판별 알고리즘이다. 임의의 자연수 n에 대해 그 이하의 모든 소수를 찾는 가장 간단하고 빠른 방법이다. 먼저 입력받은 수가 소수인지 판별하는 알고리즘을 작성해보자. def prime(n): for i in range(2, n): if n % i == 0: return False return True 위와 같은 알고리즘의 시간복잡도는 O(N)이다. 주어진 모든 경우의 수 만큼 반복문을 돌며 약수 여부를 확인하기 때문에 매우 비효율적이다. 예를 들어 숫자 8의 경우 2 * 4 = 4 * 2와 같은 식으로 대칭을 이루기 때문이다. 더 간단하게 생각해보더라도 반복문에서 n이 8이라고 가정한다면 2에서 이미 한번 False가 반환되지만 반복이 계속..

코딩테스트 연습 - 모의고사 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 programmers.co.kr 1. 수포자들이 찍는 방식을 리스트로 만든다. 2. answers 만큼 반복문을 돌면서 p1과 같으면 cnt1, p2와 같으면 cnt2, p3와 같으면 cnt3을 증가시킨다. 3. 그것을 answer_temp에 담는다. 4. 가장 많은 문제를 맞춘 사람을 맞춰야한다. 인덱스와 값을 낼 수 있도록 enumerate를 사용하여 score가 max와 같은 인덱스 + 1을 정답 리스트에 append한다. def solution(answers): answer = [] a..

코딩테스트 연습 - 소수 만들기 주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 programmers.co.kr 1. combinations 를 사용해서 nums에서 3개를 고른다. 2. 반복문 안에서 3개의 수를 더한 수를 구하고 2부터 그 수의 제곱근 까지 나누어서 나머지가 0인 수가 있으면 소수가 아님을 이용한다. 3. 만약 소수라면 answer 의 개수를 1씩 증가 시킨다. from itertools import combinations as c def solution(nums): answer = 0 comb = list(c(nums,3)) for..