목록자료구조 (2)
Sun's Blog
맨하탄 계산법
좌표계에 두점 P, Q 가 주어질때 두 점사이의 거리는 아래와 같이 정의된다. n차원일 경우 각 n까지 계산하면 된다.
자료구조/Algorithm
2023. 5. 22. 21:03
에라토스테네스의 체
고대 그리스 수학자 에라토스테네스가 발견한 소수를 찾는 방법 1부터 소수를 구하고자 하는 구간(n)의 모든 수를 나열한다. 일단 소수도, 합성수도 아닌 유일한 자연수 1을 제거한다. 2를 제외한 2의 배수를 제거한다. 3을 제외한 3의 배수를 제거한다. 4는 2의 배수이므로 넘어간다. 이렇게 루트n 까지 반복한다. 제거되지 않은 수들이 소수이다. 루트n까지 하는 이유는 n보다 작은 어떤 수 m이 m =ab라면 a와 b 중 적어도 하나는 루트n 이하이다. 즉 n보다 작은 합성수 m은 루트n보다 작은 수의 배수만 체크해도 전부 지워진다는 의미이므로, 루트n 이하의 수의 배수만 지우면 된다. Java import java.util.*; /** 프로그래머스 12921 소수 찾기 크기가 n인 배열 arr 생..
자료구조/Algorithm
2023. 5. 11. 15:34