고대 그리스 수학자 에라토스테네스가 발견한 '에라토스테네스의 체'는 2부터 N까지의 범위에서 소수를 구하는 알고리즘이다. 소수를 판별하는 문제에서 매우 유용하게 사용할 수 있다. 1부터 120까지의 숫자중에서 소수인 숫자를 구하려면 어떻게 해야할까? 1부터 120까지 1씩 숫자를 늘려가며 소수인지 판별할 수도 있겠지만 '에라토스테네스의 체' 알고리즘을 사용하면 보다 빠르게 답을 구할 수 있다. 참고로 '에라토스테네스의 체'의 시간 복잡도는 O(n log(logn)) 이다. '에라토스테네스의 체'의 핵심은 배열에서 소수의 배수를 모두 제거하고 남은 숫자는 모두 소수라는 성질을 이용한 것이다. 아래의 gif를 보자. 우선 2부터 N까지의 숫자를 저장하는 배열을 선언한다. 2부터 시작하는 이유는 1은 소수가 ..
Level1. 소수 만들기 ㆍ문제 설명 주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요. ㆍ 제한사항 nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다. nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다. ㆍ 입출력 예 nums result [1,2,3,4] 1 [1,2,7,6,4] 4 ㆍ입출력 예 설명 입출력 예 #1 [1,2,4]를 이용해서 7을 만들 수 있습니다. 입출력 예 #2 [1,2,4]를 이용해서 7을 만..
우리가 자주 사용하는 반복문, 정렬 알고리즘, 검색 알고리즘, 재귀 함수 등은 입력값에 따라 해당 알고리즘의 실행시간이 증가하게 된다. 이를 점근적 실행시간(asymptotic runtime)이라고 한다. 점근적 측정의 지표로 시간 복잡도 또는 공간 복잡도를 사용할 수 있다. 반대로 입력 값의 증가와 상관없이 항상 같은 실행 시간을 갖는 것을 상수 시간(constant runtime) - O(1) 이라고 한다. 시간 복잡도 표기법 종류 알고리즘의 효율성을 단순하게 구분하면 '최고의 경우', '최악의 경우', '평균적인 경우'의 세가지 측면에서 생각할 수 있다. 시간 복잡도 또한 이러한 세가지 측면에 따라 다르게 표기한다. Big-Ω(빅 오메가) 표기법 - 알고리즘이 최고의 성능을 낼 수 있도록 특별한 조..
