csmoon1010의 SW 블로그

0. 문제 유형 : 조합(완전탐색, 재귀), 소수(에라토스테네스의 체) 1. 문제 이해 (1) 주요 요구사항 - nums : 숫자들이 들어가 있는 배열 - nums 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 return (2) 제한사항 - nums의 길이 : 3개 이상 50개이하 → 완전탐색 가능 - nums의 원소 : 1이상 1000이하 → 3개 수의 합 < 3000, int형 사용 가능 - nums의 원소 : 중복된 숫자 없음 → 중복 조합 상황 고려X 2. 전략 (1) 소수 판단 : public boolean[] calcPrime(int n) - 나올 수 있는 소수의 범위 : 3000보다 작음 ▶ 3000까지의 수에 대해 에라토스테네스의 체로 소수 구하기 - 에라토스테네스의 체 esw-c..

1. 완전탐색(Brute-force)? : 모든 경우의 수를 탐색하여 문제를 푸는 방식. 대표적인 예로 순열, 조합이 있음 2. 순열(Permutation, nPk) : n개의 요소들 중 k개를 뽑아 '정렬'할 수 있는 경우의 수 (1) 전통적인 순열 구하는 방법 - k개의 자리에 올 수 있는 요소의 개수를 세는 방식 - n x (n-1) x (n-2) x ... x (n-k+1) = n! / (n-k) ! - 단, 위의 수식은 단순히 "개수"를 구하는 방법일 뿐 완전탐색에 조건을 적용하기엔 부족함 (2) 순열 알고리즘 : 0~k번째에 수를 고정시킨다. [과정] ① depth번째 수 고정 - 방법1) 첫번째 수와의 swap을 통해 지정 - 방법2) 고정여부를 담은 visited배열(n과 같은 길이)에 표..