병아리 개발자의 실력 양성기

문제 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를..

양의 정수 n과 k가 주어진다. 정수 n의 약수는 n % i == 0을 만족하는 정수 i로 정의된다. n의 모든 약수를 오름차순으로 정렬한 목록을 고려하여, 이 목록에서 k번째 약수를 반환하거나 n의 약수가 k개 미만인 경우 -1을 반환하세요. 이 문제를 O(n) 복잡도보다 적게 해결하도록 해봅시다 (제한 조건: 1

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