본문 바로가기

CS9

[Algorithm] 에라토스테네스의 체 에라토스테네스의 접근 주어진 자연수 N이 소수이기 위한 필요충분 조건은 N이 N의 제곱근보다 크지 않은 어떤 소수로도 나눠지지 않는다. 소수가 되는 N이 자연수라면 sqrt(N)보다 작은 수로 나눠지지 않음 1, 2, 4, 5, 8, 10, 16, 20, 40, 80 자연수 N : 80, sqrt(80) : 8.xxxx, 2부터 8.xxxx이하만 검색하면 이후의 값은 검사할 필요가 없음 1-80, 2-40, 4-20, 5-16, 8-10이기 때문에 8.xx이하만 검사하면 됨 bool IsPrime(int num) { for (int i = 2; i * i 2022. 11. 14.
[Data Structure] Set Set 비순차적이고 중복을 허용하지 않는 자료구조 집합과 같다고 생각하면됨, 순서 x, 중복 x 순서 상관 없는 경우 빠른 look up 필요한 경우 중복된 값 관련 처리하는 경우 유용하게 사용할 수 있다. Set 종류 HashSet 대표적인 Set 사용 방식 Hash 알고리즘을 기반으로 동작함 key값을 hash function을 거쳐 hash값으로 변경 후 hash값에 맞는 bucket에 저장하여 관리한다. 이러한 알고리즘 때문에 순서 x, 중복 x, 특정값 포함 확인 빠름 (Fast Lookup) TreeSet balance binary search tree인 Red-Black Tree를 기반으로 구성된다. 간단히 말해서 값이 한쪽으로 치우쳐지지 않는 Tree 사용한다는 말 Red-Black Tre.. 2022. 10. 23.
[Algorithm] 유클리드 알고리즘 (GCD) 유클리드 알고리즘 - 주어진 두 수 사이에 존재하는 최대 공약수 (GCD) 구하는 알고리즘 - 자세한건 유클리드 호제법 참고 - gcd ( a, b ) == gcd ( b, r ) 이다. (a,b 자연수 / r은 a를b로 나눈 나머지) 원리 자연수 a, b가 주어짐 이때 a가 b보다 큰 값임 int a = 자연수 int b = 자연수 a 를 b로 나눈 나머지가 r 이면 int r; r = a % b; r이 0이면 b가 최대 공약수(gcd) 이다. if (r == 0) return b; 만약 r이 0이 아니면, a에 b값 넣고, b에 r값 넣고, 다시 두번째 부터 반복하면 된다. while(1){ int r = a % b; if( r == 0 ) return b; a = b; b = r; } 공식 int .. 2022. 10. 17.

티스토리툴바