알고리즘/Math 3

소수 (솟수)

문제 1. 어떤 수 N (=upperbound) 보다 작은 소수 목록(prime numbers)을 구하라. 소수는 1과 자기 자신만을 약수로 갖는 수이다. 그러므로 무언가의 2배, 3배, 4배 등이 되는 수라면 이는 소수가 아니다. N=60이라고 하면, 그보다 작은 소수들은 primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59] 가 있을 것이다. 이를 구하는 가장 효율적인 방법은 기원전에 발견되었다(에라토스테네스의 체, Sieve of Eratosthenes). 이 방법은 우선 모든 수를 소수라고 추정한 뒤, 어떤 소수의 배수처럼 소수가 아닌 수를 지워나가는 것이다. 먼저 0, 1은 소수가 아니라고 정의한다. 최초의 소수인 2를..

알고리즘/Math 2023.08.06

random (1)

랜덤(random)한 수를 다루는 문제는 수학적 코딩 문제의 대표적 유형으로서 자주 출제되나 이 문제를 해결하려면 결코 녹록지가 않다. 이산수학, 조합수학, 추상대수 등의 개념을 담고 있기 때문이다. 하지만 그런 어려운 수학을 전부 공부하지 않더라도 직관과 상식으로 이를 풀어낼 수 있고, 대표적 문제들을 풀다보면 변형된 형태에도 대응할 수 있을 것이라 믿는다. 이 번 포스트에서는 몇 가지 연관된 문제를 풀어본다. EPI (Elements of Programming Interviews in Python)과 LeetCode 등을 참고했다. 부분집합 1 문제: 서로 다른 숫자로 된 배열(원소 n개) A에서 정해진 크기(k)만큼의 원소를 갖는 부분집합 1개를 찾기. 각 부분집합이 나타날 확률은 동일해야 한다. ..

알고리즘/Math 2022.03.29