[알고리즘 공부 5일차]

1. 소수찾기

소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수다.
그러므로 1을 소수가아닌것으로 2,3을 소수로 예외처리해주고
나머지는 2와 3으로 나머지연산을 한후 만약 나누어떨어진다면 소수가아닌것으로 한다(시간복잡도를 나누기위함 2와 3을 약수로 가지는데 굳이 끝까지 연산할 필요가없음)
2와 3을 약수로 가지지않는다고해도 소수일 가능성이있으므로 반복문을 통해 자신보다 1작은수까지 나눠서 소수임을 판별

2.소수

1번과 동일한 소수판별 함수를 사용하고 a,b를 받아 a부터 b까지 소수를 count에 더해주면서 처음으로나온 소수를 min 저장하고 만약 소수가 하나도 없어 count가 0이라면 -1을 출력해서 해결했다.

3.소인수분해

정수 a를 입력으로 받고 a > 1인동안 2로 약분해보고 안된다면 3..4로 하나씩 증가하면서 약분하며 약분되면 약분한수를 출력 하고 a를 a/약분한수로 대입해준다

4.소수 구하기

1과동일하게 빠른시간복잡도를 위해 n일때 1부터 n까지 전체를 검색하는것이 아닌 n의 제곱근 + 1 미만까지 검사하는식으로 소수를 판별한다

5.베르트랑 공준

4번에서 소수검사의 범위를 입력받은 a < i <= 2*a로 바꾸면 간단하게 해결할수있다.

6. 골드바흐의 추측

입력받은 수를 a라고 하면 b = a / 2, c= a -b로 한다(절반부터 검사해야 두 수의 차이가 제일 작은경우를 알수있기때문) 다음 b와 c가 소수인지 판별해서 만약 둘다 소수라면 두 수를 출력해주면 된다

7.직사각형에서 탈출

사각형 안에 있는 점에서 변에 닿는 최소거리를 구해야 하므로
1. h-y
2. w-x
3. x
4. y
중에 가장 작은값을 출력해주면 된다중에 가장 작은값을 출력해주면 된다

8.네번째 점

입력으로 받은 x,y좌표를 각각 x1,x2,x3,y1,y2,y3라고 한다면

x = (x1 == x2) ? x3 : (x1 == x3 ? x2 : x1);
y = (y1 == y2) ? y3 : (y1 == y3 ? y2 : y1);

를 통해 x,y좌표를 알수있다

9.직각삼각형.직각삼각형

a[3]에 세 숫자를 입력받은뒤 반복문을 통해 배열에서 가장 큰 인자의 위치를 변수 key에 넣는 방법으로 가장 큰 인자를 정한뒤 피타고라스의 법칙을 사용해 문제를 해결한다 a^2 = b^2+ c^2

10. 택시 기하학

유클리드 기하학에서의 원의 넓이는 r^2 pi 이고
택시 기하학에서는 r2 2 이다 r을입력받고 pi상수를 사용하위해
#define _USE_MATH_DEFINES
#include <math.h>
를 해준후 각각의 넓이를 출력해주면된다.

11. 터렛. 터렛

두 원이 위치관계를 구하는 문제이다
x1,y1,x2,y2는 각각 두원의 중심좌표
r1,r2는 각 원의 반지름을 의미한다
경우는 4가지로 나뉜다.
사용하기위해

big_r = (double)max(r1-r2, r2-r1);
d = sqrt(pow(x2 - x1, 2) + pow(y2 - y1, 2));

로 대입한다 big_r은 큰반지름에서 작은 반지름을 뺀것이고 d는 두원의 중심좌표 사이의 거리이다
1.같은원일경우(점 무한대) (x1 == x2 && y1 == y2 && r1 == r2)
2.두점에서 만날때 (big_r < d && d < r1 + r2)
3.1점에서 만날때 (r2 + r1 == d || big_r == d) 각각 외접과 내접
4.만나지 않을때 ((r1 + r2) < d || d < big_r || d == 0)
두원이 서로 밖에있을때와 큰원안에 한원이 있을때 그리고 중심은 같고 반지름이 다를 경우이다.

이 조건을 조건문에 넣어서 계산하면 마린의 위치의 가능성을 구할수있다.